In this post, we will learn How to write a quicksort program in Java.
Quicksort is usually considered the fastest in-memory sorting algorithm in most of the situations. Just like Merge sort, It is also a divide and conquer algorithm. which works on the idea to partition the large list into smaller lists around a chosen value (pivot) so that all the smaller values than the pivot value are on the left and all the higher values than the pivot value are on the right. Quicksort then recursively sorts the list with smaller values and the list with higher values by further partitioning it around a pivot.
Steps to implement the quicksort are as follows-
First chose a pivot value (it must be one of the elements from the list that has to sort).
Partition the list in such a way that all the elements having a value less than the pivot value come before the pivot and all the elements having a value higher than the pivot value come after the pivot. After this partitioning is done pivot value is at its final position.
Finally, we call recursively the above steps separately for the smaller element list and for the higher element list.
We can choose any random value as the pivot while implementing a quick sort like.
- The first element in the list as a pivot.
- Last element in the list as a pivot
- A middle element as pivot.
- Median of the items being sorted.
Understanding the quicksort program
In the program, we have a quickSort method which is called recursively with the two arrays. One sub-array contains the elements smaller than the pivot and another sub-array contains the elements greater than the pivot. To partition the elements, we have a partition method.
To swap the elements we will start at both ends of the array. From the left, we move towards right looking for an element greater than pivot value, and from the right, we move towards left looking for an element smaller than the pivot.
Complete Source Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
package com.kkjavatutorials.client; import java.util.Arrays; /** * Java program for Quick sort * @author KK JavaTutorials */ public class QuickSortTest { public static void main(String[] args) { //Input Array int[] inputArr = {50,25,92,16,76,30,43,54,19}; System.out.println("Original input Array:"+Arrays.toString(inputArr)); //Call quickSort to perform sorting quickSort(inputArr, 0, inputArr.length-1); //Print sorted Array System.out.println("Array Sorted After Quick Sort:"+Arrays.toString(inputArr)); } /** * Recursive method to perform quck sort * @param inputArr input Array * @param lowerIndex start index of input array * @param upperIndex last index of input array */ private static void quickSort(int[] inputArr, int lowerIndex, int upperIndex){ //Base condition to terminate recursion if(upperIndex - lowerIndex <= 0){ return; }else{ int partition = partition(inputArr, lowerIndex, upperIndex); // calling method again with smaller values quickSort(inputArr, lowerIndex, partition-1); // calling method again with higher values quickSort(inputArr, partition+1, upperIndex); } } /** * Function to partition the list in such a way that all the * elements having a value less than the pivot value * come before the pivot and all the elements having * a value higher than the pivot value come after the pivot. * @param inputArr input Array * @param lowerIndex start index * @param upperIndex end index * @return */ private static int partition(int[] inputArr, int lowerIndex, int upperIndex){ int pivot = inputArr[upperIndex]; int left = lowerIndex - 1; int right = upperIndex; while(true){ /*Finding an element greater than pivot element * start scanning from the beginning */ while(inputArr[++left] < pivot); /*Finding an element smaller than pivot element start scanning from the end */ while(right > 0 && inputArr[--right] > pivot); if(left >= right){ break; }else{ swap(inputArr, left, right); } } swap(inputArr, left, upperIndex); return left; } private static void swap(int[] inputArr, int a, int b){ int temp = inputArr[a]; inputArr[a] = inputArr[b]; inputArr[b] = temp; } } |
The output of this program:
Original input Array:[50, 25, 92, 16, 76, 30, 43, 54, 19]
Array Sorted After Quick Sort:[16, 19, 25, 30, 43, 50, 54, 76, 92]
Performance of quicksort:
The average time complexity of quicksort is O(n log n). In the worst case, it can be O(n2). Every recursive call required its own stack space so space complexity of quicksort is O(n).
You May Also Like :
What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
How to write a Merge sort program in Java
How to write a Radix sort program in Java
Tree Sort Using Binary Search Tree in Java
That’s all about How to write a Quick Sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.