Implementing Quick Sort in Java

January 28, 2024

Implementing Quick Sort in Java

Sorting is a fundamental operation in computer science, and Quick Sort is a well-known and efficient algorithm for this task. In this blog post, we’ll explore the implementation of Quick Sort in Java, discuss its logic, and provide examples to enhance understanding.

Quick Sort Overview

Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a ‘pivot’ element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is then applied recursively to the sub-arrays.

Implementing Quick Sort in Java

Let’s dive into a simple Java implementation of Quick Sort:

Java Program – Quick Sort

import java.util.Arrays;

public class QuickSort {

    // Main method to start the Quick Sort process
    public static void main(String[] args) {
        int[] array = {29, 10, 14, 37, 13};

        System.out.println("Original Array: " + Arrays.toString(array));

        // Call the sort method to perform Quick Sort
        sort(array);

        System.out.println("Sorted Array: " + Arrays.toString(array));
    }

    // Main method to start the Quick Sort process
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

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

            // Recursively apply Quick Sort to the sub-arrays
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    // Helper method to partition the array and return the pivot index
    private static int partition(int[] array, int low, int high) {
        // Choose the rightmost element as the pivot
        int pivot = array[high];
        int i = low - 1;

        // Iterate through the array and reorganize elements
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                // Swap elements if they are less than the pivot
                swap(array, i, j);
            }
        }

        // Swap the pivot element into its correct position
        swap(array, i + 1, high);

        // Return the pivot index
        return i + 1;
    }

    // Helper method to swap two elements in the array
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Understanding the Logic

sort :

Entry point to the Quick Sort algorithm. It checks for null or empty arrays and calls quickSort to start the sorting process.

quicksort :

Recursive method that performs the actual sorting.
Chooses a pivot, partitions the array, and recursively applies Quick Sort to the sub-arrays.

partition :

Selects the rightmost element as the pivot.
Reorganizes the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

swap :

Helper method to swap two elements in the array.

Example:

Let’s consider an example array: {29, 10, 14, 37, 13}.

Initial Step:

Choose 13 as the pivot (rightmost element).

Partition:

Reorganize the array: {10, 13, 14, 37, 29}.

Recursion:

Apply Quick Sort to the left and right sub-arrays.

Final Result:

The sorted array: {10, 13, 14, 29, 37}.

Output:

Output – Quick Sort

Original Array: [29, 10, 14, 37, 13]
Sorted Array: [10, 13, 14, 29, 37]

Complexity:

Complexity	Worst Case	Average Case	Best Case
Time Complexity	O(n^2)	O(n log n)	O(n log n)
Space Complexity	O(log n) auxiliary	O(log n) auxiliary	O(log n) auxiliary

Conclusion

Quick Sort is a powerful and widely used sorting algorithm, known for its efficiency and average-case time complexity of O(n log n). By understanding its logic and implementation in Java, you can appreciate its effectiveness in sorting arrays with speed and elegance. Happy Coding!

Latest Posts: