Thread: sorting array in increasing order

When we have

list = 5 4 3 2 1

how to sort array in increasing order ? list = 1 2 3 4 5

here is process how I think

5 - 4 compare if greater then update 4 5 3 2 1
5 - 3 compare if greater then update 4 3 5 2 1
5 - 2 compare if greater then update 4 3 2 5 1
5 - 1 compare if greater then update 4 3 2 1 5

and so more

I wrote my program to sort array in increasing order

Code:

#include <stdio.h>

int main()
{
    int i = 0; int j = 0; int k = 0;
    
    int list[5] = {5, 4, 3, 2, 1};
    
    int temp[5];
    
    for (i = 0; i <5; i++)
    {
         for (j = i+1 ; j <5; j++)
         {
             if (list[i]>list[j]) // if the one is greater then other swap value 
             {
                 temp[k] = list[j];
                 list[i] = temp[k];
                 
             }
         }
         
    }
    
    return 0;
}

What's wrong in code

You're not swapping anything at line 17.

Swaps typically take 3 lines of code.

If we have X = 1 and Y = 3 when we will swap it would X = 3 and Y = 1

X=1, Y=3, Temp = 0

Temp = X=1
X = Y = 3
Y = temp = 1

After swapping X =3 and Y = 1

Code:

#include <stdio.h> 
int main()
{
    int i = 0; int j = 0; int k = 0;
     
    int list[5] = {5, 4, 3, 2, 1};
     
    int temp[5];
     
    for (i = 0; i <5; i++)
    {
         for (j = i+1 ; j <5; j++)
         {
             if (list[i]>list[j]) // if the one is greater then other swap value 
             {
                 temp[k] = list[i];
                 list[i] = list[j];
                 list[j] = temp[k];
                  
             }
             printf("%d", list[j]);
         }
          
    }
     
    return 0;
}

> printf("%d", list[j]);
Move it into the i loop, and print subscript i instead.

Also, you don't need an array of temp, just one.

> return (*(int *)ap > *(int *)bp) - ( *(int *)ap < *(int *)bp );
Unnecessarily terse, and contains a bug.
Try again.

There's a host of sorting algorithms. The one that is usually used in practice is quicksort, because it is fast and fairly easy to implement. However it requires recursion.

Selection sort or insertion sort are easier to understand, and actually faster for very small arrays, but unacceptably slow for large arrays. Bubble sort is taught in introductory computer science classes. It's not a very good algorithm, but it's a good example of an algorithm. Merge sort is easier than quicksort and has similar good performance, but it's slightly tricky to code correctly.

There are many more.

Originally Posted by flp1969

A more "generic" approach:

Code:

#include <stdlib.h>

// Comparison funcions named after type and identifier.
#define QSORT_CMP_FN_ASC(T,FN) FN ## _ ## T ## _A
#define QSORT_CMP_FN_DESC(T,FN) FN ## _ ## T ## _D

// Definition of comparison functions based on type and identifier.
#define QSORT_CMP_ASC(T,FN) \
  int QSORT_CMP_FN_ASC(T,FN) ( const void *a, const void *b ) \
  { \
    return (*(const T *)a > *(const T *)b) - \
           (*(const T *)a < *(const T *)b); \
  }

#define QSORT_CMP_DESC(T,FN) \
  int QSORT_CMP_FN_DESC(T,FN) ( const void *a, const void *b ) \
  { \
    return (*(const T *)a < *(const T *)b) - \
           (*(const T *)a > *(const T *)b); \
  }

// qsort() function call based on ponter to buffer, number of elements, type and identifier
#define QSORT_ASC_CALL(ptr,E,T,FN) \
  qsort( ptr, E, sizeof(T), QSORT_CMP_FN_ASC(T,FN) )

#define QSORT_DESC_CALL(ptr,E,T,FN) \
  qsort( ptr, E, sizeof(T), QSORT_CMP_FN_DESC(T,FN) )


// Define ascending comparison static function for ints (qsort).
static QSORT_CMP_ASC(int, cmp)

// Example for ascending sort.
void sort( int *p, size_t elements )
{ QSORT_ASC_CALL( p, elements, int, cmp ); }

Or maybe just make the comparison a macro and let the user define the function. Might make things a little clearer anyway:

Code:

#include <stdlib.h>

