quicksort

Definition: Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the two partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.

The basic idea is as follows:

1. pick one element in the array, which will be the pivot.

2. make one pass through the array, called a partition step, re-arranging the entries so that:

   • the pivot is in its proper place.

   • entries smaller than the pivot are to the left of the pivot.

   • entries larger than the pivot are to its right.

3. recursively apply quicksort to the part of the array that is to the left of the pivot, and to the part on its right.

See http://mathworld.wolfram.com/Quicksort.html for more discussion and references on QuickSort.

Fast algorithm for random distributions. Worst case in O(n²), when the array is already sorted. For random arrays, the algorithm has O(n log(n)) complexity.

Algorithm in Java (source: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm )

void quicksort (int[] a, int lo, int hi)
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    //  partition
    do
    {    
        while (a[i]<x) i++; 
        while (a[j]>x) j--;
        if (i<=j)
        {
            h=a[i]; a[i]=a[j]; a[j]=h;
            i++; j--;
        }
    } while (i<=j);

    //  recursion
    if (lo<j) quicksort(a, lo, j);
    if (i<hi) quicksort(a, i, hi);
}

Algorithm in C

/*

* This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation; either version 2 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program; if not, write to the Free Software

* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

*

* This program demonstrates the use of the quick sort algorithm. For

* more information about this and other sorting algorithms, see

* http://linux.wku.edu/~lamonml/kb.html

*

*/

#include <stdlib.h>

#include <stdio.h>

#define NUM_ITEMS 100

void quickSort(int numbers[], int array_size);

void q_sort(int numbers[], int left, int right);

int numbers[NUM_ITEMS];

int main()

{

int i;

//seed random number generator

srand(getpid());

//fill array with random integers

for (i = 0; i < NUM_ITEMS; i++)

numbers[i] = rand();

//perform quick sort on array

quickSort(numbers, NUM_ITEMS);

printf("Done with sort.\n");

for (i = 0; i < NUM_ITEMS; i++)

printf("%i\n", numbers[i]);

}

void quickSort(int numbers[], int array_size)

{

q_sort(numbers, 0, array_size - 1);

}

void q_sort(int numbers[], int left, int right)

{

int pivot, l_hold, r_hold;

l_hold = left;

r_hold = right;

pivot = numbers[left];

while (left < right)

{

while ((numbers[right] >= pivot) && (left < right))

right--;

if (left != right)

{

numbers[left] = numbers[right];

left++;

}

while ((numbers[left] <= pivot) && (left < right))

left++;

if (left != right)

{

numbers[right] = numbers[left];

right--;

}

}

numbers[left] = pivot;

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot)

q_sort(numbers, left, pivot-1);

if (right > pivot)

q_sort(numbers, pivot+1, right);

}