| 1080 | //--------------------------------------------------------------quick_sort |
| 1081 | template <class Array, class Less> |
| 1082 | void quick_sort(Array& arr, Less less) |
| 1083 | { |
| 1084 | if (arr.size() < 2) |
| 1085 | return; |
| 1086 | |
| 1087 | typename Array::value_type* e1; |
| 1088 | typename Array::value_type* e2; |
| 1089 | |
| 1090 | int stack[80]; |
| 1091 | int* top = stack; |
| 1092 | int limit = arr.size(); |
| 1093 | int base = 0; |
| 1094 | |
| 1095 | for (;;) |
| 1096 | { |
| 1097 | int len = limit - base; |
| 1098 | |
| 1099 | int i; |
| 1100 | int j; |
| 1101 | int pivot; |
| 1102 | |
| 1103 | if (len > quick_sort_threshold) |
| 1104 | { |
| 1105 | // we use base + len/2 as the pivot |
| 1106 | pivot = base + len / 2; |
| 1107 | swap_elements(arr[base], arr[pivot]); |
| 1108 | |
| 1109 | i = base + 1; |
| 1110 | j = limit - 1; |
| 1111 | |
| 1112 | // now ensure that *i <= *base <= *j |
| 1113 | e1 = &(arr[j]); |
| 1114 | e2 = &(arr[i]); |
| 1115 | if (less(*e1, *e2)) |
| 1116 | swap_elements(*e1, *e2); |
| 1117 | |
| 1118 | e1 = &(arr[base]); |
| 1119 | e2 = &(arr[i]); |
| 1120 | if (less(*e1, *e2)) |
| 1121 | swap_elements(*e1, *e2); |
| 1122 | |
| 1123 | e1 = &(arr[j]); |
| 1124 | e2 = &(arr[base]); |
| 1125 | if (less(*e1, *e2)) |
| 1126 | swap_elements(*e1, *e2); |
| 1127 | |
| 1128 | for (;;) |
| 1129 | { |
| 1130 | do |
| 1131 | i++; |
| 1132 | while (less(arr[i], arr[base])); |
| 1133 | do |
| 1134 | j--; |
| 1135 | while (less(arr[base], arr[j])); |
| 1136 | |
| 1137 | if (i > j) |
| 1138 | { |
| 1139 | break; |
no test coverage detected