Coding Exercise: Quick Sort Using Recursion

Sort using partition: pick pivot → partition → recurse left/right.

Example: [64,34,25,12,22,11,90] → [11,12,22,25,34,64,90]

Problem Statement

Input: Unsorted array

Output: Sorted array (ascending)

Average: O(n log n), Worst: O(n²)

Lomuto Partition Scheme

1. Choose last element as pivot

2. Partition: smaller→left, larger→right

3. Recurse: left subarray, right subarray

Complete Implementation

              
            
C++

          Quick sort with Lomuto partition
        
#include <iostream>
using namespace std;

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);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;
    quickSort(arr, 0, n-1);
    cout << "Sorted: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Quick Sort Steps: [50, 30, 80, 10, 90, 40]

              
            
TEXT

          Partition visualization
        
Initial: [50,30,80,10,90,40] pivot=40
↓ Partition → [30,10,40,80,90,50]
                 ↓    ↓
           [30,10]  [80,90,50]
            ↓         ↓
         [10,30]  [50,80,90]
Result: [10,30,40,50,80,90]

Test Cases

              
TEXT

          Expected outputs
        
[64,34,25,12,22,11,90] → [11,12,22,25,34,64,90]
[5,2,4,7,1,3] → [1,2,3,4,5,7]
[1] → [1]

Complexity Analysis

Average: O(n log n)

Worst: O(n²) - sorted/reverse sorted

Space: O(log n) - recursion stack

Practice Variations

1. Hoare partition scheme

2. Randomized pivot selection

3. 3-way quicksort

Conclusion

Mastered quicksort! In-place, fast average case.

Next: Tree traversals or backtracking.