Java Code for Quick Sort

Java Code for Quick Sort. Quick sort is a highly efficient sorting algorithm based on the divide and conquer strategy. It is widely used in practice due to its superior performance with large data sets where its average and worst time complexity stand impressively as O(n logn) and O(n^2) respectively. The algorithm operates by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process of partitioning, recursive sorting, and merging results in the entire array being sorted.

How Quick Sort Works

• Pivot Selection: The first step in the quick sort is to choose a pivot element from the array. The choice of pivot can affect the algorithm’s performance, but for simplicity, we often select the first element, the last element, or a random element as the pivot.
• Partitioning: Rearrange the array so that all elements less than the pivot come before it, while all elements with a value greater than the pivot come after it. After this partitioning, the pivot is the next final position.
• Recursive Sorting: Recursively apply the above steps to the sub-array of elements with smaller values and a sub-array of elements with larger values.

Java Program for Quick Sort

Below is a concise implementation of the quick sort algorithm in Java. This implementation showcases how quick sort is applied to an array of integers. The following Java code for quick sort demonstrates the algorithm’s recursive nature and how partitioning works.

import java.util.Scanner;

public class quicksort {

   public static int partition(int array[], int low, int high)
    {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j <= high; j++)
        {
            if (array[j] < pivot)
            {
                i++;
                int temp = array[i];
                array[i]=array[j];
                array[j]=temp;
            }
        }
        int temp = array[i+1];
        array[i+1]=array[high];
        array[high]=temp;
        return i + 1;
    }
    public static void quickSort(int array[], int low, int high)
    {
        if (low < high)
        {
            int partitionIndex = partition(array, low, high);
            quickSort(array, low, partitionIndex - 1);
            quickSort(array, partitionIndex + 1, high);
        }
    }
    public static void main(String[] args)    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of array");
        int n =sc.nextInt();
        int[] array = new int[n];
        System.out.println("Enter the element of array ");
        for(int i=0;i<n;i++) {
            array[i] = sc.nextInt();
        }
        System.out.println("Array before sorting");
        for (int i = 0; i < n; i++)
        {
            System.out.print(array[i]+" ");
        }
        quickSort(array, 0, n - 1);
        System.out.println("\nArray After sorting");
        for (int i = 0; i < n; i++)
        {
            System.out.print(array[i]+" ");
        }
    }

}

Output

Key Points for Quick Sort

• The Pivot choice is crucial: The efficiency of the quick sort algorithm significantly depends on the pivot selection. The worst-case time complexity is O(n^2) occurs in scenarios where the smallest or largest element is always picked as the pivot. However, this is rare in practice, especially with good pivot selection strategies.
• In-Place Sorting: Quick sort is an in-place sorting algorithm that does not require additional storage proportional to the size of the input array, leading to a space complexity of O(logn) due to stack space used in recursion.
• Not stable: By default quick sort algorithm is not stable. However, with some modification, a special version can be achieved.

Quick sort is a preferred algorithm for sorting large datasets due to its efficiency and performance. Its implementation in Java(as given above) is straightforward yet powerful, making it a valuable algorithm for Java developers to understand and utilize.

Happy Coding & Learning

See Also

• Binary to Decimal Java Conversion
• Java Code for Selection Sort