Quick Sort

Given an array of integers, your task is to sort the array in ascending order using the Quick Sort algorithm.

• Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
• The process is applied recursively to the sub-arrays, resulting in a sorted array.

Understanding the Problem

We are given an array of numbers, and we want to sort them in ascending order. Our goal is to use the Quick Sort algorithm — a popular and efficient sorting technique.

Quick Sort follows a divide-and-conquer strategy, which means it breaks the problem into smaller parts, solves them individually, and combines the results.

How We'll Solve It

Let’s solve this step by step:

1. Select a Pivot: Pick an element from the array. We’ll choose the last element as our pivot.
2. Partitioning: Rearrange the array so that:
   • All elements smaller than the pivot go to the left.
   • All elements greater go to the right.
3. Recursive Sorting: Apply the same steps on the left and right parts of the array (excluding the pivot, which is already in the correct position).
4. Base Case: If a subarray has 0 or 1 element, it’s already sorted — we stop recursion there.

Step-by-Step Example

Input Array: [8, 4, 7, 3, 10, 2]

1. Choose pivot = 2 (last element).
2. We compare each element with the pivot:
   • None are less than 2, so no swaps happen during comparison.
   • Finally, swap pivot 2 with the first element → [2, 4, 7, 3, 10, 8]
3. Pivot 2 is now at index 0. Now we recursively sort:
   • Left part: [] → Already sorted
   • Right part: [4, 7, 3, 10, 8]
4. On [4, 7, 3, 10, 8], pick pivot = 8:
   • Partition so that left = [4, 7, 3], right = [10]
   • Place pivot 8 at correct position → [4, 7, 3, 8, 10]
5. Continue sorting [4, 7, 3] → pick pivot = 3:
   • Partition → [3, 7, 4]
   • Recursively sort [7, 4] → pivot = 4 → result: [4, 7]

Final Sorted Array: [2, 3, 4, 7, 8, 10]

Edge Cases and Intuitive Handling

Case 1 - Mixed Elements (Normal Case)

• Input: [6, 2, 8, 4, 10]
• Process: Quick Sort proceeds by choosing pivots and dividing the array into left and right parts.
• Output: [2, 4, 6, 8, 10]

Case 2 - Already Sorted Array

• Input: [1, 2, 3, 4, 5]
• Insight: If we always pick the last element as pivot, it becomes the largest each time, leading to skewed recursion — which is inefficient (O(n²)).
• Output: [1, 2, 3, 4, 5]

Case 3 - Reverse Sorted Array

• Input: [5, 4, 3, 2, 1]
• Explanation: Similar to the sorted case, the pivot selection leads to poor performance if not handled wisely.
• Output: [1, 2, 3, 4, 5]

Case 4 - All Elements Equal

• Input: [7, 7, 7, 7]
• Behavior: All comparisons succeed, but no actual movement happens. The array remains the same.
• Output: [7, 7, 7, 7]

Case 5 - Single Element

• Input: [3]
• Explanation: Base case: No sorting needed, it's already sorted.
• Output: [3]

Case 6 - Empty Array

• Input: []
• Explanation: An empty array is trivially sorted.
• Output: []

1. Select a pivot element from the array (commonly the last element).
2. Partition the array so that all elements less than the pivot are on its left, and all greater are on its right.
3. Recursively apply the same process to the subarrays on the left and right of the pivot.
4. Repeat until the base case is reached (subarray has one or no elements).
5. The array is now sorted in place without using additional memory.

#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;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[high]);
    return i;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

#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;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[high]);
    return i;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array is: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    quick_sort(arr)
    print("Sorted array is:", arr)

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        int temp = arr[i];
        arr[i] = arr[high];
        arr[high] = temp;
        return i;
    }

    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.print("Sorted array is: ");
        for (int num : arr) System.out.print(num + " ");
    }
}

function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        const p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
    return arr;
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low;
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[high]] = [arr[high], arr[i]];
    return i;
}

const arr = [6, 3, 8, 2, 7, 4];
quickSort(arr);
console.log("Sorted array is:", arr);

package main

import (
    "fmt"
)

func quickSort(arr []int, low, high int) {
    if low < high {
        p := partition(arr, low, high)
        quickSort(arr, low, p-1)
        quickSort(arr, p+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[high] = arr[high], arr[i]
    return i
}

func main() {
    arr := []int{6, 3, 8, 2, 7, 4}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println("Sorted array is:", arr)
}

fn quick_sort(arr: &mut [i32]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }
    let pivot_index = partition(arr);
    quick_sort(&mut arr[0..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}

fn partition(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let pivot = arr[len - 1];
    let mut i = 0;
    for j in 0..len - 1 {
        if arr[j] < pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, len - 1);
    i
}

fn main() {
    let mut arr = [6, 3, 8, 2, 7, 4];
    quick_sort(&mut arr);
    println!("Sorted array is: {:?}", arr);
}

fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val p = partition(arr, low, high)
        quickSort(arr, low, p - 1)
        quickSort(arr, p + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low
    for (j in low until high) {
        if (arr[j] < pivot) {
            arr[i] = arr[j].also { arr[j] = arr[i] }
            i++
        }
    }
    arr[i] = arr[high].also { arr[high] = arr[i] }
    return i
}

fun main() {
    val arr = intArrayOf(6, 3, 8, 2, 7, 4)
    quickSort(arr, 0, arr.size - 1)
    println("Sorted array is: ${arr.joinToString(" ")}")
}

func quickSort(_ arr: inout [Int], low: Int, high: Int) {
    if low < high {
        let p = partition(&arr, low: low, high: high)
        quickSort(&arr, low: low, high: p - 1)
        quickSort(&arr, low: p + 1, high: high)
    }
}

func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
    let pivot = arr[high]
    var i = low
    for j in low..<high {
        if arr[j] < pivot {
            arr.swapAt(i, j)
            i += 1
        }
    }
    arr.swapAt(i, high)
    return i
}

var arr = [6, 3, 8, 2, 7, 4]
quickSort(&arr, low: 0, high: arr.count - 1)
print("Sorted array is:", arr)

function quickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
    if (low < high) {
        const p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
    return arr;
}

function partition(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let i = low;
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[high]] = [arr[high], arr[i]];
    return i;
}

const arr: number[] = [6, 3, 8, 2, 7, 4];
quickSort(arr);
console.log("Sorted array is:", arr);

Time complexity

Space complexity

O(log n)

The algorithm is in-place and does not use extra space for arrays, but the recursive calls use stack space. In the best/average case, the depth of the recursion is O(log n). In the worst case, it could be O(n) if not optimized with tail recursion.