Quick Sort in java

Quicksort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.
In quick sort, we first choose a 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=0 and right=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] and arr[right]
  • Recursively sort sublists(sublist with less than pivot, sublist greater than pivot) using above algorithm.
  • In the end , you will get sorted array.

Java program to implement quick sort:

Time complexity : 
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

Add Comment