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.
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;
To use this my_quicksort(…) we need to write my_partitionsort(…) partition sort algorithm as below;
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;
Here is the full C++ Builder Console VCL Example below;
Head over and find out more about building Windows apps in C++Builder.