We will discuss the Quick Sort Algorithm, pseudo code, Code implementation of Quick Sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Quick Sort.

## Table of Contents

## 1. What is Quick Sort Algorithm?

**Quick Sort** is also the divide-and-conquer strategy of sorting a list of elements like merge sort.

**Quick Sort** is a highly efficient sorting algorithm and is based on partitioning an array into smaller sub-arrays.

It works by selecting a ‘*pivot*‘ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

The worst case of quick sort occurs when the given elements are already sorted or almost sorted.

### 1.1 Explanation of Quick Sort

**Choose a pivot**: This can be any element from the array.**Partitioning**: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.**Recursively apply the above steps**to the sub-arrays of elements with smaller and greater values.

## 2. Pseudocode for Quick Sort

QUICKSORT(S, P, r)1. If p < r 2. then q <- PARTITION(S, p, r) 3. QUICKSORT(S, p, q-1) 4. QUICKSORT(S, q+1, r)

### 2.1 Pseudocode for Partition

PARTITION(S, p, r)1. x <- S[r] 2. i <- p-1 3. for j <- p to r-1 4. do if S[j] <= x 5. then i <- i+1 6. swap S[i] <-> S[j] 7. swap S[i+1] <-> S[r] 8. return i+1

## 3. Recurrence Relation of Quick Sort

### 3.1 Recurrence Relation in Worst Case

The ** worst case of quick sort** occurs when the pivot we picked turns out to be the least element of the array to be sorted, in every step (i.e. in every recursive call).

A similar situation will also occur if the pivot happens to be the largest element of the array to be sorted.

Then ** Recurrence Relation of Quick Sort in the worst case** is

(1)

### 3.2 Recurrence Relation in Best Case

The ** best case of quick sort** occurs when the pivot we picked happens to divide the array into two almost equal parts, in every step.

Thus, we have *k = n/2* and *n − k = n/2* for the original array of size *n.*

Then ** Recurrence Relation of Quick Sort in the best case** is

(2)

## 4. Code Implementation of Quick Sort

### 4.1 Quick Sort in C

#include <stdio.h> void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf("Sorted array: \n"); printArray(arr, n); return 0; }

#### 4.1.1 Line-by-Line Explanation of Quick Sort

**Partition Function**:*pivot = arr[high]*: Choose the last element as the pivot.*i = low – 1*: Initialize the index of the smaller element.- Loop through the array, comparing each element with the pivot.
- If an element is smaller than the pivot, increment the index of the smaller element and swap the current element with the element at the smaller index.
- After the loop, swap the pivot element with the element at the index
*i + 1*to place the pivot in the correct sorted position.

**Quick Sort Function**:- Recursively call the quick sort on the sub-arrays formed by partitioning the array around the pivot.

This method ensures that the *array is sorted in-place with an average time complexity of O(n log n)*

### 4.2 Quick Sort in C++

#include <iostream> using namespace std; void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); cout << "Sorted array: \n"; printArray(arr, n); return 0; }

### 4.3 Quick Sort in Java

public class QuickSort { int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } void sort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); sort(arr, low, pi - 1); sort(arr, pi + 1, high); } } static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72}; int n = arr.length; QuickSort ob = new QuickSort(); ob.sort(arr, 0, n - 1); System.out.println("Sorted array:"); printArray(arr); } }

### 4.4 Quick Sort in JavaScript

function swap(arr, i, j) { const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } function quickSort(arr, low, high) { if (low < high) { const pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } const arr = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72]; quickSort(arr, 0, arr.length - 1); console.log("Sorted array:", arr);

### 4.5 Quick Sort in Python

def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quick_sort(arr, low, high): if low < high: pi = partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high) arr = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72] quick_sort(arr, 0, len(arr) - 1) print("Sorted array:", arr)

## 5. Advantages of Quick Sort

**Efficiency**: Quick Sort is very efficient for large datasets. It has an average time complexity of*O(n log n)***In-place Sorting**: It requires only a small, constant amount of additional storage space.**Cache Performance**: It has excellent cache performance due to its in-place partitioning.

## 6. Disadvantages of Quick Sort

**Worst-case Complexity**: The worst-case time complexity is*O(n*, which can occur if the pivot selection is poor.^{2})**Stability**: Quick sort is not a stable sort. Equal elements might not preserve their relative order.

## 7. Time and Space Complexity of Quick Sort

Time Complexity | |

Worst Case | O(n^{2}) |

Best Case | O(n log n) |

Average Case | O(n log n) |

Space Complexity | |

Worst Case | O(1) |

## 8. Applications of Quick Sort

Quick Sort is implemented when

- the programming language is good for recursion
- time complexity matters
- space complexity matters

*FAQs*

*FAQs*

### What is Quick Sort?

Quicksort is also the divide-and-conquer strategy of sorting a list of elements like merge sort.

Quick sort is a highly efficient sorting algorithm and is based on partitioning an array into smaller sub-arrays.

It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

### What are the advantages of Quick Sort?

Quick Sort is very efficient for large datasets. It has an average time complexity of *O(n log n)*

It requires only a small, constant amount of additional storage space.

It has excellent cache performance due to its in-place partitioning.

### What are the disadvantages of Quick Sort?

Quick sort is not a stable sort. Equal elements might not preserve their relative order.

The worst-case time complexity is *O(n ^{2})*, which can occur if the pivot selection is poor.