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

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!

CodePudding user response：

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