Quick Sort

Quick Sort

Sort Algorithm:
  1. If left >= right the
    1. return
  2. Recursively call sort function with left to pivot – 1 index
  3. Recursively call sort function with pivot + 1 to right index
Partition Algorithm:
  1. Set pivot = array[end]
  2. Set pivot_index = start
  3. Iterate from start to end of
    1. If array[i] < pivot then
      1. Swap ith index data with pivot_index data
      2. Increase pivot_index by 1
  4. Swap pivot_index with end_index
  5. return pivot_index
Merge Sort Quick Sort
Worst case O(nlogn) Avg case O(nlogn) and,
wors case O(n2)
O(n) – space complexity (not in-place sorting) O(n) – constant (in-place sorting)

Source Code:
Github: QuickSort.java


Output:

Before sort: 7 3 18 9 1 2 15 12 5 
After sort: 1 2 3 5 7 9 12 15 18     

Video

Author: Hrishikesh Mishra