Существует два типа алгоритма сортировки: стабильный и нет. Стабильные сортировки поддерживают порядок элементов, которые считаются равными, тогда как нестабильные сортировки не дают таких гарантий.
Так что, если у нас есть небольшой набор неупорядоченных карт, и мы сортируем по пипсам, игнорируя масти, следующий неупорядоченный список:
3♠ 2♣ 3♦ 2♥ 3♣
будет стабильно отсортирован как:
2♣ 2♥ 3♠ 3♦ 3♣
так как 2 из клубов появились перед 2 из сердец в первоначальном списке, и 3 из них также поддерживаются в первоначальном порядке (пики, алмазы, булавы). Нестабильная сортировка (примером которой является самая известная сортировка, quicksort) ничего не гарантирует в отношении порядка 2 или 3, только то, что 2 появляются перед 3.
Хорошей стабильной сортировкой является вставная сортировка. Вот как вы сортируете карты, скажем, для бриджа. Вы начинаете с левой стороны, сортируете первые две карты, а затем прокладываете карты по порядку вправо, вставляя следующую карту в правильной последовательности в уже отсортированные карты. Вот как сортировка вставок будет работать последовательно на наших оригинальных перемешанных картах:
3♠ | 2♣ 3♦ 2♥ 3♣ 2♣ 3♠ | 3♦ 2♥ 3♣ 2♣ 3♠ 3♦ | 2♥ 3♣ 2♣ 2♥ 3♠ 3♦ | 3♣ 2♣ 2♥ 3♠ 3♦ 3♣
Я указал вертикальной чертой разделение между отсортированной частью и несортированной частью.
Для удобства, вот сортировка вставки в массив, реализованный в JavaScript:
var insertionSort = function (a) {
var i, j, temp;
for (i = 1; i < a.length; i++) {
temp = a[i];
j = i;
while ((j > 0) && (temp < a[j - 1])) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
};
Обратите внимание, что у нас есть двойной тест для внутреннего цикла. Первое условие — убедиться, что мы не запустили начало массива, а второе — остановить цикл, как только мы достигнем правильного места, чтобы вставить элемент. Мы считаем справа во внутреннем цикле, чтобы обеспечить стабильность сортировки (мы не хотим находить первый из набора равных элементов, мы хотим найти последний ).
Интересно, что сортировка вставками заключается в том, что, несмотря на то, что это официально алгоритм O ( n 2 ) — в цикле есть цикл — он имеет лучшее (среднее) поведение O ( n ), если элементы почти отсортирован. Это свойство означает, что сортировка вставкой часто используется для ускорения других алгоритмов, таких как быстрая сортировка: вы выполняете быструю сортировку до тех пор, пока размер разделов не составит около 8 элементов, а затем вставка сортирует весь массив. Это имеет тенденцию быть быстрее, чем просто позволить быстрой сортировке завершить разделы из одного элемента.
Глядя на код для сортировки вставкой, не было бы неплохо, если бы у нас не было двойного условного теста? Это не помогло бы без конца в простом случае использования сортировки вставкой для завершения алгоритма «почти сортировки»: в большинстве случаев проверка на отсутствие запуска массива совершенно не нужна. Итак, в моей книге я добавил оптимизацию поиска наименьшего элемента в массиве и замены его на первый элемент, а затем выполнил стандартную сортировку вставки. Так как самый маленький предмет действует как страж , я мог бы избавиться от двойного условия во внутреннем цикле. Мой внутренний цикл никогда не выйдет за пределы массива: страж должен быть самым маленьким элементом.
var insertionSort = function (a) {
var i, j, temp;
j = 0;
for (i = 1; i < a.length; i++) {
if (a[i] < a[j]) {
j = i;
}
}
temp = a[0];
a[0] = a[j];
a[j] = temp;
for (i = 1; i < a.length; i++) {
temp = a[i];
j = i;
while (temp < a[j - 1]) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
};
И это продолжалось целых десять лет, пока пару дней назад я не получил письмо, в котором говорилось, что мой вид вставки был сломан. Ерунда, сказал я, смотри: все вроде отлично и денди. Не так, ответил мой корреспондент, вы нарушили стабильность сортировки вставок. На что меня воспитали коротко. Он был прав: моя эффективная реализация сортировки вставками больше не была стабильной.
Вот пример проблемы с картами. Предположим, мы начнем с этого:
5♠ 5♣ 2♦ 2♥ 3♣
При первом прохождении через мою сортировку вставки 5 пиков с первым появлением наименьшего элемента, 2 бриллиантов:
2♦ 5♣ 5♠ 2♥ 3♣
И тогда сортировка вставки будет продолжаться со сторожем, чтобы дать это:
2♦ 2♥ 3♣ 5♣ 5♠
Но обратите внимание: 5 пиков и 5 клубов уже не в своем первоначальном порядке. Стабильность была нарушена. Небольшая эффективность поиска и настройки часового сломала алгоритм.
Я полагаю, что здесь есть два решения: во-первых, не использовать улучшение скорости и придерживаться стандартной сортировки вставки, а во-вторых, удалить наименьший элемент из массива и вставить его в первую позицию (или, эквивалентно, перемешать все предметы по порядку между первой позицией и местом, где был найден самый маленький предмет). Любой из них будет работать нормально, и обратите внимание, что второй по-прежнему процесс O ( n ), который меньше, чем общий вид O ( n 2 ).
Конечно, другая вещь, которую нужно сделать, это полностью игнорировать проблему. Я использовал оптимизированную сортировку вставок главным образом как последний шаг к реализации эффективной быстрой сортировки. Поскольку быстрая сортировка нестабильна по определению, не имеет значения, что оптимизированная сортировка вставок также нестабильна.
Еще одно замечание: за все мои годы программирования я никогда не полагался на стабильность. Это просто никогда не подходит. Если исходный заказ имел значение, то должен быть способ изменить сравнение, чтобы учесть исходный порядок (например, для карт вы также можете отсортировать по масти). Используя этот метод улучшения сравнения, вы даже можете сделать быструю сортировку стабильной (существенно различая все дублирующиеся элементы). Поэтому, хотя технически моя оптимизированная сортировка вставок не содержит ошибок, она достаточно хороша для моего использования.