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.

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
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
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.