Java Program to Implement Quick Sort Algorithm

July 28, 2023

What is Quicksort in java.

The quicksort sorting algorithm divides an unsorted list into smaller sublists, which are then repeatedly sorted until the full list is sorted. The list is split into two sublists: elements less than the pivot and elements greater than the pivot when it selects a “pivot” element. The two sublists are then sorted recursively with the pivot put in its last position in the sorted list.

The final sorted array is obtained by concatenating the left sub-array, pivot, and right sub-array.
This algorithm has a time complexity of O(n log n) in the average and best case, and O(n^2) in the worst case.
Quicksort is widely used due to its efficiency and simplicity.

To know more about Quicksort Algorithm in java read the complete article.

How to implement QuickSort in Java

Quicksort can be implemented in Java as follows:

Define a quickSort method that takes in the array to be sorted, the start index, and the end index.
In the quickSort method, select a pivot element from the array.
Partition the array into two sub-arrays, one containing elements less than the pivot and the other containing elements greater than the pivot.
Recursively sort the sub-arrays by calling the quickSort method on each of them.
Concatenate the two sub-arrays and the pivot element to obtain the final sorted array.

Note: QuickSort is also not a stable sorting algorithm, meaning that equal elements may not retain their original order after sorting.

Note: QuickSort has an average time complexity of O(n log n) and is generally faster than other sorting algorithms such as Bubble Sort and Selection Sort.

JVM vs JRE vs JDK

abs in java

String in java

add arraylist function in java

removeall arraylist in java

Choosing the Optimal Pivot in Quicksort algorithm in java :

Choosing the optimal pivot in the Quicksort algorithm can greatly impact the performance of the algorithm. There are several strategies for choosing the pivot, including:

First Element: Selecting the first element of the array as the pivot. This is the simplest strategy, but it can lead to poor performance if the array is already sorted or nearly sorted.
Last Element: Selecting the last element of the array as the pivot. This strategy is often used in practice because it’s simple and efficient in most cases.
Median Element: Selecting the median element of the array as the pivot. This strategy can lead to good performance, as the median is likely to be a better representative of the elements in the array.
Random Element: Selecting a random element of the array as the pivot. This strategy can provide good performance, as it reduces the chances of the worst-case scenario occurring.

Ultimately, the choice of pivot will depend on the specifics of the problem and the data being sorted. It’s important to choose a pivot strategy that’s appropriate for the data and the problem being solved.

Let’s look at a Java program where the implementation of Quicksort Algorithm on java is used to perform an operation.

Example: Implementation of Quicksort Algorithms in java

Run

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex-1);
            quickSort(arr, pivotIndex+1, high);
        }
    }

    private 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;
    }
}

Output

Sorted array: [1, 5, 7, 8, 9, 10]

Explanation: In the example, the partition method is used to partition the array into two sub-arrays, and the quickSort method is used to sort the sub-arrays recursively. The pivot element is selected as the last element in the array in this example, but it can be selected in other ways as well.

Example 2 : Java Quicksort Algorithm Method

Run

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        quickSort(input,0,input.length-1);
        System.out.println("Sorted Array: " + Arrays.toString(input));
    }

    private static void quickSort(int[] input, int start, int end) {
        if (start < end) {
            int partitionIndex = partition(input, start, end);
            quickSort(input, start, partitionIndex-1);
            quickSort(input, partitionIndex+1, end);
        }
    }

    private static int partition(int[] input, int start, int end) {
        int pivot = input[end];
        int i = start-1;
        for (int j = start; j < end; j++) {
            if (input[j] <= pivot) {
                i++;
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
        int temp = input[i + 1];
        input[i + 1] = input[end];
        input[end] = temp;
        return i + 1;
    }
}

Output

Sorted Array: [2, 2, 12, 20, 24, 45, 53, 56, 56, 75, 99]

Explanation: In this example, the quickSort method uses the partition method to partition the array and sort the sub-arrays recursively. The partition method selects the last element as the pivot and partitions the array into two sub-arrays based on the pivot. The sub-arrays are then sorted recursively using the quickSort method.

Example 3: how to use the object clone property:

Run

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] input = {12,6,18,17,4,95,2,73,90,34,13};
        quickSort(input,0,input.length-1);
        System.out.println("Sorted Array: " + Arrays.toString(input));
    }

    private static void quickSort(int[] input, int start, int end) {
        if (start < end) {
            int partitionIndex = partition(input, start, end);
            quickSort(input, start, partitionIndex-1);
            quickSort(input, partitionIndex+1, end);
        }
    }

    private static int partition(int[] input, int start, int end) {
        int pivot = input[end];
        int i = start-1;
        for (int j = start; j < end; j++) {
            if (input[j] <= pivot) {
                i++;
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
        int temp = input[i + 1];
        input[i + 1] = input[end];
        input[end] = temp;
        return i + 1;
    }
}

Output

Sorted Array: [2, 4, 6, 12, 13, 17, 18, 34, 73, 90, 95]

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Java Program to Implement Quick Sort Algorithm

What is Quicksort in java.

How to implement QuickSort in Java

Choosing the Optimal Pivot in Quicksort algorithm in java :

Let’s look at a Java program where the implementation of Quicksort Algorithm on java is used to perform an operation.

Example: Implementation of Quicksort Algorithms in java

Output

Example 2 : Java Quicksort Algorithm Method

Output

Example 3: how to use the object clone property:

Output

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription