Quick Sort
Sort Algorithm:
- If left >= right the
- return
- Recursively call sort function with left to pivot – 1 index
- Recursively call sort function with pivot + 1 to right index
Partition Algorithm:
- Set pivot = array[end]
- Set pivot_index = start
- Iterate from start to end of
- If array[i] < pivot then
- Swap ith index data with pivot_index data
- Increase pivot_index by 1
- If array[i] < pivot then
- Swap pivot_index with end_index
- 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