DSA Tutorial

⚙️ 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;
}