Quicksort as name suggests is the one of the quick technique to sort array of elements.
Now Question is, is it the best one ? No, not at all, we have many other sorting algorithms better than it.
Still you should have a very good understanding of Quicksort.
Quicksort works on the Divide and Conquer strategy.
It divides the whole array around an element of the array (we will call it Pivot), and try to arrange the elements in such a way that elements to the left of the array are smaller than it (might not be sorted) and elements to the right of Pivot are all greater than it (might not be sorted).
Once you finish this activity, you are sure that the Pivot element is at the right position in the array.
Do the same to the left and right subarrays around the Pivot element recursively and you are done.
Just before moving to the code:
1. I have explained every step as comments in the code, so please read process in code only.
2. We can select any element as Pivot, it could be 1st element, last element or middle or any random. generally I choose middle, however it is not the most efficient.
3. When we write any recursive method we always have to think before hand when to break the recursion, so have this in mind.
4. Best case time complexity is O(nlogn)
5. Worst case time complexity is O(n*n) in case of worst choice of pivot or already sorted.
6. in Java 8, Quicksort is used for primitive elements array, however Mergesort is used for Objects array.
Github link
lets write some code:
package madwani.sushil.sorting;
import madwani.sushil.Util;
public class QuickSort {
public static void main(String[] args) {
String input = Util.readLine();
int[] elements = Util.convertLineToIntArray(input);
quicksort(elements, 0, elements.length-1);
Util.print1dArray(elements);
}
public static void quicksort(int[] arr, int start, int end) {
// basic check to ensure corner case
if (arr == null || arr.length == 0) {
return;
}
// condition to break recursion
if (start >= end) {
return;
}
// I always chose middle element as Pivot
int middle = start + (end - start) / 2;
// Pivot element
int pivot = arr[middle];
// lets start the real sorting
int i = start, j = end;
// do comparison and swapping till start and end have not met
while (i <= j) {
// increment till left side elements are lesser or equal to pivot
while (arr[i] <= pivot) {
i++;
}
// decrement till right side elements are greater to pivot
while (arr[j] > pivot) {
j--;
}
// swap elements from left right only when indices haven't crossed each other
// after swap always increase lower index and decrease higher index
if (i <= j) {
Util.swapElementsInArray(arr, i, j);
i++;
j--;
}
}
// one pass is done, so we have 2 boundaries
// lower boundary: i which was moving towards end
// upper boundary: j which was moving towards start
// if i has not reached and crossed the end lets do one more pass from i to end
// this is left subarray
if (end > i) {
quicksort(arr, i, end);
}
// if j has not reached the start and crossed, lets do one more pass from start to j
// this is right subarray
if (start < j) {
quicksort(arr, start, j);
}
}
}
