Quick Sort Algorithm with explanation

Quick Sort is a very popular sorting algorithm also known as partition exchange sort. Quick sort follows divide-and-conquer strategy to sort an array elements. In this algorithm first we select the pivot element. This pivot element can be selected either the left most element or right most element.

After selecting pivot element, first divide an unsorted array into two smaller sub-arrays on the basic of pivot element and then further sub-array if possible. Elements of the Left sub arrays will be lesser than pivot element and the element in the right subarray will be greater than pivot element.

Quick Sort algorithm was developed by C. A. R. Hoare which is a widely used sorting algorithm to sort the elements of a list. In the average case, Quick Sort makes O(n log n) comparisons to sort an array of n elements. And in the worst case, it has a quadratic running time O(n²).

• Quick sort is a recursive algorithm that follows a divide-and-conquer strategy.
• The time complexity of the Quick Sort algorithm is O(nlogn) in the average case.
• The time complexity of the Quick Sort algorithm is O(n²) in the worst case.
• Quick Sort is an in-place sorting algorithm it means it takes an only a constant amount of memory to perform the sorting algorithm.
• Quick Sort is often the efficient sorting algorithm that is used by most of the language libraries to perform sorting.

What is Quick Sort Algorithm ?

Quick Sort is a fast and popular sorting algorithm used to arrange elements in order. It works by choosing a pivot element from the array and then dividing the array into two parts: one part has elements smaller than the pivot, and the other part has elements greater than the pivot. After dividing, Quick Sort is applied recursively on both parts, meaning it repeats the same process for the smaller and larger parts until the whole array is sorted. The main idea is to put each element in its correct position relative to the pivot, which makes the array gradually get sorted. Quick Sort is very efficient for large datasets because it sorts faster than simple methods like Bubble Sort or Insertion Sort.

However, its speed depends on how the pivot is chosen, a good pivot can make it very fast, while a bad pivot can make it slower. Overall, Quick Sort is widely used because it sorts arrays quickly and works well for most practical cases.

Here are the steps of the quick sort algorithm

1. First Choose a Pivot element from the Array. Pivot element will be either the first element or last element of the array.
2. After selecting Pivot element we have to Partition the array into two sub-arrays. One sub-array will contain the elements less than the pivot, and another sub array will contain the elements greater than the pivot.
3. To do this, you have to maintain two pointers. One Pointer will be at the start and another pointer will be at the end of the array. Move the start pointer towards the end of the array until you find an element greater than the pivot. Similarly, move the end pointer towards the start of the array until you find an element less than the pivot. Swap these two elements and continue until the start pointer is greater than or equal to the end pointer.
4. Recursively sort the two sub-arrays created. This can be done by calling the quick sort function on each sub-array.
5. Concatenate the sorted sub-arrays and return the resulting array.

Detailed explanation of Quick sort with example

Lets take an array arr = [10,5,12,8,2,11,17] that need to be sorted using quick sort.

[10,5,12,8,2,11,17]

Step 1: First we will choose a pivot element. Pivot element can be either first one or the last one.

Here we are choosing the first element of the array as the pivot, which is 10.

Step 2: Partition the array

After selecting the pivot array, we will partition the array into two sub-array. One sub array will contain elements less than or equal to the pivot, and another sub array will contain elements greater than the pivot. To do this, we are taking two pointers i and j.

[10,5,12,8,2,11,17]
 ↑  i           j

Pivot = 10, i = 0, arr[i] = 5, j=6 and arr[j] = 17

Now i will move towards right and j will move towards left and will match the value at i index with pivot and value of j index with pivot. If the element at i index is smaller than pivot value then i will increase by 1 and move towards right. Similarly if element at j will be greater than pivot element then j will be increase by 1 and will move towards left.

Now we have to keep in mind, when the element at i index is greater than pivot then we have to stop there. Similarly if the element at j index is smaller than pivot then we have to stop.

Lets back to our example:

