Java Program to Implement Quick sort

«
»

This is the 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.

advertisement
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.

  1.  
  2. //Java Program to Implement Quick Sort
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6. import java.util.Arrays;
  7. import java.util.Random;
  8.  
  9. public class QuickSort {
  10.     // Function to partion the array on the basis of the pivot value; 
  11.     static int partition(int[] array, int low, int high) {
  12.         int j, temp, i = low + 1;
  13.         Random random = new Random();
  14.         int x = random.nextInt(high - low) + low;
  15.         temp = array[low];
  16.         array[low] = array[x];
  17.         array[x] = temp;
  18.         for (j = low + 1; j <= high; j++) {
  19.             if (array[j] <= array[low] && j != i) {
  20.                 temp = array[j];
  21.                 array[j] = array[i];
  22.                 array[i++] = temp;
  23.             } else if (array[j] <= array[low]) {
  24.                 i++;
  25.             }
  26.         }
  27.         temp = array[i - 1];
  28.         array[i - 1] = array[low];
  29.         array[low] = temp;
  30.         return i - 1;
  31.     }
  32.     // Function to implement quick sort
  33.     static void quickSort(int[] array,int low,int high){
  34.         if(low<high){
  35.             int mid = partition(array,low,high);
  36.             quickSort(array,low,mid-1);
  37.             quickSort(array,mid+1,high);
  38.         }
  39.     }
  40.     // Function to read user input
  41.     public static void main(String[] args) {
  42.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  43.         int size;
  44.         System.out.println("Enter the size of the array");
  45.         try {
  46.             size = Integer.parseInt(br.readLine());
  47.         } catch (Exception e) {
  48.             System.out.println("Invalid Input");
  49.             return;
  50.         }
  51.         int[] array = new int[size];
  52.         System.out.println("Enter array elements");
  53.         int i;
  54.         for (i = 0; i < array.length; i++) {
  55.             try {
  56.                 array[i] = Integer.parseInt(br.readLine());
  57.             } catch (Exception e) {
  58.                 System.out.println("An error Occurred");
  59.             }
  60.         }
  61.         System.out.println("The initial array is");
  62.         System.out.println(Arrays.toString(array));
  63.         quickSort(array,0,array.length-1);
  64.         System.out.println("The sorted array is");
  65.         System.out.println(Arrays.toString(array));
  66.     }
  67. }
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.

advertisement
advertisement

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]

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter