Quicksortblätter blätter oft ein Element ungeortiert [geschlossen] ⇐ C++

[Anonymous]

Ich habe den folgenden Code für QuickSort geschrieben: < /p>

Code: Select all

typedef unsigned uint;
#include 
#include 

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

void quickSort(int *tester, uint start, uint end) {
if (start >= end)
return;
uint mid = partition(tester, start, end);
quickSort(tester, start, mid);
quickSort(tester, 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');
}
< /code>
Mein [url=viewtopic.php?t=20324]Problem[/url] ist, dass dies oft ein oder mehrere Elemente nicht ungewöhnlich bleibt: < /p>
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

Ich erhielt den folgenden Pseudocode und versuchte es am besten, dies an realen Code anzupassen, der nur Swap verwendet und vergleichen kann, ohne die tatsächlichen Werte zu betrachten:

Code: Select all

Partition(numbers, lowIndex, highIndex) {
// Pick middle element as pivot
midpoint = lowIndex + (highIndex - lowIndex) / 2
pivot = numbers[midpoint]

done = false
while (!done) {
// Increment lowIndex while numbers[lowIndex] < pivot
while (numbers[lowIndex] < pivot) {
lowIndex += 1
}

// Decrement highIndex while pivot < numbers[highIndex]
while (pivot < numbers[highIndex]) {
highIndex -= 1
}

// If zero or one elements remain, then all numbers are
// partitioned. Return highIndex.
if (lowIndex >= highIndex) {
done = true
}
else {
// Swap numbers[lowIndex] and numbers[highIndex]
temp = numbers[lowIndex]
numbers[lowIndex] = numbers[highIndex]
numbers[highIndex] = temp

// Update lowIndex and highIndex
lowIndex += 1
highIndex -= 1
}
}

return highIndex
}

Quicksort(numbers, lowIndex, highIndex) {
// Base case: If the partition size is 1 or zero
// elements, then the partition is already sorted
if (highIndex