C Quick Sort Source

Algorithms in C - quicksort.c

<source lang="c"> /* Sort function based on Quick Sort with a moving pivot point. Sorts values */ /* between lower_start_index and upper_start_index. Calls itself recursively.*/ /* If lower index and upper index are neighbours, the sort is reduced to a */ /* conditional swap. */ void sort( int* list, const int lower_start_index, const int upper_start_index ) {

  /* Set the pivot value to half way between upper and lower start points */
  const int pivot_index = ( lower_start_index + upper_start_index ) / 2;
  const int pivot_value = list[ pivot_index ];

  int tmp;
  int lower_index = lower_start_index;
  int upper_index = upper_start_index;

  /* If the lower index and upper index are neighbours, swap if necessary */
  if( upper_start_index <= lower_start_index + 1 )
  {
     if( list[ lower_start_index ] > list[ upper_start_index ] )
     {
        tmp = list[ lower_index ];
        list[ lower_index ] = list[ upper_index ];
        list[ upper_index ] = tmp;
     }

     return;
  }

  /* Move the index points together until they cross */
  while( lower_index < upper_index )
  {
     /* Move the lower index up until it reaches a value greater than or equal
        to the pivot value */
     while( list[ lower_index ] < pivot_value &&
                    lower_index < upper_start_index )
     {
        lower_index++;
     }

     /* Move the upper index down until it reaches a value lower than pivot */
     while( list[ upper_index ] > pivot_value &&
                    upper_index > lower_start_index )
     {
        upper_index--;
     }

     if( lower_index < upper_index )
     {
        /* Swap the two values if the index points have not crossed over */
        tmp = list[ lower_index ];
        list[ lower_index ] = list[ upper_index ];
        list[ upper_index ] = tmp;

        /* Move the index points on until they cross over */
        lower_index++;
        upper_index--;
     }
  }

  /* Now the index points have met sort the list above and below the point */
  if( lower_start_index < upper_index )
  {
     sort( list, lower_start_index, upper_index );
  }
  
  if( lower_index < upper_start_index )
  {
     sort( list, lower_index, upper_start_index );
  }

} </source>