Java Program to Implement Quick Sort

What is Quick Sort?
Quick Sort is a sorting algorithm used in Java that employs a divide-and-conquer strategy to sort a list of elements. It works by selecting a “pivot” element from the array and then partitioning the other elements into two sub-arrays based on whether they are less than or greater than the pivot. The process is then repeated recursively on the sub-arrays until the entire array is sorted.

1. Pick an element, called a pivot, from the array.
2. Partition the array into two halves, the left side of the array containing elements less than the pivot element, and the right side of the array containing elements greater than the pivot element.
3. Recursively sort the left side of the array and the right side of the array.
4. Return the array.

Write a Java program to implement the Quick Sort algorithm.

The idea is to divide the array into two parts, on the basis of a special value known as the pivot. The array is divided such that all the elements to the left of the pivot are less than or equal to the pivot, and all the elements to the right of the pivot are greater than the pivot. Recursively, sort the two divided parts of the array.

Let’s say we have a list of numbers that we want to sort in ascending order using the Quick Sort algorithm. The list is {7, 2, 9, 1, 6, 8, 5, 3, 4}.

1. Choose a pivot element: In this example, we’ll choose 6 as the pivot element.
2. Partition the list: Rearrange the list so that all elements less than the pivot are on the left and all elements greater than the pivot are on the right. The new list is {2, 1, 5, 3, 4, 6, 9, 7, 8}.
3. Sort the sub-lists recursively: Divide the list into two sub-lists, one with elements less than the pivot and one with elements greater than the pivot. For the left sub-list, choose 3 as the pivot and partition the list into {2, 1} and {5, 4, 3}. For the right sub-list, choose 8 as the pivot and partition the list into {7} and {9, 8}.
4. Recursively sort each sub-list using the same steps until the entire list is sorted.
5. The final sorted list is {1, 2, 3, 4, 5, 6, 7, 8, 9}.

There are several ways to write an Quick Sort program in Java language. Let’s discuss all the ways in detail.

• Quick Sort Program in Java
• Quick Sort Program in Java using Recursion
• Quick Sort in Java using Randomization

In this approach we will not use recursion. We will instead use a for loop to iterate through the array.

Here is the source code of the Java Program to Implement Quick Sort. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

 
//Java Program to Implement Quick Sort
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
 
public class QuickSort {
    // Function to partion the array on the basis of the pivot value; 
    static int partition(int[] array, int low, int high) {
        int j, temp, i = low + 1;
        Random random = new Random();
        int x = random.nextInt(high - low) + low;
        temp = array[low];
        array[low] = array[x];
        array[x] = temp;
        for (j = low + 1; j <= high; j++) {
            if (array[j] <= array[low] && j != i) {
                temp = array[j];
                array[j] = array[i];
                array[i++] = temp;
            } else if (array[j] <= array[low]) {
                i++;
            }
        }
        temp = array[i - 1];
        array[i - 1] = array[low];
        array[low] = temp;
        return i - 1;
    }
    // Function to implement quick sort
    static void quickSort(int[] array,int low,int high){
        if(low<high){
            int mid = partition(array,low,high);
            quickSort(array,low,mid-1);
            quickSort(array,mid+1,high);
        }
    }
    // Function to read user input
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size;
        System.out.println("Enter the size of the array");
        try {
            size = Integer.parseInt(br.readLine());
        } catch (Exception e) {
            System.out.println("Invalid Input");
            return;
        }
        int[] array = new int[size];
        System.out.println("Enter array elements");
        int i;
        for (i = 0; i < array.length; i++) {
            try {
                array[i] = Integer.parseInt(br.readLine());
            } catch (Exception e) {
                System.out.println("An error Occurred");
            }
        }
        System.out.println("The initial array is");
        System.out.println(Arrays.toString(array));
        quickSort(array,0,array.length-1);
        System.out.println("The sorted array is");
        System.out.println(Arrays.toString(array));
    }
}

1. In function partition(), the first element of the array is randomly swapped with any element of that element of the array and then it is chosen as pivot.
2. The loop for(j = low+1;j<=high; j++), shifts all the elements less than the pivot to its left and finally the pivot value is shifted to its final position.
3. In function quicksort(), the dividing index is obtained from the call to partition function.
4. Then recursively the two halves are sorted.

Time Complexity: O(n*log(n))
The time complexity of the quick sort algorithm is O(n*log(n)), where n is the number of elements in the array.

Space Complexity: O(n)
The space complexity for quick sort is O(n).

Test Case 1: Quicksort on a Reverse-Sorted Array

Input:
An array of integers in reverse sorted order: 5, 4, 3, 2, 1.

Task:
Apply the quicksort algorithm to the input array to sort it in ascending order.

Output:

 
Enter the size of the array
5
Enter array elements
5
4
3
2
1
The initial array is
[5, 4, 3, 2, 1]
The sorted array is
[1, 2, 3, 4, 5]

Test Case 2: In this case, the elements are entered in a random order. The elements entered to sort the array using quick sort are “4, 3, 2, 1, 1, 2, 3, 4”.

Enter the size of the array
8
Enter array elements
4
3
2
1
1
2
3
4
The initial array is
[4, 3, 2, 1, 1, 2, 3, 4]
The sorted array is
[1, 1, 2, 2, 3, 3, 4, 4]

