Quick sort is a sorting algorithm that sorts an array by partitioning the array into two subarrays, then sorting the subarrays recursively.
The algorithm works by selecting a pivot element from the array, then partitioning the array around the pivot such that all elements less than the pivot are before it and all elements greater than the pivot are after it. The two subarrays are then sorted recursively.
Quick sort is a divide and conquer algorithm, meaning it breaks the problem down into smaller subproblems which it then solves recursively.
The time complexity of quick sort depends on the implementation, but the worst case is O(n^2) and the best case is O(n log n).
Here is a quick sort algorithm implemented in C.
void quick_sort(int *arr, int left, int right)
{
int i, j, pivot, tmp;
if (left < right) {
pivot = left;
i = left;
j = right;
while (i < j) {
while (arr[i] <= arr[pivot] && i <= right) {
i++;
}
while (arr[j] > arr[pivot]) {
j--;
}
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
tmp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = tmp;
quick_sort(arr, left, j - 1);
quick_sort(arr, j + 1, right);
}
}
The quick sort algorithm works by selecting a pivot element from the array, then partitioning the array around the pivot such that all elements less than the pivot are before it and all elements greater than the pivot are after it. The two subarrays are then sorted recursively.
The time complexity of quick sort depends on the implementation, but the worst case is O(n^2) and the best case is O(n log n).
Implement quick sort in your favorite programming language.
Compare the running time of quick sort and merge sort on various inputs.