C++ quick sort
Quick sort is a powerful sorting alogrithm. It sort a set in O( n*log(n) ).There are bad cases which the big O can be O(n^2). However, the case is very very rare.
In order to understand this sorting algoritm, you need to know what recussive funtion..
If you do not know that, think it as using same function over and over; you will see that soon.
Let's say that you would like to sort the following array.
In order to do quick sort, you need two functions.
One is called, "quick_sort." The other one is called "partition."
"quick_sort" calls the "partition".
"partition" picks one of array value( only one!!!!), place the value to right position and return the position of value
quick_sort
void quickSort (int array[], int low, int high)
{
if( low < high ){
int position = partition(array, low, high);
quickSort (array, low, position-1);
quickSort (array, position+1, high);
}
else{
return;
}
}
array = arrary that you want to sort
low = first index of set
high = last index of set
The first thing the "quick_sort" is checking whether the low is smaller than high.
It may look strange to you. However, if you read the following three line, you can understand the reason.
After chekcing the condition, "quick_sort" calls "partition" to place one element to right poisiton in the array.
"partition" makes sure one element of the array is in the right position and returns position.
The position is used to create two "quick_sort"s.
quickSort (array, low, position-1); -----> low = low position -1 = high
quickSort (array, position+1, high); ------> low = position+1 high = high
"quick_sort" makes "quick_sort"s over and over until low >= high.
This kind of function is called recursive function.
Then I will move on to the "partiton"
Just like "quick_sort", you have three parameters arary, low high
int partition (int array[], int low, int high)
In the you need to have three tools
They are
i = index
j = index
pivot_val = array[ high ]
It would be like this
6 3
1 3
Do this untill i reach "high"
Then switch array[i] and array[j]
The element is in yellow box is placed right postion. "partiton", returns the position of this.
"quick_sort" calls "quick_sort"s to work on The rest elemnt of array
The power of quick sort is that everytime, if place a element in right postiion, it it will breaks array into small pieces for sorting.
I made a sample code.
-------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.
#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <ctime>
#include <cstdlib>
using namespace std;
void quickSort (int array[], int low, int high);
int partition (int array[], int lcow, int high);
int main()
{
srand(time(0));
int array[8] = {7,6,4,1,20,4,5,7};
int len = 8;
/*
// populate array with random number between 0 to 99
for (int i = 0; i < len; i++)
{
array[i] = rand()%100;
}
*/
quickSort(array, 0, 7);
for (int i = 0; i < len; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
/*
* @brief Do quick sort (recursive function)
* @param int array[] - array that is needed to be sort
* @param int low - min bound for sorting
* @param int high - max bound for sorting
* @return void (call by referece) sorted array
*/
void quickSort (int array[], int low, int high)
{
if( low < high ){
// after the partition, val in the position is sorted
int position = partition(array, low, high);
cout << "position " << position << endl;
// sort values before the postion
quickSort (array, low, position-1);
// sort values after the position
quickSort (array, position+1, high);
}
// if row and high are same, there is nothing to be sorted, so termimate the sorting
else{
return;
}
}
/*
* @brief Pick a pivot and put it in the right position
* @param int array[] - array that is needed to be sort
* @param int row - min bound for sorting
* @param int high - max bound for sorting
* @return index of pivot
*/
int partition (int array[], int low, int high)
{
int tmp;
int pivot_val = array[high];
int j=low;
int i;
for(i=low; i<high; i++){
if( array[i] <= pivot_val ){
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
j++;
}
}
tmp = array[high];
array[high] = array[j];
array[j] = tmp;
return j;
}
