Quick Sort Algorithm

Quick Sort Algorithm

Quick Sort is a widely used Divide and Conquer sorting algorithm that is very efficient for large datasets. It works by selecting a "pivot" element from the array and partitioning the other elements into two subarrays, according to whether they are smaller or greater than the pivot. The algorithm then recursively sorts the subarrays. Quick Sort is efficient in practice and is often faster than other O(n log n) algorithms like Merge Sort and Heap Sort due to its smaller hidden constants.

Steps in Quick Sort

Quick Sort follows these basic steps:

1. Pick a Pivot: Select an element from the array to act as a pivot. Different pivot selection strategies exist (e.g., pick the first element, last element, middle element, or a random element).

2. Partitioning: Re-arrange the array so that:

   • All elements smaller than the pivot come before it.
   • All elements greater than the pivot come after it. After this step, the pivot is in its correct position in the sorted array.

3. Recursively Sort Subarrays: Recursively apply the Quick Sort algorithm to the two subarrays (left and right of the pivot) until the entire array is sorted.

Quick Sort Pseudocode

Here is the pseudocode for Quick Sort:

// Function to perform partitioning
int partition(int arr[], int low, int high) {
    // Pivot is selected as the last element of the array
    int pivot = arr[high];
    int i = (low - 1);  // Index of smaller element

    // Traverse through all elements of the array
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;  // Increment index of smaller element
            swap(arr[i], arr[j]);  // Swap the elements
        }
    }
    swap(arr[i + 1], arr[high]);  // Place pivot at the correct position
    return (i + 1);  // Return the index of the pivot
}

// Function to implement Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is the partitioning index, arr[pi] is now in the correct position
        int pi = partition(arr, low, high);

        // Recursively sort the subarrays before and after partition
        quickSort(arr, low, pi - 1);  // Left subarray
        quickSort(arr, pi + 1, high);  // Right subarray
    }
}

Quick Sort Example

Let’s walk through an example to see how Quick Sort works.

Suppose we have the following unsorted array:

[38, 27, 43, 3, 9, 82, 10]

Step 1: Pick a Pivot

We pick the last element of the array as the pivot. In this case, the pivot is 10.

Step 2: Partitioning

We rearrange the array such that elements smaller than 10 come to the left, and elements greater than 10 come to the right. After the partitioning, the array looks like this:

[3, 9, 10, 43, 38, 82, 27]

The pivot 10 is now in its correct sorted position (index 2).

Step 3: Recursively Sort Subarrays

Now, we recursively sort the left and right subarrays:

• Left subarray: [3, 9] (indices 0 to 1)
• Right subarray: [43, 38, 82, 27] (indices 3 to 6)

Sorting Left Subarray [3, 9]:

• Pivot: 9
• Partition: After partitioning, the array becomes [3, 9], and 9 is in the correct position.

Since this subarray has only two elements, it's already sorted.

Sorting Right Subarray [43, 38, 82, 27]:

• Pivot: 27
• Partition: After partitioning, the array becomes [27, 38, 82, 43], and 27 is in the correct position.

Now, we recursively sort the two subarrays:

• Left subarray: [27] (already sorted).
• Right subarray: [38, 82, 43].

Sorting [38, 82, 43]:

• Pivot: 43
• Partition: After partitioning, the array becomes [38, 43, 82], and 43 is in the correct position.

Now, we have two subarrays:

• Left subarray: [38] (already sorted).
• Right subarray: [82] (already sorted).

Final Sorted Array

After all recursive calls are completed, the sorted array looks like this:

[3, 9, 10, 27, 38, 43, 82]

---

Time Complexity of Quick Sort

Quick Sort is known for its efficiency. The time complexity depends on how balanced the partitioning process is.

1. Best and Average Case:

   • If the pivot divides the array into roughly equal halves (balanced partitioning), the algorithm performs logarithmic divisions and processes all elements linearly at each level. Thus, the time complexity in the best and average case is:
   • O(n log n)

2. Worst Case:

   • In the worst case, the pivot may be the smallest or largest element, leading to unbalanced partitioning. This happens when the array is already sorted (or nearly sorted) and results in partitioning only one element at a time.
   • In this case, Quick Sort degenerates to a linear scan with a time complexity of O(n²).

   Worst-case time complexity can be reduced to O(n log n) by choosing a good pivot, such as using the median of three (the first, middle, and last element) as the pivot.

Space Complexity of Quick Sort

1. Space Complexity:

   • Quick Sort is an in-place sorting algorithm, meaning it does not require extra space for storing copies of subarrays. However, it does use O(log n) space due to the recursive stack calls. This is because each recursive call only requires a constant amount of space, and the depth of the recursion tree is proportional to log n.

   Space Complexity: O(log n) in the best case and O(n) in the worst case (for highly unbalanced partitions).

---

Pivot Selection in Quick Sort

The choice of pivot has a significant effect on the performance of Quick Sort:

• First Element as Pivot: In this method, we always choose the first element as the pivot. This can be inefficient if the input is already sorted, as it results in O(n²) time complexity.
• Last Element as Pivot: Similar to the first element method, but choosing the last element as the pivot.
• Random Pivot: Randomly select a pivot. This helps avoid the worst-case scenario and gives an expected time complexity of O(n log n).
• Median of Three: Select the pivot as the median of the first, middle, and last element of the array. This approach helps to achieve better partitioning, improving the performance on already sorted arrays.

---

Advantages of Quick Sort

1. Efficient for Large Data: Quick Sort is generally faster than other O(n log n) algorithms like Merge Sort and Heap Sort, especially for large datasets, due to its smaller constant factors.
2. In-Place Sorting: Quick Sort does not require additional space to store arrays, so it uses O(log n) space.
3. Cache-Friendly: Quick Sort performs well on modern computers because it takes advantage of cache locality (it tends to access contiguous blocks of memory).
4. Average Case: The average case time complexity of Quick Sort is O(n log n), which is very efficient.

---

Disadvantages of Quick Sort

1. Worst-Case Time Complexity: The worst-case time complexity is O(n²), which occurs when the pivot is the smallest or largest element (e.g., in an already sorted array). This can be mitigated by using strategies like median of three for pivot selection.
2. Not Stable: Quick Sort is not stable, meaning that it may change the relative order of equal elements.
3. Recursive Stack: In the worst case, Quick Sort can use O(n) space due to deep recursion, which can cause stack overflow for very large arrays (though this is rare with proper pivot selection).

---

Conclusion

Quick Sort is one of the most efficient sorting algorithms, with an average time complexity of O(n log n). It is widely used because of its in-place sorting nature and excellent performance on large datasets. However, its performance can degrade to O(n²) if poor pivot selection leads to unbalanced partitions. By using strategies like random pivots or median of three, the chances of hitting the worst case can be minimized.