Quick Sort in java


If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Quick sort 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.

Quick Sort implementation


Before Sorting :
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1]
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]

Time complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
To understand more about complexity,please go through complexity of algorithm.

 That’s all about quick sort in java.

Related posts

Add Comment