Pivot = 10, Value at arr[i] = 5, i=1 which is smaller than pivot, will increase i by one and move right.

[10,5,12,8,2,11,17]
 ↑     i         j

Pivot = 10, Value at arr[i] = 12, i=2 which is greater than pivot, will stop here. Here we compare arr[j] = 17, j=6 with pivot, pivot is smaller then decrement in j by 1. so now j is 5.

[10,5,12,8,2,11,17]
 ↑     i     j

Again arr[j] = 11 (j=5), greater then pivot, decrease j by 1.

[10,5,12,8,2,11,17]
 ↑     i   j

Again arr[j] = 2 (j=4), Here 2 is smaller than pivot. So we will perform swapping between arr[i] and arr[j]. Pivot will be at the same place. So after swapping array will look like

[10,5,2,8,12,11,17]
 ↑    i    j

Again i will move towards right and stop at 12 because 12 is greater than pivot element. And j will start moving towards left and stop at 8 because 8 is smaller than Pivot element. And also i become greater than j.

[10,5,2,8,12,11,17]
 ↑      j  i

Here swapping will be done between pivot and arr[j]=8. So after swapping array will look like

[8,5,2,10,12,11,17]

Here you can see in first pass all the element in left of pivot is smaller than pivot. And all the element right of pivot is greater than pivot.

Here array will broken into two sub array. Sub-array 1 will be [8,5,2] and Sub array 2 will be [12,11,17]. Again same process will apply on the above two sub array. Once array is broken in sub array, then conquer will be happen to form sorted array again.

Algorithm of quick sort

Quick Sort Pivot Algorithm

Step 1 – Initialize an array arr
Step 2 − Choose the First element as a pivot element
Step 3 − Take two pointers l and r. Where l is pointing to left most element excluding pivot and r is pointing to the right most element.
Step 4 − Move the left pointer l towards right until it reached at the element that is greater than or equal to the pivot element. If l pointer reached at that element stop there.
Step 5 − Move the right pointer r to the left until it points to an element that is lesser than or equal to the pivot element. If this condition matched just stop there.
Step 6 − Now swap the left pointer element with the right pointer element.
Step 7 − Repeat the above step(4-6) util left pointer become greater than right pointer.
Step 8 – If left pointer become greater than right pointer, now swap the pivot element with right pointer element.
Step 9 – Here Pivot element is now at sorted position.

Pseudo Code of Quick Sort

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);  // Get the pivot index
        quick_sort(arr, low, pivot - 1);  // Sort the left partition
        quick_sort(arr, pivot + 1, high);  // Sort the right partition
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // Choose the first element as the pivot
    int left = low + 1;
    int right = high;

    while (1) {
        // Move left pointer to the right until we find an element that is greater than or equal to the pivot
        while (left <= right && arr[left] < pivot) {
            left++;
        }

        // Move right pointer to the left until we find an element that is less than or equal to the pivot
        while (left <= right && arr[right] > pivot) {
            right--;
        }

        if (left <= right) {
            // Swap the elements at left and right pointers
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        } else {
            // Swap the pivot with the element at right pointer
            int temp = arr[low];
            arr[low] = arr[right];
            arr[right] = temp;
            return right;  // Return the pivot index
        }
    }
}

Quick Sort Program in C

#include <stdio.h>
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int arr[], int l, int r) {
    int pivot = arr[l];
    int i = l + 1;
    int j = r;
    while (1) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(&arr[i], &arr[j]);
        } else {
            break;
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

void quicksort(int arr[], int l, int r) {
    if (l < r) {
        int pi = partition(arr, l, r);
        quicksort(arr, l, pi - 1);
        quicksort(arr, pi + 1, r);
    }
}

int main() {
    int arr[100],i,j,n,key;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    quicksort(arr, 0, n - 1);
    printf("\nSorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d \t", arr[i]);
    }
    return 0;
}

Output:

