How to implement Quick Sort in java

Posted on Updated on

Quick sort which by name conveys sorting done quickly. It is based on Divide and Conquer as termed as Partition exchange sort. Though this sorting algorithm is not stable but it requires very less additional space and is fast. To follow its definition of divide and conquer, it first selects a pivot value and with the assistance of Pivot value list is splitting into three parts as mentioned below-

  1. Elements lesser than Pivot value
  2. Pivot Value
  3. Elements greater than Pivot value

There are many ways to choose the pivot value, but generally middle index item in list selected as pivot value. The actual position of pivot value in final sorted list is called a splitting point.

Worst Case Time Complexity : O(n2)

Best Case Time Complexity : O(n log n)

Average Time Complexity : O(n log n)

Space Complexity : O(n log n)

Space required by quick sort is very less, only O(n log n) additional space is required.

Quick sort is not a stable sorting technique, so it might change the occurrence of two similar elements in the list while sorting.

Let’s see an example-

Output

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.