CodeCogs

Quick sort an array of values into ascending numerical order.

You're viewing an older version of this page (#4). View the current version.

Interface

#include <codecogs/computing/sort/quick.h>

using namespace Computing::Sort;

template <class T>void quickSort(T *vals, int n)

Overview

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

FUNCTION

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:

$T(n) = O(n\ log_2\ n)$

(1)

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

the number of items in the array

Author

James Warren (July 2005)