Enter the number of elements you want to sort:
6
Now enter the 6 elements you want to sort: 
23
11
12
78
99
1
before sorting:
23      11      12      78      99      1 
Sorted array: 
1       11      12      23      78      99 

Explanation of Code

1. Including the library

#include <stdio.h>

This line includes the standard input/output library, which allows the program to use printf() and scanf() functions for displaying output and taking input from the user.

2. Swap Function

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

The function swap swaps the values of two numbers. The *x and *y are pointers that point to the numbers we want to swap. A temporary variable temp is used to hold one number for a short time while the swap is done.

3. Partition Function

int partition(int arr[], int l, int r) {
    int pivot = arr[l];
    int i = l + 1;
    int j = r;
    while (1) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(&arr[i], &arr[j]);
        } else {
            break;
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

The function partition picks a pivot and arranges the array so that smaller numbers go to the left of the pivot and larger numbers go to the right. The first element is chosen as the pivot. One pointer i starts just after the pivot, and another pointer j starts at the end of the array. Two loops move i forward and j backward to find numbers that are on the wrong side. If i is less than or equal to j, the numbers at i and j are swapped. When i and j cross, the pivot is swapped with arr[j] to put it in the correct position. The function then returns j, the pivot’s final position, for further sorting.

4. Quicksort Function

void quicksort(int arr[], int l, int r) {
    if (l < r) {
        int pi = partition(arr, l, r);
        quicksort(arr, l, pi - 1);
        quicksort(arr, pi + 1, r);
    }
}

The function quicksort sorts an array using Quick Sort in a recursive way. If the array has more than one element (l < r), it calls the partition() function to divide the array and find the pivot index pi. Then, it sorts the left part of the array (from l to pi-1) and the right part (from pi+1 to r) by calling itself again. This process continues until the whole array is sorted.

5. Main Function

int main() {
    int arr[100],i,j,n,key;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    quicksort(arr, 0, n - 1);
    printf("\nSorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d \t", arr[i]);
    }
    return 0;
}

The main() first creates an array arr[100] to store numbers and some variables like i, j, and n. It asks the user how many numbers they want to enter and stores that number in n. Then, using a loop, it takes n numbers from the user and saves them one by one in the array. Before sorting, it prints the array so we can see the numbers as entered. Next, it calls the quicksort(arr, 0, n-1) function, which sorts the array using Quick Sort by dividing it with a pivot and arranging smaller numbers to the left and larger numbers to the right, repeating this process for all parts until the array is fully sorted. After sorting, it prints the sorted array, and finally, the program ends by returning 0 to show it ran successfully.

Time & Space complexity of Quick Sort

Time Complexity

Case	Time Complexity
Best-case performance	O(n log n)
Average performance	O(n log n)
Worst-case performance	O(n²)

Space Complexity

Type	Space Complexity
In-place (array itself)	O(1)
Recursive call stack (average)	O(log n)
Recursive call stack (worst)	O(n)

Advantage of Quick Sort

1. Very fast for large datasets in most cases.
2. Works well in memory because it sorts in-place (doesn’t need extra large arrays).
3. Simple to implement recursively.
4. Efficient for average-case performance (O(n log n)).

Disadvantage of Quick Sort

1. It can be slow (O(n²)) if the pivot is not chosen well.
2. Equal numbers may not stay in their original order.
3. Using recursion can take extra memory, which can be a problem for very big arrays.

Conclusion

Quick Sort is a fast and efficient sorting algorithm that works by picking a pivot element and arranging the array so that smaller elements go to the left of the pivot and larger elements go to the right. This process is repeated recursively for all parts of the array until everything is sorted. Its average performance is very good (O(n log n)), and it sorts in-place, so it doesn’t need extra large memory. However, if the pivot is chosen poorly, it can become slow (O(n²)), and it is not stable, meaning equal elements may change their original order. Overall, Quick Sort is widely used because it is simple, fast, and works efficiently for most real-world data.