Quick Sort (QuickSort) Algorithm, also called as partition exchange sort, is a very fast sorting algorithm that developed by British computer scientist Tony Hoare in 1959. It gets a pivot element as pivot and partitions the given array around this element. QuickSort method can be summirized as Divide and Conquer Algorithm. There are many versions of QuickSort that pick elements in different ways. Basically, 4 methods are listed as below;
- Always pick first element as pivot.
- Always pick last element as pivot (implemented below)
- Pick a random element as pivot.
- Pick median as pivot.
In C++, standard library also has qsort algorithm that can be directly used with a given comparison method. To use this qsort(…) algorithm we must define our compare function and it should return integer.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <vcl.h> #include <stdlib.h> /* qsort */ #include <stdio.h> int compare(const void * aa, const void * bb) { int a=*(int*)aa, b=*(int*)bb; if (a < b) return (-1); else return(1); } int _tmain(int argc, _TCHAR* argv[]) { int n=6, mat[6] = { 5, 32, 37, 7, 2, 9 }; qsort(mat, n, sizeof(int), compare); // stdlib qsort algorithm for (int i=0; i<n; i++) printf ("%d,",mat[i]); getchar(); return 0; } |
The main idea in QuickSort is partitioning to element groups and using itself as a recursive procedure. Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
Let’s learn to build our own quicksort. QuickSort algorithm gets a pivot ( here it is pi ) by partition sort in range . Then it recursively keeps running quicksort() to sort two lower and higher partitions by using these high and low parameters. An example of my_quicksort(…) is given as below;
|
1 2 3 4 5 6 7 8 9 10 11 |
void my_quicksort(int array[], int low, int high) { if ( low < high ) { int pi = my_partitionsort( array, low, high ); my_quicksort( array, low, pi - 1 ); my_quicksort( array, pi + 1, high ); } } |
To use this my_quicksort(…) we need to write my_partitionsort(…) partition sort algorithm as below;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
int my_partitionsort( int array[], int low, int high) { int swap, pivot = array[high]; // swap & pivot int i = (low - 1); // Index of smaller element for ( int j = low; j <= high-1; j++) { if (comp (array[j] , pivot)) // if smaller than the pivot { i++; swap=array[i]; array[i]=array[j]; array[j] =swap; } } swap=array[i+1]; array[i+1]=array[high]; array[high] =swap; return i+1; } |
Here we used comp(…) compare function which has two integer parameters and returns bool, for specific comparisons we can define our own compare function as below;
|
1 2 3 4 5 6 |
bool static comp(int a, int b) { return (a*pow(10,(1+(int)log10(b)))+b) > (b*pow(10,(1+(int)log10(a)))+a); } |
Here is the full C++ Builder Console VCL Example below;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <vcl.h> #include <windows.h> #include <tchar.h> #include <stdio.h> #include <stdio.h> /* printf */ #include <stdlib.h> /* qsort */ #include <math.h> /* pow */ #pragma hdrstop #pragma argsused //------------------------------------------------------- int my_partitionsort( int array[], int low, int high) { int swap, pivot = array[high]; // swap & pivot int i = (low - 1); // Index of smaller element for ( int j = low; j <= high-1; j++) { if (comp (array[j] , pivot)) // if smaller than the pivot { i++; swap=array[i]; array[i]=array[j]; array[j] =swap; } } swap=array[i+1]; array[i+1]=array[high]; array[high] =swap; return i+1; } //------------------------------------------------------- void my_quicksort(int array[], int low, int high) { if ( low < high ) { int pi = my_partitionsort( array, low, high ); my_quicksort( array, low, pi - 1 ); my_quicksort( array, pi + 1, high ); } } //------------------------------------------------------- int _tmain(int argc, _TCHAR* argv[]) { int i,n=5, mat[5] = { 3, 30, 34, 5, 9 }; my_quicksort(mat, 0, n - 1); return 0; } |
Head over and find out more about building Windows apps in C++Builder.
