Quick Sort - Visualization

Sorting

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Input Array Sorted Output Description
[10, 5, 2, 3, 7] [2, 3, 5, 7, 10] Normal case with unsorted distinct integers
[5, 5, 5, 5] [5, 5, 5, 5] All elements are the same, already sorted
[9, 8, 7, 6, 5] [5, 6, 7, 8, 9] Reverse sorted input
[1] [1] Single-element array is already sorted
[] [] Empty array, nothing to sort
[3, -1, 0, 2] [-1, 0, 2, 3] Includes negative numbers
[100, 10, 1000, 1] [1, 10, 100, 1000] Wide range of values

Solution❯

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

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n log n)In the best case, the pivot divides the array into two equal halves at every step. This results in log n levels of recursion, with each level doing O(n) work for partitioning.
Average CaseO(n log n)On average, the pivot splits the array into reasonably balanced parts. Each level of recursion requires O(n) operations, and there are log n such levels.
Worst CaseO(n^2)In the worst case (e.g., when the pivot is always the smallest or largest element), the partition results in one subarray of size n−1 and one of size 0, leading to n levels of recursion and O(n) work per level.

Space Complexity❯

O(log n)

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


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...