📚  Quick Sort

Quick Sort is a divide-and-conquer algorithm.
It picks an element as a pivot and partitions the given array around the pivot such that:

• Elements less than the pivot go to its left,

• Elements greater than the pivot go to its right.

After partitioning, it recursively sorts the left and right parts.

---

⚡ Steps in Quick Sort

1. Choose a Pivot:
   (You can choose first element, last element, middle element, or use a random pivot.)

2. Partitioning:
   Rearrange the array such that:

   • All elements smaller than pivot come before it,

   • All elements greater come after it.

3. Recursively apply the same steps to left and right sub-arrays.

---

Quick Sort Algorithm (Pseudo code)

QUICKSORT(arr, low, high)
    if low < high
        pivotIndex = PARTITION(arr, low, high)
        QUICKSORT(arr, low, pivotIndex - 1)
        QUICKSORT(arr, pivotIndex + 1, high)

PARTITION(arr, low, high)
    pivot = arr[high]   // Choosing last element as pivot
    i = low - 1
    for j = low to high-1
        if arr[j] <= pivot
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i+1] and arr[high]
    return i+1   // New pivot index

---

✨ Example

Sort: [8, 3, 1, 7, 0, 10, 2]

1. Choose pivot 2 (last element).

2. Partition: elements <=2 on left, >2 on right → [1, 0, 2, 7, 8, 10, 3]

3. Recursive calls:

   • Left: [1, 0] → pivot 0 → [0, 1]

   • Right: [7,8,10,3] → pivot 3 → [3,7,10,8]

   • Continue until fully sorted: [0,1,2,3,7,8,10]

---

🚀 Features of Quick Sort

Property	Value
Time Complexity	Best: O(n log n)
	Average: O(n log n)
	Worst: O(n²)
Space Complexity	O(log n) (due to recursion)
Type	In-place, Not Stable

C Program - Quick Sort

#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

// Partition function

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // Choosing last element as pivot

    int i = low - 1;       // Index of smaller element

    

    for (int j = low; j <= high - 1; j++) {

        if (arr[j] <= pivot) {

            i++;

            swap(&arr[i],&arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[high]); // Place pivot at correct position

    return (i + 1);

}

// Quick Sort function

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high); // pi is partitioning index

        quickSort(arr, low, pi - 1);  // Sort elements before partition

        quickSort(arr, pi + 1, high); // Sort elements after partition

    }

}

void printArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

void readArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        scanf("%d", &arr[i]);

    

}

int main() {

    int arr[50] ;

    int n;

    

    printf("Enter the number of elements \n");

    scanf("%d",&n);

    printf("Enter the array elements\n");

    readArray(arr,n);

    

    printf("Original array: ");

    printArray(arr, n);

    quickSort(arr,0,n-1);

    printf("Sorted array: ");

    printArray(arr, n);

    return 0;

}

Output

Enter the number of elements 

10

Enter the array elements

5 8 2 4 0 1 8 9 7 3

Original array: 5 8 2 4 0 1 8 9 7 3 

Sorted array: 0 1 2 3 4 5 7 8 8 9