0. Thought#
- Divide and conquer
1. Steps#
- Select 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 of the elements to be sorted, then after each sorting, one element's position is determined, taking time: $\theta(n)$, and then recursively performing quick sort on an n-1 element array and a 0 element array. 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 after each sorting, one element's position is determined, taking time: $\theta(n)$, and then recursively performing quick sort on two n/2 element arrays. 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. Therefore, a random selection can be added to optimize quick sort.
- For small array sorting, other methods can be used.
- Use iteration instead of recursion.
Done！
This article is synchronized and updated to xLog by Mix Space
The original link is https://www.vikifish.com/posts/algo/qsort