[3] | 1 | #include <functional> |
---|
| 2 | // #include <algorithm> |
---|
| 3 | // #include <iterator> |
---|
| 4 | // #include <iostream> |
---|
| 5 | |
---|
| 6 | void swap(float &a, float &b) |
---|
| 7 | { |
---|
| 8 | float t=a; a=b; b=t; |
---|
| 9 | } |
---|
| 10 | |
---|
| 11 | void sort(float *array, int begin, int end) { |
---|
| 12 | float pivot = array[begin]; |
---|
| 13 | int i = begin + 1, j = end, k = end; |
---|
| 14 | float t; |
---|
| 15 | |
---|
| 16 | while (i < j) { |
---|
| 17 | if (array[i] < pivot) i++; |
---|
| 18 | else if (array[i] > pivot) { |
---|
| 19 | j--; k--; |
---|
| 20 | t = array[i]; |
---|
| 21 | array[i] = array[j]; |
---|
| 22 | array[j] = array[k]; |
---|
| 23 | array[k] = t; } |
---|
| 24 | else { |
---|
| 25 | j--; |
---|
| 26 | swap(array[i], array[j]); |
---|
| 27 | } } |
---|
| 28 | i--; |
---|
| 29 | swap(array[begin], array[i]); |
---|
| 30 | if (i - begin > 1) |
---|
| 31 | sort(array, begin, i); |
---|
| 32 | if (end - k > 1) |
---|
| 33 | sort(array, k, end); |
---|
| 34 | } |
---|
| 35 | |
---|
| 36 | void sort(float *array, float *matchingArray, int begin, int end) |
---|
| 37 | { |
---|
| 38 | float pivot = array[begin]; |
---|
| 39 | int i = begin + 1, j = end, k = end; |
---|
| 40 | float t; |
---|
| 41 | |
---|
| 42 | while (i < j) { |
---|
| 43 | if (array[i] < pivot) i++; |
---|
| 44 | else if (array[i] > pivot) { |
---|
| 45 | j--; k--; |
---|
| 46 | t = array[i]; |
---|
| 47 | array[i] = array[j]; |
---|
| 48 | array[j] = array[k]; |
---|
| 49 | array[k] = t; |
---|
| 50 | t = matchingArray[i]; |
---|
| 51 | matchingArray[i] = matchingArray[j]; |
---|
| 52 | matchingArray[j] = matchingArray[k]; |
---|
| 53 | matchingArray[k] = t; |
---|
| 54 | } |
---|
| 55 | else { |
---|
| 56 | j--; |
---|
| 57 | swap(array[i], array[j]); |
---|
| 58 | swap(matchingArray[i], matchingArray[j]); |
---|
| 59 | } |
---|
| 60 | } |
---|
| 61 | i--; |
---|
| 62 | swap(array[begin], array[i]); |
---|
| 63 | swap(matchingArray[begin], matchingArray[i]); |
---|
| 64 | if (i - begin > 1) |
---|
| 65 | sort(array, matchingArray, begin, i); |
---|
| 66 | if (end - k > 1) |
---|
| 67 | sort(array, matchingArray, k, end); |
---|
| 68 | } |
---|
| 69 | |
---|
| 70 | |
---|
| 71 | |
---|
| 72 | |
---|
| 73 | // template< typename BidirectionalIterator, typename Compare > |
---|
| 74 | // void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) { |
---|
| 75 | // if( first != last ) { |
---|
| 76 | // BidirectionalIterator left = first; |
---|
| 77 | // BidirectionalIterator right = last; |
---|
| 78 | // BidirectionalIterator pivot = left++; |
---|
| 79 | |
---|
| 80 | // while( left != right ) { |
---|
| 81 | // if( cmp( *left, *pivot ) ) { |
---|
| 82 | // ++left; |
---|
| 83 | // } else { |
---|
| 84 | // while( (left != --right) && cmp( *pivot, *right ) ) |
---|
| 85 | // ; |
---|
| 86 | // std::iter_swap( left, right ); |
---|
| 87 | // } |
---|
| 88 | // } |
---|
| 89 | |
---|
| 90 | // --left; |
---|
| 91 | // std::iter_swap( first, left ); |
---|
| 92 | |
---|
| 93 | // quick_sort( first, left, cmp ); |
---|
| 94 | // quick_sort( right, last, cmp ); |
---|
| 95 | // } |
---|
| 96 | // } |
---|
| 97 | |
---|
| 98 | // template< typename BidirectionalIterator > |
---|
| 99 | // inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) { |
---|
| 100 | // quick_sort( first, last, |
---|
| 101 | // std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >() |
---|
| 102 | // ); |
---|
| 103 | // } |
---|
| 104 | |
---|
| 105 | |
---|
| 106 | |
---|
| 107 | |
---|
| 108 | // void sort(float *arr, int beg, int end) |
---|
| 109 | // { |
---|
| 110 | // if (end > beg + 1) |
---|
| 111 | // { |
---|
| 112 | // float piv = arr[beg]; |
---|
| 113 | // int l = beg + 1, r = end; |
---|
| 114 | // while (l < r) |
---|
| 115 | // { |
---|
| 116 | // if (arr[l] <= piv) |
---|
| 117 | // l++; |
---|
| 118 | // else |
---|
| 119 | // swap(arr[l], arr[--r]); |
---|
| 120 | // } |
---|
| 121 | // swap(arr[--l], arr[beg]); |
---|
| 122 | // sort(arr, beg, l); |
---|
| 123 | // sort(arr, r, end); |
---|
| 124 | // } |
---|
| 125 | // } |
---|
| 126 | |
---|