Quick Sort
CS/Algorithm 2010. 8. 3. 04:24function 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> |