Home | Projects | Notes > Data Structures & Algorithms > Quick Sort: T = O(n logn) , S = O(n)

Quick Sort: T = O(n logn) , S = O(n)

Quick Sort

• A widely used sorting algorithm that employs a divide-and-conquer strategy. It selects a "pivot" element from an array and partitions the other elements into two subarrays, one containing elements less than the pivot and the other containing elements greater than the pivot. This process is recursively applied to the subarrays, effectively sorting the entire array.

• Quick sort has an average time complexity of O(n log n) and often outperforms other sorting algorithms due to its efficient partitioning technique.

• The space complexity of Quick Sort is generally O(log n), where "n" is the number of elements in the array being sorted.

• Quick sort has space complexity of O(n), where "n" is the number of elements in the input array.

Algorithm

1. Input: An array of elements to be sorted.

2. Choose Pivot: Select a pivot element from the array. The pivot can be chosen using various methods, such as selecting the first, last, or middle element.

3. Partitioning: Rearrange the elements in the array such that all elements less than the pivot are moved to its left and all elements greater than the pivot are moved to its right. The pivot element is now in its final sorted position.

4. Recursion: Recursively apply quick sort to the subarrays on the left and right of the pivot. These subarrays are formed by the partitioning step.

5. Combine: No combining step is needed, as the array is already sorted in place after the partitioning and recursive sorting steps.

6. Base Case: The base case for the recursion is when the subarray has only one element or is empty. In such cases, the array is considered sorted.

Pseudo-code

xxxxxxxxxx
15
1
QuickSort(arr, begIdx, endIdx):
2
    if begIdx < endIdx:
3
        pivotIdx = Partition(arr, begIdx, endIdx)
4
        QuickSort(arr, begIdx, pivotIdx - 1)
5
        QuickSort(arr, pivotIdx + 1, endIdx)
6
        
7
Partition(arr, begIdx, endIdx):
8
    pivot = arr[endIdx]
9
    gtIdx = begIdx - 1
10
    for i from lbegIdxow to endIdx-1:
11
        if arr[i] <= pivot:
12
            gtIdx = gtIdx+1
13
            swap(arr[gtIdx], arr[i])
14
    swap(arr[gtIdx+1], arr[endIdx])
15
    return gtIdx+1

Code (C++)

xxxxxxxxxx
52
1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
// Function to partition the array
7
int partition(vector<int>& arr, int begIdx, int endIdx)
8
{
9
    int pivot = arr[endIdx];
10
    int gtIdx = begIdx - 1; // To mark the first element that is greater than the pivot
11
    
12
    for (int i = begIdx; i < endIdx; i++)
13
    {
14
        if (arr[i] <= pivot)
15
        {
16
            gtIdx++;
17
            swap(arr[gtIdx], arr[i]);
18
        }
19
    }
20
    
21
    // At this point, arr[gtIdx] does not contain the first element that is greater
22
    // than the pivot due to the swap operation previously performed. Rather, it should 
23
    // contain the last element that is smaller than the pivot.
24
    swap(arr[gtIdx + 1], arr[endIdx]);
25
    
26
    // Now, the pivot is placed in the index 'greaterIdx + 1'.
27
    return gtIdx + 1;
28
}
29

30
// Quick Sort function
31
void quickSort(vector<int>& arr, int begIdx, int endIdx)
32
{
33
    if (begIdx < endIdx)
34
    {
35
        int pivotIdx = partition(arr, begIdx, endIdx);
36
        quickSort(arr, begIdx, pivotIdx - 1);
37
        quickSort(arr, pivotIdx + 1, endIdx);
38
    }
39
}
40

41
int main(void)
42
{
43
    vector<int> arr = {6, 4, 2, 1, 5, 3};
44
    quickSort(arr, 0, arr.size() - 1);
45
    
46
    for (auto val : arr)
47
        cout << val << " ";
48
    
49
    cout << endl;
50
    
51
    return 0;
52
}

xxxxxxxxxx
1
1
1 2 3 4 5 6

Code (C)

xxxxxxxxxx
54
1
#include <stdio.h>
2

3
// Function to swap two elements
4
void swap(int *a, int *b)
5
{
6
    int temp = *a;
7
    *a = *b;
8
    *b = temp;
9
}
10

11
// Function to partition the array
12
int partition(int arr[], int begIdx, int endIdx)
13
{
14
    int pivot = arr[endIdx];
15
    int gtIdx = begIdx - 1;
16
        
17
    for (int i = begIdx; i < endIdx; i++)
18
    {
19
        if (arr[i] <= pivot)
20
        {
21
            gtIdx++;
22
            swap(&arr[gtIdx], &arr[i]);
23
        }
24
    }
25
    
26
    swap (&arr[gtIdx + 1], &arr[endIdx]);
27
    return gtIdx + 1;
28
}
29

30
// Quick Sort function
31
void quickSort(int arr[], int begIdx, int endIdx)
32
{
33
    if (begIdx < endIdx)
34
    {
35
        int pivotIdx = partition(arr, begIdx, endIdx);
36
        quickSort(arr, begIdx, pivotIdx - 1);
37
        quickSort(arr, pivotIdx + 1, endIdx);
38
    }
39
}
40

41
int main(void)
42
{
43
    int arr[] = {6, 4, 2, 1, 5, 3};
44
    int size = sizeof(arr) / sizeof(arr[0]);
45
    
46
    quickSort(arr, 0, size - 1);
47
    
48
    for (int i = 0; i < size; i++)
49
        printf("%d ", arr[i]);
50
    
51
    puts("");
52
    
53
    return 0;
54
}

xxxxxxxxxx
1
1
1 2 3 4 5 6