In this approach we will use recursion. We will pick a pivot element, and partition the array into two halves. We will then recursively sort the left side of the array and the right side of the array. We will then return the array.

Here is the source code of the Java Program to Implement Quick Sort using recursion. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

 
//Java Program to Implement Quick Sort using Recursion
 
public class QuickSort
{
    public static void quickSort(int[] array, int left, int right)
    {
        if (left < right) {
            int pivotIndex = partition(array, left, right);
            quickSort(array, left, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, right);
        }
    }
 
    public static int partition(int[] array, int left, int right)
    {
        int pivot = array[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, right);
        return i + 1;
    }
 
    public static void swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
    public static void main(String[] args)
    {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;
 
        System.out.println("Original Array:");
        for (int i = 0; i < n; i++) {
            System.out.print(array[i] + " ");
        }
 
        quickSort(array, 0, n - 1);
 
        System.out.println("\nSorted Array:");
        for (int i = 0; i < n; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

1. The program implements the Quick Sort algorithm to sort an array of integers.
2. The quickSort() method recursively partitions the array around a pivot element and sorts the resulting subarrays.
3. The partition() method chooses the rightmost element as the pivot and rearranges the elements in the array such that all elements to the left of the pivot are smaller and all elements to the right are larger.
4. The swap() method swaps two elements in the array. The main() method initializes an array and prints the original and sorted arrays using quickSort().

The program uses the QuickSort algorithm to sort the given array in ascending order. The original array is printed first, followed by the sorted array.

Original Array:
10 7 8 9 1 5
Sorted Array:
1 5 7 8 9 10

This is a java program to sort the large number of elements using Quick Sort Technique. Quick sort uses a pivot element, where all the elements less that pivot are kept in one list and all the elements greater than pivot are kept in another list, and so on.

Here is the source code of the Java Program to Perform Quick Sort on Large Number of Elements. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to sort large number of element using Quick Sort
import java.util.Random;
 
public class Quick_Sort 
{
    public static int N = 25;
    public static int[] sequence = new int[N];
 
    public static void QuickSort(int left, int right) 
    {
        if (right - left <= 0)
            return;
        else 
        {
            int pivot = sequence[right];
            int partition = partitionIt(left, right, pivot);
            QuickSort(left, partition - 1);
            QuickSort(partition + 1, right);
        }
    }
 
    public static int partitionIt(int left, int right, long pivot) 
    {
        int leftPtr = left - 1;
        int rightPtr = right;
        while (true) 
        {
            while (sequence[++leftPtr] < pivot)
                ;
            while (rightPtr > 0 && sequence[--rightPtr] > pivot)
                ;
 
            if (leftPtr >= rightPtr)
                break;
            else
                swap(leftPtr, rightPtr);
        }
        swap(leftPtr, right);
        return leftPtr;
    }
 
    public static void swap(int dex1, int dex2) 
    {
        int temp = sequence[dex1];
        sequence[dex1] = sequence[dex2];
        sequence[dex2] = temp;
    }
 
    static void printSequence(int[] sorted_sequence) 
    {
        for (int i = 0; i < sorted_sequence.length; i++)
            System.out.print(sorted_sequence[i] + " ");
    }
 
    public static void main(String args[]) 
    {
        System.out
                .println("Sorting of randomly generated numbers using QUICK SORT");
        Random random = new Random();
 
        for (int i = 0; i < N; i++)
            sequence[i] = Math.abs(random.nextInt(100));
 
        System.out.println("\nOriginal Sequence: ");
        printSequence(sequence);
        System.out.println("\nSorted Sequence: ");
        QuickSort(0, N - 1);
        printSequence(sequence);
 
    }
 
}

$ javac Quick_Sort.java
$ java Quick_Sort
 
Sorting of randomly generated numbers using QUICK SORT
 
Original Sequence: 
54 22 88 52 43 84 61 75 54 72 7 42 47 15 40 16 46 28 9 48 78 10 89 95 8 
Sorted Sequence: 
7 8 9 10 15 16 22 28 40 42 43 46 47 48 52 54 54 61 72 75 78 84 88 89 95

Advantages of Quick Sort Algorithm:

• Efficiency: Quicksort has an average-case time complexity of O(n log n), making it efficient for sorting large data sets.
• In-place sorting: Quicksort can sort elements in place, which means it does not require additional memory.
• Fastest for random input: Quicksort is the fastest sorting algorithm for random or almost random input data.
• Cache-friendly: Quicksort accesses memory in a sequential pattern, taking advantage of CPU cache and making it a cache-friendly algorithm.
• Divide and conquer approach: Quicksort uses a divide and conquer approach, breaking problems down into smaller sub-problems and solving each independently. This approach is more efficient than other algorithms that compare and swap elements in place.

Disadvantages of Quick Sort Algorithm:

• Worst-case complexity: Quicksort has a worst-case time complexity of O(n²) when the data is already sorted or mostly sorted, making it inefficient.
• Unstable sorting: Quicksort is an unstable sorting algorithm, which means that the order of equal elements in the input is not necessarily preserved in the output.
• Random pivot selection: Quicksort relies on random pivot selection, which can result in worst-case behavior when the pivot is poorly chosen.
• Recursive: Quicksort is a recursive algorithm, which can lead to stack overflow errors and memory usage problems for large data sets.

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.