Quick Sort in Java
Quick Sort in Java is used to sort elements of an array. Quick sort works on divide and conquer strategy and comparison sort. It is the fastest and simplest sorting algorithm when compared to other bubble sort, insertion sort, heap sort and other sorting algorithms. First it divides an array into two sub-arrays.
The complexity of quick sort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).
How does Quick Sort algorithm in Java works?
Quick Sort algorithm works on comparison sort that means it compares elements with each other in an array.
For this a random element is picked from an array called "Pivot". Once pivot is selected, the elements on its right and left are compared with it. When a smaller element to pivot is found, it is kept on the left side of pivot. In case of bigger elements, they are kept on the right side of the pivot.
Once the comparison is done the array is divided in two sub-arrays, one part of the array has small numbers than the pivot while others have bigger elements than pivot.
Same procedure is followed again in these two sub-arrays and partition is followed until numbers are sorted. At the end, all the arrays are merged.
Quick Sort does not require allocation of additional memory.
Posted on: September 28, 2013 If you enjoyed this post then why not add us on Google+? Add us to your Circles