Sorting Algorithms — Quick Sort

Hi everyone! Welcome to my article on Sorting Algorithms part 6. In this blog, we’ll explore a most commonly used sorting algorithm; Quick Sort. Let’s dive in!

If you want to know the basics of Sorting Algorithms, you can check out my article on Sorting Algorithms part 1 — Introduction to Sorting Algorithms.

Concept

Quick Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot. This process is then applied recursively to the sub-arrays.

Steps

1. Choose a Pivot: Select an element from the array to be the pivot. Various strategies can be used, such as picking the first element, the last element, the middle element, or a random element.
2. Partition: Rearrange the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it. The pivot is now in its correct position.
3. Recursion: Recursively apply the above steps to the sub-arrays of elements less than and greater than the pivot.

Implementation

Here’s a simple Java implementation of Quick Sort:

public class QuickSort {

    // Method to perform Quick Sort
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pi = partition(array, low, high);

            // Recursively sort elements before and after partition
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    // Method to partition the array
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high]; // Choosing the last element as the pivot
        int i = (low - 1); // Index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (array[j] <= pivot) {
                i++;

                // Swap array[i] and array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // Swap array[i + 1] and array[high] (or pivot)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

    // Main method to test the Quick Sort
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};

        System.out.println("Unsorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();

        // Sort the array using Quick Sort
        quickSort(array, 0, array.length - 1);

        System.out.println("Sorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

Explanation

1. Partition Function: The partition method selects the last element as the pivot and rearranges the array so that all elements less than or equal to the pivot come before it, and all elements greater than the pivot come after it. It returns the index of the pivot element after partitioning.
2. Quick Sort Function: The quickSort method recursively sorts the elements before and after the pivot by calling itself with updated indices.
3. Main Method: The main method initializes an array, prints it, sorts it using Quick Sort, and then prints the sorted array.

Complexity of Quick Sort

Time Complexity

1. Best Case: O(nlog⁡n)

• The best case occurs when the pivot divides the array into two equal halves at each step.

2. Average Case: O(nlog⁡n)

• On average, Quick Sort performs well with a time complexity of O(nlog⁡n).

3. Worst Case: O(n²)

• The worst case occurs when the pivot is the smallest or largest element, leading to unbalanced partitions. This can be mitigated by using random pivots or the median-of-three method.

Space Complexity: O(log⁡n)

• Quick Sort is an in-place sorting algorithm, meaning it requires a constant amount of additional memory space for the partitioning process.
• The recursive calls add an additional space complexity of O(log⁡n) for the call stack in the average and best cases, but it can be O(n) in the worst case.

Summary

Quick Sort is an efficient and popular sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element, partitions the array around the pivot, and recursively sorts the sub-arrays. It has a time complexity of O(nlog⁡n) in the average and best cases, but can degrade to O(n²) in the worst case. Quick Sort is often preferred for its speed and efficiency, especially with larger datasets.

I hope this blog has helped you understand the Quick Sort algorithm, its implementation and its complexity.

Thank you for reading! If you have any questions or feedback, feel free to leave a comment below. Happy coding!