DSA Tutorial

🪓 Choose a pivot → 🔀 Partition array → 🔄 Sort subarrays

⚙️ How Quick Sort Works

1. Pick a pivot element from the array.
2. Rearrange the array such that all elements less than the pivot are on the left and greater elements are on the right.
3. Recursively apply the same process to the left and right subarrays.

📘 Step-by-Step Example

Array: [10, 80, 30, 90, 40, 50, 70]

• Select pivot: 50
• Partition: [10, 30, 40] | 50 | [80, 90, 70]
• Recursively sort left: [10, 30, 40] → Pivot: 30 → [10] | 30 | [40]
• Recursively sort right: [80, 90, 70] → Pivot: 70 → [70] | 80, 90
• Final sorted array: [10, 30, 40, 50, 70, 80, 90]

💻 C Code Example

#include <stdio.h>

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 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[] = {10, 80, 30, 90, 40, 50, 70};
    int n = 7;
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}
    

📊 Time Complexity: O(n log n) on average
💾 Space Complexity: O(log n) — Uses recursion stack

✅ Quick Sort is very fast, but its worst-case time complexity is O(n²). It is commonly used for large datasets.