📚  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- first element as pivot)

QUICKSORT(A, low, high)
    if low < high then
        pivotIndex ← PARTITION(A, low, high)
        QUICKSORT(A, low, pivotIndex - 1)
        QUICKSORT(A, pivotIndex + 1, high)

PARTITION(A, low, high)
    pivot ← A[low]                // choose first element as pivot
    i ← low + 1
    j ← high

    while true do
        while i ≤ high and A[i] ≤ pivot do
            i ← i + 1
        while j ≥ low and A[j] > pivot do
            j ← j - 1

        if i < j then
            swap A[i] and A[j]
        else
            break

    swap A[low] and A[j]           // place pivot in correct position
    return j                       // return pivot index

Quick Sort Algorithm (Pseudo code-last element as pivot)

QUICKSORT(A, low, high)
    if low < high then
        pivotIndex ← PARTITION(A, low, high)
        QUICKSORT(A, low, pivotIndex - 1)
        QUICKSORT(A, pivotIndex + 1, high)


PARTITION(A, low, high)
    pivot ← A[high]               // choose last element as pivot
    i ← low
    j ← high - 1

    while true do
        while i ≤ high - 1 and A[i] ≤ pivot do
            i ← i + 1
        while j ≥ low and A[j] > pivot do
            j ← j - 1

        if i < j then
            swap A[i] and A[j]
        else
            break

    swap A[i] and A[high]          // place pivot in correct position
    return i                       // return pivot index

---

✨ Example

Initial Array

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

---

Step 1: First Partition (pivot = 8)

• Pivot = 8 (first element).

• Elements ≤ 8 go left, elements > 8 go right.

After partition:

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

Pivot 8 is in its final position (index 5).

---

Step 2: Recurse on Left Part [2, 3, 1, 7, 0]

[2, 3, 1, 7, 0]

• Pivot = 2.

Partition:

• Left side ≤ 2 → [0, 1]

• Right side > 2 → [7, 3]

After partition:

[0, 1]  [2]  [7, 3]

---

Step 3: Recurse on Left Part [0, 1]

[0, 1]

• Pivot = 0.

• Partition: [0] [1]

Sorted result:

[0, 1]

---

Step 4: Recurse on Right Part [7, 3]

[7, 3]

• Pivot = 7.

• Partition: [3] [7] 

Sorted result:

[3, 7]

---

Step 5: Combine Left Side

Now left part [2, 3, 1, 7, 0] is fully sorted:

[0, 1, 2, 3, 7]

---

Step 6: Right Part [10]

Nothing to sort (single element).

---

Final Combined Sorted Array

Now combine everything:

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

---

✅ Final Answer:
The sorted array is:

$$[0, 1, 2, 3, 7, 8, 10]$$

---

 Let’s do a complete step-by-step trace of Quick Sort on the array

$$[8, 4, 7, 3, 10]$$

using the last element (10) as the pivot in each recursive step.

---

✨ Example Initial Array ( last element as pivot)

[8, 4, 7, 3, 10]

---

Step 1: First Partition (pivot = 10)

• Pivot = 10 (last element)

• Compare each element with pivot.

    

i	Element	Comparison	Action
0	8	8 ≤ 10	Stay left
1	4	4 ≤ 10	Stay left
2	7	7 ≤ 10	Stay left
3	3	3 ≤ 10	Stay left

👉 All elements ≤ 10, so the pivot is already the largest.

After partition:

[8, 4, 7, 3, 10]

✅ Pivot 10 is now in correct position (index 4).

Left subarray: [8, 4, 7, 3]
Right subarray: (none)

---

Step 2: Recurse on Left Part [8, 4, 7, 3]

Pivot = 3 (last element)

i	Element	Comparison	Action
0	8	8 > 3	stays right
1	4	4 > 3	stays right
2	7	7 > 3	stays right

No element ≤ 3, so pivot goes to index 0 after swapping with first element.

After partition:

[3, 4, 7, 8, 10]

✅ Pivot 3 is in correct position (index 0).

Left subarray: (none)
Right subarray: [4, 7, 8]

---

Step 3: Recurse on Right Part [4, 7, 8]

Pivot = 8 (last element)

i	Element	Comparison	Action
1	4	4 ≤ 8	Stay left
2	7	7 ≤ 8	Stay left

All ≤ 8, so pivot stays at index 3.

After partition:

