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)01 | void quick_sort(int arr[], int l, int r) |
02 | { |
03 | if (l < r) { |
04 | int i=l, j=r, pivot=l+(r-l)/2; |
05 | while (i < j) { |
06 | while (i < pivot && arr[i] <= arr[pivot]) |
07 | ++i; |
08 | while (j > pivot && arr[j] >= arr[pivot]) |
09 | --j; |
10 | swap_arr(arr, i, j); |
11 | ++i, --j; |
12 | if (i-1 == pivot) |
13 | pivot = j = j+1; |
14 | else if (j+1 == pivot) |
15 | pivot = i = i-1; |
16 | } |
17 | qsort_2(arr, l, pivot-1); |
18 | qsort_2(arr, pivot+1, r); |
19 | } |
20 | } |
// 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)
01 | int partition(int arr[], int l, int r, int pivot)<br> |
02 | { |
03 | int pivot_val = arr[pivot]; |
04 | int sorted_index = l, i; |
05 | swap_arr(arr, pivot, r); |
06 |
07 | for (i=l; i < r; ++i) { |
08 | if (arr[i] <= pivot_val) { |
09 | swap_arr(arr, i, sorted_index); |
10 | sorted_index++; |
11 | } |
12 | } |
13 | swap_arr(arr, sorted_index, r); |
14 | return sorted_index; |
15 | } |
16 |
17 | void quick_sort(int arr[], int l, int r) |
18 | { |
19 | if (l < r) { |
20 | int pivot = partition(arr, l, r, (l+r)/2); |
21 | qsort_1(arr, l, pivot-1); |
22 | qsort_1(arr, pivot+1, r);; |
23 | } |
24 | }<p></p> |