Interface

#include <codecogs/array/sort/quick_sort.h>

using namespace Array::Sort;

	template<class T> void	quickSort (T vals[], int left, int right) The actual work function of quickSort. Performs the recursion.
	template<class T> void	quickSort (T *vals, int n) Quick sort an array of values into ascending numerical order.

---

Function Documentation

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:

- To get code register with CodeCogs. Already a Member, then Login.

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 quickSortRecur . It is present to shield the programmer from the intricacies of the quick sort algorithm. Please see quickSortRecur for a description of the actual algorithm.

Example:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
#include <codecogs/array/sort/quick_sort.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");
 
  Array::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:

- To get code register with CodeCogs. Already a Member, then Login.