[3, 4, 7, 8, 10]

✅ Pivot 8 in correct position (index 3).

Left subarray: [4, 7]
Right subarray: (none)

---

Step 4: Recurse on Left Part [4, 7]

Pivot = 7

i	Element	Comparison	Action
1	4	4 ≤ 7	Stay left

No swaps needed. Pivot stays in correct position (index 2).

After partition:

[3, 4, 7, 8, 10]

✅ Pivot 7 in correct position.

---

Step 5: All Subarrays of Size 1

• [3], [4], [7], [8], [10] — already sorted.

---

✅ Final Sorted Array

[3, 4, 7, 8, 10]

---

🧠 Summary of Recursive Steps

Step	Subarray	Pivot	Pivot Position	Resulting Array
1	[8, 4, 7, 3, 10]	10	4	[8, 4, 7, 3, 10]
2	[8, 4, 7, 3]	3	0	[3, 4, 7, 8, 10]
3	[4, 7, 8]	8	3	[3, 4, 7, 8, 10]
4	[4, 7]	7	2	[3, 4, 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>

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

    for (int i=low; i<high; i++)

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

    

}

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

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

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

    

}

// Function to swap two elements

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

    int temp = *a;

    *a = *b;

    *b = temp;

}

// Partition function (first element as pivot)

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

    int pivot = arr[low];  // choose first element as pivot

    int i = low + 1;

    int j = high;

    while (1) {

        // move i forward while elements are <= pivot

        while (i <= high && arr[i] <= pivot) {

            i++;

        }

        // move j backward while elements are > pivot

        while (j >= low && arr[j] > pivot) {

            j--;

        }

        if (i < j) {

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

        } else {

            break;

        }

    }

    // place pivot in correct position

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

    

    return j;  // return pivot index

}

// Quicksort function

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

    if (low < high) {

        int pivotIndex = partition(arr, low, high);

        printArray(arr,low,pivotIndex);

        printf("\t*%d\t",arr[pivotIndex]);

        printArray(arr,pivotIndex+1,high+1);

        printf("\n");

        quicksort(arr, low, pivotIndex - 1);

        quicksort(arr, pivotIndex + 1, high);

    }

}

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,0, n);

    printf("\n");

    quicksort(arr,0,n-1);

    printf("Sorted array: ");

    printArray(arr,0, n);

    printf("\n");

    return 0;

}

Output

Enter the number of elements 

7

Enter the array elements

8 3 1 7 0 10 2

Original array: 8 3 1 7 0 10 2 

2 3 1 7 0       *8      10 

1 0     *2      7 3 

0       *1

3       *7

Sorted array: 0 1 2 3 7 8 10 

C Program - Quick Sort(last element as pivot)

#include <stdio.h>

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

    for (int i=low; i<high; i++)

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

    

}

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

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

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

    

}

// Function to swap two elements

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

    int temp = *a;

    *a = *b;

    *b = temp;

}

// Partition function (first element as pivot)

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

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

    int i = low;             // start pointer

    int j = high - 1;        // end pointer (just before pivot)

    while (1) {

        // Move i to the right until arr[i] > pivot

        while (i <= high - 1 && arr[i] <= pivot)

            i++;

        // Move j to the left until arr[j] < pivot

        while (j >= low && arr[j] > pivot)

            j--;

        // If pointers cross, break

        if (i >= j)

            break;

        // Swap elements on wrong sides

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

    }

    // Place pivot in correct position

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

    return i;  // return pivot position

}

// Quicksort function

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

    if (low < high) {

        int pivotIndex = partition(arr, low, high);

        printArray(arr,low,pivotIndex);

        printf("\t*%d\t",arr[pivotIndex]);

        printArray(arr,pivotIndex+1,high+1);

        printf("\n");

        quicksort(arr, low, pivotIndex - 1);

        quicksort(arr, pivotIndex + 1, high);

    }

}

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,0, n);

    printf("\n");

    quicksort(arr,0,n-1);

    printf("Sorted array: ");

    printArray(arr,0, n);

    printf("\n");

    return 0;

}

Output

Enter the number of elements 

7

Enter the array elements

8 3 1 10 0 7 2

Original array: 8 3 1 10 0 7 2 

0 1     *2      10 8 7 3 

0       *1

        *3      8 7 10 

8 7     *10

        *7      8 

Sorted array: 0 1 2 3 7 8 10