Definition
one of sort algorithms
- The most important sort algorithm
- Use this algorithm anywhere with any languages
- The best way to avoid worst time complexity is pick pivot randomly.
- if program most not have $O(n^2)$, need to use other sorting algorithm.
Technique
Decrease and Conquer
Algorithm steps
Recusively loop based on Lomuto.
- pick pivot the most right element.
- left side will be smaller than pivot value and right side will be bigger than pivot.
- let’s say most left value is selected index and comaparing index without pivot.
- if comaparing index value is smaller than pivot, swap with selected index and increase the selected index.
- if comaparing index value is bigger than or equal pivot, increase the comaparing index.
- when the comaparing index is equal to pivot index, swap pivot and the selected index.
- Recusively loop step 1~6.
how to pick pivot
Lomuto
- pivot : the most right element.
- starting selected index (i) : 0
- starting comaparing index (j) : 0
Hoare
- pivot : the most left element.
- starting selected index (i) : 1
- starting comaparing index (j) : the most right element.
Randomly Choose
Java code - Lomuto
public static void quickSort(int[] input) {
quickSortRecur(input, 0, input.length - 1);
}
public static void quickSortRecur(int[] input, int left, int right) {
if (left >= right) {
return;
}
int pivotPos = partition(input, left, right);
quickSortRecur(input, left, pivotPos - 1);
quickSortRecur(input, pivotPos + 1, right);
}
public static void swap(int[] input, int a, int b) {
int temp = input[a];
input[a] = input[b];
input[b] = temp;
}
public static int partition(int[] input, int left, int right) {
int pivot = input[right];
int i = (left - 1);
for (int j = left; j < right; ++j) {
if (input[j] < pivot) {
++i;
swap(input, i, j);
}
}
swap(input, (i + 1), right);
return i + 1;
}
Java code - Hoare
public static void quickSort(int[] input) {
quickSortRecur(input, 0, input.length - 1);
}
public static void quickSortRecur(int[] input, int left, int right) {
if (left >= right) {
return;
}
int pivotPos = partition(input, left, right);
quickSortRecur(input, left, pivotPos);
quickSortRecur(input, pivotPos + 1, right);
}
public static void swap(int[] input, int a, int b) {
if (a != b) {
int temp = input[a];
input[a] = input[b];
input[b] = temp;
}
}
public static int partition(int[] input, int left, int right) {
int pivot = input[left];
int i = left - 1;
int j = right + 1;
while (true) {
do {
++i;
} while (input[i] < pivot);
do {
--j;
} while (input[j] > pivot);
if (i >= j) {
return j;
}
swap(input, i, j);
}
}
Avg. time complexity
$O(n, log, n)$
Worst time complexity
$O(n^2)$
space complexity
$O(log, n)$
stability
no
How to calculate
numbers of loop
- base recursion: $O(n)$
- If separated evenly : $O(log,n)$
- If separated not evenly : $O(n)$
Time Complexity
- If separated evenly : $ O(n \cdot log,n)=O(n,log,n)$
- If separated not evenly (the worst case) : $O(n \cdot n)=O(n^2)$