Sorting Algorithms in Java: Bubble, Selection, Insertion, Merge, and Quick Sort

Chapter 5: Quick Sort in Java

1. Description of Quick Sort (No Coding)

Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot element and partitions the array such that all elements smaller than the pivot are on the left and all larger elements are on the right. It then recursively sorts the left and right partitions.

It is one of the fastest sorting algorithms in practice and is widely used in real-world applications due to its O(n log n) average-case complexity and in-place sorting (requires no extra memory like Merge Sort). However, it has a worst-case complexity of O(n²) if the pivot selection is poor (e.g., always picking the smallest or largest element in a sorted or reverse-sorted array).

Working Principle of Quick Sort

1. Choose a pivot (typically the last element, first element, middle element, or a random element).
2. Partition the array such that:
• All elements smaller than the pivot move to the left.
• All elements larger than the pivot move to the right.
3. Recursively apply Quick Sort to the left and right partitions.
4. The base case is reached when the partitions have one or zero elements (already sorted).

Visualization Example

Unsorted Array:

[8, 3, 5, 2, 9, 4, 1, 7]

Step 1: Choose a Pivot (e.g., 7)

• Partition the array:
• Left: [3, 5, 2, 4, 1] (less than 7)
• Pivot: 7
• Right: [8, 9] (greater than 7)

Step 2: Recursively Sort Left and Right Partitions

• Sorting [3, 5, 2, 4, 1] → Pivot: 3 → [2, 1] + 3 + [5, 4]
• Sorting [8, 9] → Already sorted

Step 3: Combine Sorted Partitions

Final Sorted Array: [1, 2, 3, 4, 5, 7, 8, 9]

2. Quick Sort Coding Examples

(a) Syllabus-Based Example (Sorting an Array of Numbers)

public class QuickSortExample {

    static void quickSort(int arr[], int low, int high) {

        if (low < high) {

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

            quickSort(arr, low, pi - 1);

            quickSort(arr, pi + 1, high);

        }

    }

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

        int pivot = arr[high];

        int i = (low - 1);

        for (int j = low; j < high; j++) {

            if (arr[j] < pivot) {

                i++;

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

        int temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

        return i + 1;

    }

    public static void main(String args[]) {

        int arr[] = {8, 3, 5, 2, 9, 4, 1, 7};

        quickSort(arr, 0, arr.length - 1);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Output:
[1, 2, 3, 4, 5, 7, 8, 9]

(b) Real-World Example (Sorting a List of Employee Salaries in Descending Order)

import java.util.Arrays;

public class QuickSortDescending {

    static void quickSort(double arr[], int low, int high) {

        if (low < high) {

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

            quickSort(arr, low, pi - 1);

            quickSort(arr, pi + 1, high);

        }

    }

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

        double pivot = arr[high];

        int i = (low - 1);

        for (int j = low; j < high; j++) {

            if (arr[j] > pivot) { // Change "<" to ">" for descending order

                i++;

                double temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

        double temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

        return i + 1;

    }

    public static void main(String args[]) {

        double salaries[] = {55000, 72000, 48000, 82000, 65000};

        quickSort(salaries, 0, salaries.length - 1);

        System.out.println(Arrays.toString(salaries));

    }

}

Output:
[82000, 72000, 65000, 55000, 48000]

3. Advantages of Quick Sort (Pros)

✔ Very fast for large datasets – Performs better than Merge Sort and Insertion Sort.
✔ In-place sorting – Requires no extra memory (O(1)).
✔ Divide-and-conquer approach – Efficiently sorts large data.
✔ Efficient for random data – Performs well for most real-world datasets.
✔ Used in real-world applications – Quick Sort is the foundation of Java’s Arrays.sort() for primitive types.

4. Disadvantages of Quick Sort (Cons)

❌ Worst case O(n²) for poor pivot selection – If the pivot is always the smallest or largest element, performance degrades.
❌ Not a stable sort – It does not preserve the relative order of equal elements.
❌ Recursive function calls – Can cause stack overflow for large arrays.
❌ Performance depends on pivot choice – Bad pivot selection can slow down sorting.
❌ Slower than Merge Sort for large, already sorted datasets – Merge Sort is more consistent.

5. How is Quick Sort Better Than Other Sorting Techniques?

• Faster than Merge Sort for most practical cases – Uses in-place partitioning, reducing overhead.
• More efficient than Bubble Sort, Selection Sort, and Insertion Sort – Much faster for large datasets.
• Better than Merge Sort in terms of memory – No extra space required.
• Used in Java’s sorting library – Optimized in Java’s Arrays.sort().
• Faster than Merge Sort when implemented with an efficient pivot selection strategy (e.g., randomized pivot).

6. Best Cases to Use Quick Sort

✔ When memory is limited – Uses in-place sorting (O(1) space complexity).
✔ For general-purpose sorting – Works well on most data structures.
✔ For sorting large datasets – Performs better than Merge Sort in most cases.
✔ When speed is crucial – One of the fastest sorting algorithms.
✔ When a non-stable sort is acceptable – Useful for applications where stability is not required.

7. Worst Cases to Use Quick Sort

❌ When worst-case O(n²) time complexity is a concern – Merge Sort is safer.
❌ When stability is required – Merge Sort is a stable alternative.
❌ For already sorted or reverse-sorted arrays – Leads to poor performance if pivot is poorly chosen.
❌ For very large datasets with recursion limits – Can cause stack overflow issues.
❌ For sorting linked lists – Merge Sort is more efficient for linked lists.

Final Thoughts

Quick Sort is one of the fastest sorting algorithms and is widely used in real-world applications. However, poor pivot selection can degrade its performance. For consistent performance, consider using randomized pivot selection or Hybrid Quick Sort (combining Quick Sort with Insertion Sort for small arrays). 🚀