Quick sort in Java

Refer: Main indexed article on sorting.

Quick sort is based on the principle of divide and conquer.
Quick sort first divides the large lists into two sub smaller lists, the low elements and the high elements.
It can then recursively sort the sub-lists.

How does it work?

• Choose an element and called it as pivot, in the given list.
• Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way).
• After this partitioning pivot is in its final position.
• This is called the partition operation.
• Recursively apply the above steps to the sub-lists of the elements with smaller values and separately the sub-lists of elements with greater values.

Choice of Pivot:
Generally, the last element of the partition would often be chosen as the pivot element.
Unfortunately, this causes worst-case behavior on already sorted arrays.
One can choose a random index for pivot or choose the median of the first, middle and last element.

Java Code snippet: