Quick

Interface

QuickSort

This functions performs the actual work of a quick sort. The quick sort is based on the divide-and-conquer idea. It recursively divides the array up into sub-arrays, partitioning at each level. The partitioning step is the most complex. It works by splitting the array into two portions, the left of which is less than or equal to a given pivot value. This right portion is greater than the pivot. A series of swaps are performed to make the array obey these criteria. With this work done, the pivot value lies in its final place in the sorted array. The two portions are then quick sorted again, until they reach a size of 1 element.

Parameters

vals	the array of values to be sorted
left	left bound of region to sort
right	right bound of region to sort

Authors

James Warren (July 2005)

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

QuickSort

Quick sort permutes an array of values to lie in ascending numerical order. This is the fastest general sort available. It is often the best practical choice for sorting. The complexity of the quick sort is:

The limitations of quick sort are that it is a relatively complex algorithm, and is largely recursive. This means that for large data arrays there is a possibility of stack overflow. For this reason quick sort should be avoided in these circumstances. A good rule of thumb is data sets of up to a million items, though this value is entirely dependent on hardware. This function sets up the recursive call to <em> quickSortRecur </em>. It is present to shield the programmer from the intricacies of the quick sort algorithm. Please see <em> quickSortRecur </em> for a description of the actual algorithm.

Example 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
#include <codecogs/computing/sort/quick.h>
 
int main()
{
  double vals[25];
  int n=25;
 
  srand((unsigned int) time(NULL));
  for (int i=0; i<n; i++) vals[i]=((double) n*rand())/RAND_MAX;
 
  printf("\nArray to be sorted:\n");
  for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
  printf("\n");
 
  Computing::Sort::quickSort<double>(vals, n);
 
  printf("Sorted array:\n");
  for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
  printf("\n");
  return 0;
}

Output:

Array to be sorted:
 12  23  10  23   4
  2   9  19  14  16
 22   5   7  16   1
  6   8  24  13  21
  9  17   1   3   6
Sorted array:
  1   1   2   3   4
  5   6   6   7   8
  9   9  10  12  13
 14  16  16  17  19
 21  22  23  23  24

Parameters

vals	the array of values
n	the number of items in the array

Authors

James Warren (July 2005)

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.