Home Arrays Quick Sort

# Quick Sort

This algorithm is one of the specific ones people generally have a problem to understand. We will try out best to simplify it and understand it.
Basically quick sort comprises of these steps:-

1. Choose a pivot element (it can be any random element in array)
2. In one iteration keep all the numbers smaller to it on the left side and larger to it on the right side.
(smaller numbers)_ _ _[PIVOT]_ _ _(larger numbers)
3. Now we have the left sub-array of (small numbers) and the right sub-array (large numbers)
4. Repeat steps 1 and 2 recursively on both the sub-arrays until we are left with just single elements.
5. This should give you the final sorted array.

#### Illustration

Quick Sort works on the principle of Divide and Conquer algorithmic paradigm. The image below will illustrate the concept in a better way. In this example, we are choosing the first element of the array as the pivot element. The selected pivot element is represented in blue.

#### Algorithm

Basically, we can choose any element as the pivot element. The algorithm for quick sort will be therefore:-

.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
# choose pivot
swap a[1, rand(1, n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a, swap a[++k, i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1, n]

Now let us take an example with array

arr[] = {2, 6, 4, 10, 8, 1, 9, 5, 11, 7};

And we will choose the last element as the pivot element.

1. PIVOT = 7 or arr
2. Now we apply the iteration in the range 0-9 , leaving the pivot.
3. We start from the left side, keeping “i” as a pointer
• if(2 < pivot)  => move ahead (i = 0)
• if(6 < pivot)  => move ahead (i = 1)
• if(4 < pivot)  => move ahead (i = 2)
• if(10 < pivot) => NO, STOP (i = 3 and points to 10)
4. Now we start from the right side, keeping “j” as a pointer
• if(11 > pivot)  => move towards left (j = 8)
• if(3 > pivot) => NO, STOP. (j = 7 and points to 5)
5. If (i < j) , we swap them
thus array is now {2, 6, 4, 5, 8, 1, 9, 10, 11, 7}
6. Increment i and decrease j. (i = 4, j = 6)
7. Again we start; i = 4 and points to 8 and; j = 6 and points to 9.
8. Eventually, we will get the array as:- {2, 6, 4, 5, 1, 8, 9, 10 ,11, 7}
9. Swap the pivot element with arr[i].
10. Thus we have {2, 6, 4, 5, 1, 7, 9, 10, 11, 8}

This way when PIVOT = 7, all small elements are on the left and greater elements on the right. Repeat this process with the left and right sub parts to sort the complete array.

#### Code

Here is an implementation of the above algorithm:-

.hljs > mark.shcb-loc { background-color: #ddf6ff; }#include<stdio.h>

//a simple function to swap two numbers
void swap(int *i, int *j)
{
int temp = *i;
*i = *j;
*j = temp;
}

// a function to partition the array arr
// having starting index as - start
// and ending index as - end
int partition(int arr[], int start, int end)
{
// we take the pivot to be the last element
// that means all elements smaller
// to it will be on left and larger on right
int pivot = arr[end];

// taking i and j to define the range, we leave the pivot
int i = start;
int j = end-1;

// loop till in range
while(i <= j)
{
// keep moving till the left element is smaller than pivot
while(arr[i] < pivot)
i++;

// keep moving left till right element is larger
while(arr[j] < pivot)
j--;

// we need to swap the left and right
if(i <= j)
{
swap(&arr[i], &arr[j]);
i++;
j--;
}
}

// once partitioned, we need to put the pivot at correct place
swap(&arr[i], &arr[end]);

// return the position of pivot
return i;
}

void performQuickSort(int arr[], int start, int end)
{
//the terminating condition for recursion
if(start < end)
{
// get the partition index
int p = partition(arr, start, end);

// perform quick sort on left sub part
performQuickSort(arr, start, p-1);

// perform quick sort on right sub part
performQuickSort(arr, p+1, end);
}
}

//defining a function to perform merge sort on array arr[] of given size
void quickSort(int arr[], int size)
{
performQuickSort(arr, 0, size-1);
}

// driver program to test the above function
int main(void)
{
int i;
int arr = {2, 6, 4, 10, 8, 1, 9, 5, 3, 7};

quickSort(arr,10);

printf("SORTED array:- ");
for(i = 0; i < 10; i++)
printf("%d ",arr[i]);

return 0;
}


Time Complexity: O(n * \log n)
Space Complexity: O(\log n)

You can also find the code and test cases on Github.

#### You may also like June 26, 2015 - 02:36

In the #recursive sorts, at the last item, where it says “Thus we have {2,6,…,11,7}”, shouldn’t the “7” be an “8”? Great app, btw. June 30, 2015 - 19:55

Thanks for pointing out the type Patrick.
I have corrected it. :)

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More