How to sort an array that going down and then going up, to array that going down all the way?

user_19252103 0
Viewed 106

I have an assignment to make a function that sort array that going down and then going up (for example: 9, 8, 7, 6, 5, 7, 11, 13) to array that going down all the way (for example: 13, 11, 9, 8, 7, 7, 6, 5).

I wrote this in online compiler (programiz), but it just doesn't work for me.

#include <stdio.h>
#include <stdlib.h>
#define N 10

void sort_dec_inc(int a[], int n) {
  int pivot, i, q = 0;
  int c[n];
  for (i=0; i<n; i++) {
      c[i] = 0;
  }
  for (i=0; i<n-1; i++) {
      if (a[i]<a[i+1]) {
          pivot=i+1;
          break;
      }
  }
  if (pivot == n-1) {
      return;
  }

  for (i=0; i<pivot && n>=pivot; q++) {
      if (a[i]>=a[n]) {
          c[q] = a[i];
          i++;
      }
      else {
          c[q] = a[n];
          n--;
      }
   }
   
   
   if (n==pivot) {
       while(i<pivot) {
           c[q] = a[i];
           q++;
           i++;
       }
   }
   else {
       while (n>=pivot) {
           c[q] = a[n];
           q++;
           n--;
       }
   }
   
   for(i=0; i<n; i++) {
       a[i] = c[i];
   }
   
   
}

int main()
{
    int num_arr[N] = {9, 7, 5, 3, 1, 2, 4, 6, 8, 10};
    sort_dec_inc(num_arr, N);
    int i;
    for(i = 0; i < N; i++) {
        printf("%d ", num_arr[i]);
    }

    return 0;
}

output (most of the times) : 9 7 5 3 1 2 4 6 8 10

Sometimes the output is different, for example: (410878976 10 9 8 1 2 4 6 8 10 )

If someone can answer in simple code its the best, I don't understand yet all the options in C.

(I'm sorry if its a clumsy code, I'm new for this.) thanks a lot!

function-definition sorting c arrays
3 Answers

For starters it is a bad idea to define an auxiliary variable length array. Such an approach is unsafe because the program can report that there is no enough memory to allocate the array.

At least this code snippet

for (i=0; i<n-1; i++) {
    if (a[i]<a[i+1]) {
        pivot=i+1;
        break;
    }
}
if (pivot == n-1) {
    return;
}

contains a logical error.

Consider an array that contains only two elements { 1, 2 }. In this case a[0] is less than a[i+1] that is than a[1]. So the condition of the if statement

if (pivot == n-1) {
    return;
}

evaluates to logical true and the function returns the control though the array was not sorted in the descending order. It stays unchanged.

Or consider this code snippet

  if (a[i]>=a[n]) {
      c[q] = a[i];
      i++;
  }

The expression a[n] accesses memory beyond the array that results in undefined behavior.

A straightforward approach is to use the method insertion sort.

Here is a demonstration program.

#include <stdio.h>
#include <string.h>

void insertion_sort( int a[], size_t n )
{
    size_t i = 1;

    while ( i < n && !( a[i-1] < a[i] ) ) i++;

    for ( ; i < n; i++ )
    {
        size_t j = i;

        while ( j != 0 && a[j-1] < a[i] ) --j;

        if ( i != j )
        {
            int tmp = a[i];
            memmove( a + j + 1, a + j, ( i - j ) * sizeof( int ) );
            a[j] = tmp;
        }
    }
}

int main( void )
{
    int a[] = { 9, 7, 5, 3, 1, 2, 4, 6, 8, 10 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    insertion_sort( a, N );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

The program output is

9 7 5 3 1 2 4 6 8 10 
10 9 8 7 6 5 4 3 2 1
user_28772410

Solution based on the comments below:

#include <stdio.h>
#include <stdlib.h>
#define N 10

void sort_dec_inc(int a[], int n) {
  int left, i = 0;
  int right = n-1;
  int c[n];
  while (i<n) {
      if (a[left] >= a[right]) {
          c[i] = a[left];
          left++;
      }
      else {
          c[i] = a[right];
          right--;
      }
      i++;
  }
  
  for(i=0; i<n; i++) {
       a[i] = c[i];
   }
   
}

int main()
{
    int num_arr[N] = {9, 7, 5, 3, 1, 2, 4, 6, 8, 10};
    sort_dec_inc(num_arr, N);
    int i;
    for(i = 0; i < N; i++) {
        printf("%d ", num_arr[i]);
    }

    return 0;
}

output: 10 9 8 7 5 5 4 3 2 1

user_192431110

I would recommend a bubble sort. It is an easy way to sort numbers in numerical order:

for (int i = 0; i < quant; i++)
{
  for (int j = 0; j < quant-1; j++)
  {
    if (Array[j] < Array[j + 1])
    {
      int temp = Array[j];
      Array[j] = Array[j + 1];
      Array[j + 1] = temp;
    }
  }
}

quant is the quantity of numbers you want to sort. Don't forget to define an integer array with length quant for the sorting process.

To access the array, just use a for loop to return all the results.

user_196231420
Related