If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.
In quick sort, we first choose a
Table of Contents
pivot and divide into two sublists,one will contain elements lower than pivot and other will have elements greater than pivot.
Quick sort Algorithm
Lets say array is arr[]
- Choose a
pivot, it is generally mid element of the list. - Initialise two index variable ,
left=0andright=arr.length-1 - Increment left variable until you get element higher than pivot.
- Decrement right variable until you get element lesser than pivot
- swap
arr[left]andarr[right] Recursively sort sublists(sublist with less than pivot, sublist greater than pivot) using above algorithm.- In the end , you will get
sorted array.
Quick Sort implementation
|
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 |
package org.arpit.java2blog; import java.util.Arrays; public class QuickSortMain { private static int array[]; public static void sort(int[] arr) { if (arr == null || arr.length == 0) { return; } array = arr; quickSort(0, array.length-1); } private static void quickSort(int left, int right) { int i = left; int j = right; // find pivot number, we will take it as mid int pivot = array[left+(right-left)/2]; while (i <= j) { /** * In each iteration, we will increment left until we find element greater than pivot * We will decrement right until we find element less than pivot */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { exchange(i, j); //move index to next position on both sides i++; j--; } } // call quickSort() method recursively if (left < j) quickSort(left, j); if (i < right) quickSort(i, right); } private static void exchange(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String a[]){ int[] input = {33,21,45,64,55,34,11,8,3,5,1}; System.out.println("Before Sorting : "); System.out.println(Arrays.toString(input)); sort(input); System.out.println("=================="); System.out.println("After Sorting : "); System.out.println(Arrays.toString(array)); } } |
Output:
Before Sorting :
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1] ==================
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1] ==================
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]
Time complexity
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
To understand more about complexity,please go through complexity of algorithm.
 That’s all about quick sort in java.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
