Java Program to Implement Quick sort

Problem Description

Given an array of integers, sort the array using the quicksort algorithm.

Problem Solution

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.Program/Source Code

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

Program Explanation

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)) where n is the number of elements in the array.

Runtime Test Cases

Case 1 (Simple Test Case):
 
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]
 
Case 2 (Simple Test Case - another example):
 
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]