Как я могу написать QuickSort без кэширования поворота? [закрыто] ⇐ C++

[Anonymous]

Рабочий алгоритм QuickSort будет кэшировать значение поворота для сравнения: < /p>

Код: Выделить всё

typedef unsigned uint;
#include 
#include 

uint partition(int *values, uint start, uint end) {
uint midpoint = (start + end) >> 1;
int pivot = values[midpoint];
for (;;) {
while (values[start] < pivot)
++start;
while (pivot < values[end])
--end;
if (start >= end)
return end;
std::swap(values[start++], values[end--]);
}
}

void quicksort(int *values, uint start, uint end) {
if (start >= end)
return;
uint mid = partition(values, start, end);
quicksort(values, start, mid);
quicksort(values, mid + 1, end);
}

int main() {
int numbers[] = {8, 63, 8, 36, 62, 20, 68, 21, 47, 83, 54, 54, 80, 15, 80, 73, 74, 39, 62, 89};
uint NUMBERS_SIZE = sizeof(numbers) / sizeof(int);
uint i = 0;

puts("UNSORTED: ");
for (i = 0; i < NUMBERS_SIZE; ++i) {
printf("%d ", numbers[i]);
}
putchar('\n');

quicksort(numbers, 0, NUMBERS_SIZE - 1);

puts("SORTED: ");
for (i = 0; i < NUMBERS_SIZE; ++i) {
printf("%d ", numbers[i]);
}
putchar('\n');
}

Моя проблема в том, что мне было назначено назначение для реализации QuickSort, но мне не дают необработанного массива. мне дают только непрозрачный тестовый тестировщик с Swap и сравните Метод:
class Tester {
private:
int *array;
public:
Tester(int *pointer) : array(pointer) {}
void swap(uint x, uint y) {
std::swap(array[x], array[y]);
}
int compare(uint x, uint y) {
return array[x] - array[y];
}
};
< /code>
typedef unsigned uint;
#include
#include

uint partition(Tester &tester, uint start, uint end) {
uint midpoint = (start + end) >> 1;
for (;;) {
while (tester.compare(start, midpoint) < 0)
++start;
while (tester.compare(midpoint, end) < 0)
--end;
if (start >= end)
return end;
tester.swap(start++, end--);
}
}

void quicksort(Tester &tester, uint start, uint end) {
if (start >= end)
return;
uint mid = partition(tester, start, end);
quicksort(tester, start, mid);
quicksort(tester, mid + 1, end);
}
< /code>
The problem is without being able to access the pivot value directly, and the pivot value might move, this produces incorrect results:
UNSORTED:
8 63 8 36 62 20 68 21 47 83 54 54 80 15 80 73 74 39 62 89
SORTED:
8 8 15 20 36 62 63 21 39 47 54 54 62 68 73 74 80 80 83 89
^ Bad
< /code>
How can I get around this?


Подробнее здесь: https://stackoverflow.com/questions/795 ... ivot-value