Quick Sort
CS/Algorithm 2010. 8. 3. 04:24 function quicksort(array, left, right)
var pivot, leftIdx = left, rightIdx = right
if right > left // only sort if there are >= 2 elements
pivot = (left + right) / 2
while leftIdx <= pivot and rightIdx >= pivot
while array[leftIdx] < array[pivot] and leftIdx <= pivot
leftIdx = leftIdx + 1
while array[rightIdx] > array[pivot] and rightIdx >= pivot
rightIdx = rightIdx - 1;
swap array[leftIdx] with array[rightIdx]
leftIdx = leftIdx + 1
rightIdx = rightIdx - 1
if leftIdx - 1 == pivot
pivot = rightIdx = rightIdx + 1
else if rightIdx + 1 == pivot
pivot = leftIdx = leftIdx - 1
quicksort(array, left, pivot - 1)
quicksort(array, pivot + 1, right)void quick_sort(int arr[], int l, int r)
{
if (l < r) {
int i=l, j=r, pivot=l+(r-l)/2;
while (i < j) {
while (i < pivot && arr[i] <= arr[pivot])
++i;
while (j > pivot && arr[j] >= arr[pivot])
--j;
swap_arr(arr, i, j);
++i, --j;
if (i-1 == pivot)
pivot = j = j+1;
else if (j+1 == pivot)
pivot = i = i-1;
}
qsort_2(arr, l, pivot-1);
qsort_2(arr, pivot+1, r);
}
}
// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
// number of elements in subarray: right-left+1
function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex procedure quicksort(array, left, right)
if right > left // subarray of 0 or 1 elements already sorted
select a pivot index //(e.g. pivotIndex := left + (right - left)/2)
pivotNewIndex := partition(array, left, right, pivotIndex)
// element at pivotNewIndex is now at its final position and never moved again
// and guarantees termination: recursive calls will sort smaller array
// recursively sort elements on the left of pivotNewIndex
quicksort(array, left, pivotNewIndex - 1)
// recursively sort elements on the right of pivotNewIndex
quicksort(array, pivotNewIndex + 1, right)
int partition(int arr[], int l, int r, int pivot)
{ int pivot_val = arr[pivot]; int sorted_index = l, i; swap_arr(arr, pivot, r); for (i=l; i < r; ++i) { if (arr[i] <= pivot_val) { swap_arr(arr, i, sorted_index); sorted_index++; } } swap_arr(arr, sorted_index, r); return sorted_index; } void quick_sort(int arr[], int l, int r) { if (l < r) { int pivot = partition(arr, l, r, (l+r)/2); qsort_1(arr, l, pivot-1); qsort_1(arr, pivot+1, r);; } }
