*2K*

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:-

- Choose a pivot element (it can be any random element in array)
- 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)`

- Now we have the left sub-array of
`(small numbers)`

and the right sub-array`(large numbers)`

- Repeat steps 1 and 2 recursively on both the sub-arrays until we are left with just single elements.
- 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:-

```
# choose pivot
swap a[1, rand(1, n)]
# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], 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]
```

Code language: PHP (php)

*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.- PIVOT = 7 or arr[10]
- Now we apply the iteration in the range 0-9 ,
**leaving the pivot**. - 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)**

- 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)**

- If (i < j) , we swap them

thus array is now`{2, 6, 4,`

**5**, 8, 1, 9,**10**, 11, 7} - Increment
**i**and decrease**j**. (i = 4, j = 6) - Again we start;
**i = 4 and points to 8**and;**j = 6 and points to 9**. - Eventually, we will get the array as:-
`{2, 6, 4, 5,`

**1**,**8**, 9, 10 ,11, 7} - Swap the pivot element with
**arr[i].** - 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:-

```
#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[10] = {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;
}
```

Code language: C++ (cpp)

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

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

## 2 comments

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.

Thanks for pointing out the type Patrick.

I have corrected it. :)

Comments are closed.