0. Thought#
- Divide and Conquer
1. Steps#
- Choose a pivot base in the array, dividing the original array into 【less than base】- base -【greater than base】
- Repeat steps 1 and 2 for the two arrays 【less than base】 and 【greater than base】 until sorting is complete
2. Implementation#
void my_qsort(short *arr, int start, int end)
{
if (start >= end) {
return;
}
int i = start;
int j = end;
int base = arr[start];
while (i < j) {
while (arr[j] >= base && i < j) {
j--;
}
while (arr[i] <= base && i < j) {
i++;
}
if (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
arr[start] = arr[i];
arr[i] = base;
my_qsort(arr, start, i - 1);
my_qsort(arr, j + 1, end);
}
3. Performance Analysis#
Worst Case#
If the chosen pivot base is always the maximum/minimum element to be sorted, then each sorting step will determine the position of one element, taking time: $\theta(n)$, and then recursively quick sort an array of n-1 elements and an array of 0 elements. The running time is: $T(n) = T(n-1)+T(0)+\theta(n)$
The time complexity is: $O(n^2)$
Best Case#
If the chosen element is always the middle element of the array, then each sorting step will determine the position of one element, taking time: $\theta(n)$, and then recursively quick sort two arrays of n/2 elements. The running time is $T(n) = 2T(n/2)+\theta(n)$
The time complexity is: $O(nlogn)$
Average Case#
The average running time of quick sort is close to the best case, which is $O(nlogn)$
4. Optimization#
- The choice of pivot base in quick sort directly affects performance. To optimize quick sort, a random selection can be added.
- For small arrays, other sorting methods can be used.
- Use iteration instead of recursion.
Done！
This article is synchronized and updated to xLog by Mix Space Original link: https://www.vikifish.com/posts/algo/qsort