#define SORT(array, length, compare)\
qsort(array, length, sizeof(*array), (int (*)(const void*, const void*))compare)

#define STACK_SORT(array, compare)\
SORT(array, sizeof(array)/sizeof(*array), compare)

#define COMPARE(left, right) (((left) > (right)) - ((left) < (right)))

/* TEST */

#include <stdio.h>

struct thing
{
 int id;
};

int compare_things(struct thing* thing_one, struct thing* thing_two)
{
 return COMPARE(thing_one->id, thing_two->id);
}

int main()
{
 struct thing things[] = {{ 4 }, { 1 }, { 2 }, { 9 }, { 7 }};
 STACK_SORT(things, compare_things);
 for(size_t tdx = 0; tdx < 5; ++tdx)
  printf("%d ", things[tdx].id);
 puts("");
}

Originally Posted by Malcolm McLean

However it requires recursion.

You are aware that any recursive routine can be made without recursion, right?

Here's a quicksort without recursion (using an allocated stack):

Code:

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_ELEMENTS(a) ( sizeof a / sizeof a[0] )
#define swap(a,b) { int t; t=(a); (a)=(b); (b)=t; }

static ssize_t partition( int *arr, ssize_t l, ssize_t h )
{
  ssize_t i, j;
  int x;

  x = arr[h];
  i = l - 1;

  for ( j = l; j <= h - 1; j++ )
    if ( arr[j] <= x )
    {
      i++;
      swap( arr[i], arr[j] );
    }

  swap( arr[i + 1], arr[h] );

  return i + 1;
}

void quickSort( int *arr, ssize_t l, ssize_t h )
{
  ssize_t *stack, top, p;
  size_t size;

#define PUSH(v) do stack[++top] = (v); while(0)
#define POP(v) do v = stack[top--]; while(0)

  size = sizeof( ssize_t ) * ( h - l + 1 );
  if ( !( stack = malloc( size ) ) )
  {
    fprintf( stderr, "ERROR allocating memory (%zd bytes) for quickSort() stack!\n", size );
    exit( EXIT_FAILURE );
  }

  top = -1;

  // push initial values of l and h to stack
  PUSH( l );
  PUSH( h );

  // Keep popping from stack while is not empty
  while ( top >= 0 )
  {
    // Pop h and l
    POP( h );
    POP( l );

    // Set pivot element at its correct position
    p = partition( arr, l, h );

    // If there are elements on left side of pivot,
    // then push left side to stack
    if ( p - 1 > l )
    {
      PUSH( l );
      PUSH( p - 1 );
    }

    // If there are elements on right side of pivot,
    // then push right side to stack
    if ( p + 1 < h )
    {
      PUSH( p + 1 );
      PUSH( h );
    }
  }

  free( stack );
}

static void printArray( int *arr, size_t n )
{
  while ( n-- )
    printf( "%d ", *arr++ );
  putchar( '\n' );
}

// test
int main(void)
{
  int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 };

  quickSort( arr, 0, ARRAY_ELEMENTS( arr ) - 1 );

  printArray( arr, ARRAY_ELEMENTS( arr ) );

  return EXIT_SUCCESS;
}

BTW: This is, more or less, the implementation used on glibc.

PS: You can avoid the dynamic allocation of the "stack" since we need only log2(elements) entries.. If you use a stack of 64 elements it will cover any array possible, in memory. Anyway, this is also the case for a recursive quick sort, which won't exhaust the stack for the same reason.

That's a very clean quicksort.

sort array in increasing order

Code:

#include <stdio.h>

#define max 4096
#define prc 25

int arr[max] = { 
    0, 11, 16, 4,
    10, 54, 0, 0,
    76, 101, 178,
    44, 57, 167, 77, 10, 
    5, 6, 8, 1, 3, 4, 5
};

int sorted() {    
    int c = 0;
    for (int i=0; i<prc; i++) {
        if ( arr[i] > arr[i+1] ) {
            c = arr[i+1];
            arr[i+1] = arr[i];
            arr[i] = c;
            return 0;
        }
    }
    return 1;
}

int sort() {
    while ( !sorted() ) { };
    return 0;
}

int main() {

    for (int i =0; i<prc; i++) {
        printf("%i,",arr[i]);
    }  

    printf("\n"); sort();

    for (int i =0; i<prc; i++) {
        printf("%i,",arr[i]);
    }

    return 0;
}