Зміна порядку дублікатів після сортування за допомогою алгоритму Quicksort - алгоритм, сортування, структури даних, квакспорт

Я читав де-небудь (вибачення, що я не пам'ятаю, де), що правильний алгоритм сортування повинен сортувати дублюючі значення в тому порядку, в якому вони з'являються в несортированной послідовності.

Приклад:

5 (A), 2, 4, 5 (B), 6, 5 (C), 1, 3

5 (A / B / C): Тут A, B & C використовується тільки для позначення порядку 5 с.

5 (A): Перші 5 з трьох 5 "s

5 (B): Другий 5 з трьох 5 "s

5 (C): Третій 5 з трьох 5 "s

Після сортування наведений вище список має бути:

1, 2, 3, 4, 5 (A), 5 (B), 5 (C), 6

Але Quicksort дає наступну сортовану послідовність:

1, 2, 3, 4, 5 (С), 5 (А), 5 (В), 6

Код:

void sort(int[] array, int startIndex, int endIndex){
int right = endIndex;
int pivot = array[(startIndex+endIndex)/2];
int left = startIndex;
int temp;
while(left <= right){
while(array[right] > pivot){
right--;
}
while(array[left] < pivot){
left++;
}
if(left <= right){
temp = array[right];
array[right] = array[left];
array[left] = temp;
left++;
right--;
}
}
if(startIndex < right) {
sort(array, startIndex, right);
}
if(endIndex > left) {
sort(array, left, endIndex);
}
}

Чи правильна ця поведінка? Якщо ні, то що може бути зроблено, щоб мати правильний висновок, в якому впорядковані дублюючі елементи такі ж, як у несортированной послідовності?

EDIT:

Називається алгоритм, який підтримує відносну впорядкованість повторюваних елементів "Стабільний сорт". як повідомив Дюкелінг в коментарях.

Відповіді:

1 для відповіді № 1

Quicksort не є стабільним алгоритмом. Якщо ви бажаєте зберегти порядок сортування, використовуйте стабільний алгоритм. Злиття є стабільним алгоритмом сортування.

---