Как вы можете гарантировать, что быстрая сортировка отсортирует массив целых чисел?

Question

Меня спросили об этом в лекции ... немного озадачил.

как вы можете гарантировать, что быстрая сортировка всегда будет сортировать массив целых чисел?

Спасибо.

Answer 1

безвозмездно плагиат Википедия :

Правильность алгоритма разбиения основана на следующем два аргумента:

• На каждой итерации все элементы, обработанные до сих пор находятся в желаемом положении: до точки поворота, если меньше точки поворота значение, после разворота, если оно больше значения поворота (цикл инвариант).
• Каждая итерация оставляет меньше элементов для обработки. (вариант петли).

Корректность общего алгоритма может быть доказана по индукции: для нуля или одного элемента алгоритм оставляет данные без изменений; для большего набора данных он производит объединение двух части, элементы меньше, чем стержень, и элементы больше его, сами отсортированы по рекурсивной гипотезе.

Answer 2

Функция быстрой сортировки, принимая сводное значение и сортируя оставшиеся данные по двум группам. Один выше, а другой ниже. Затем вы делаете это для каждой группы по очереди, пока не получите группы не больше одной. На этом этапе вы можете гарантировать, что данные отсортированы, потому что вы можете гарантировать, что любое значение сводки находится в правильном месте, потому что вы сравнили его непосредственно с другим значением сводки, которое также находится в правильном месте. В конце концов, у вас остаются наборы размером 1 или размером 0, которые не могут быть отсортированы, поскольку они не могут быть переставлены и, следовательно, уже отсортированы.

Надеюсь, это поможет, это то, чему нас учили для A Level Дополнительная математика (16-18, Великобритания).

Answer 3

Ваш профессор может иметь в виду "стабильность".Посмотрите здесь: http://en.wikipedia.org/wiki/Stable_sort#Stability. Стабильные алгоритмы сортировки поддерживают относительный порядок записей с одинаковыми ключами.Если все ключи различны, тогда это различие не является обязательным.

Быстрая сортировка (в эффективных реализациях) не является стабильной сортировкой, поэтому одним из способов обеспечения стабильности было бы убедиться, что в вашем массиве нет повторяющихся целых чисел.