# Quick Sort

- Quick Sort Algorithm
- Quick Sort Example
- Quick Sort Algorithm Implementation
- Quick Sort Algorithm Complexity

Quick sort is a highly efficient sorting algorithm based on the principle of the divide and conquer algorithm. Quick sort works by partitioning the array into two parts around a selected pivot element. It moves smaller elements to the left side of the pivot and larger elements to the right side. After this, left and right subparts are recursively sorted to sort the whole array. It is called Quick sort because it is around `2`

or `3`

times quicker than common sorting algorithms. Quick sort is widely used for information search and numerical computations inside data structures.

## Quick Sort Algorithm

Let us assume that we have an unsorted array `A[]`

containing `n`

elements. Take two variables, `beg`

& `end`

, then store the index of starting and ending element.

`Partition()`

##### Select the last element(can be any depending on implementation) as the pivot element.

##### Initialize the value of pointer

`i`

to`beg - 1`

so that we can move elements smaller than pivot to starting of the array.##### Iteratively traverse the array and do the following for each element.

##### If the element

`A[i]`

<`pivot`

increment`i`

and swap`A[i]`

with`A[j]`

.##### Swap

`A[i]`

with`A[end]`

to put the pivot element at its correct position.##### Return the index of pivot element.

`QuickSort()`

##### Select the pivot index

`pi`

.##### Partition the array around the pivot index.

##### Recursively sort elements on left side

`arr[beg,...,pi]`

of the pivot element.##### Recursively sort elements on right side

`arr[pi+1,...,end]`

of the pivot element.

## Quick Sort Example

Suppose we have the array: `(6,5,1,4,2,3)`

. We will sort it using the quick sort algorithm.

##### First

`3`

is selected as pivot element, the array is partitioned into two subparts`(1,2)`

- smaller elements, and`(6,5,4)`

- larger elements. And then`3`

is put in its sorted position. The two subarrays formed are then recursively sorted.##### For subarray

`(1,2)`

,`2`

is selected as pivot element and put in the correct position & subarray`(1)`

is formed which is already sorted.##### For subarray

`(6,5,4)`

,`4`

is put in sorted position, and subarray`(6,5)`

is formed, which is then recursively sorted.##### For subarray

`(6,5)`

,`5`

is selected as the pivot and put into the correct position, which gives`(6)`

as the new subarray. Single element subarray`(6)`

is already sorted.##### Finally, we get the sorted array as

`(1, 2, 3, 4, 5, 6)`

.

## Quick Sort Algorithm Implementation

```
#include<bits/stdc++.h>
using namespace std;
int partition(int arr[], int beg, int end) {
// Select the last element as pivot element
int pivot = arr[end];
int i = (beg - 1);
//Move smaller elements to left side and larger on right side
for (int j = beg; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[end]); //Move pivot element to its right position in array
return (i + 1);
}
void quickSort(int arr[], int beg, int end) {
if (beg < end) {
int pi = partition(arr, beg, end);
quickSort(arr, beg, pi - 1); // Recursive Sort element on left side of partition
quickSort(arr, pi + 1, end); // Recursive Sort element on right side of partition
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
quickSort(arr, 0, n - 1); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

## Quick Sort Algorithm Complexity

### Time Complexity

- Average Case

Time taken by Quick Sort is given by the following recurrence relation:

```
T(n) = T(k) + T(n-k-1) + θ(n)
```

`k`

here represents the number of elements smaller/larger than the pivot element.

This result of this recurrence relation gives `T(n) = nLogn`

.The average-case occurs when we get random unevenly balanced partitions. The time complexity is of the order of [Big Theta]: `O(nLogn)`

.

- Worst Case

```
T(n) = T(n-1) + θ(n)
```

The worst-case occurs when the pivot element is always either the largest or smallest element of the array. In this case, all the elements fall in one subarray and maximum `n`

calls have to be made. The worst-case time complexity is [Big O]: O(n^{2}).

- Best Case

```
T(n) = 2T(n/2) + θ(n)
```

The best-case occurs when the selected pivot element is always the middle element or when both the partitions are evenly balanced i.e. difference in size is `1`

or less. The best-case time complexity is [Big Omega]: `O(nLogn)`

.

### Space Complexity

The average-case space complexity for the quick sort algorithm is `O(Logn)`

. It is the space required by the recursion stack. But in the worst-case when sorting an array requires `n`

recursive, the space complexity is `O(n)`

.