Сортировка вставками с линейным поиском

Она же «Insertion sort». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n-1)}{2})[/math], в среднем ― [math]O(\frac{n\cdot(n-1)}{1.3})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(n\cdot(n-1))[/math]. Для вставки используется буферная область памяти, в которой хранится элемент, еще не вставленный на свое место (так называемый «ключ»). Сам ключ отправляется в буфер, в результате в массиве появляется свободная ячейка — это позволяет сдвигать элементы и освободить точку вставки. В подмассиве, начиная с конца отрезка, перебираются элементы, которые сравниваются с ключом. Если элементы больше ключа, тогда они сдвигаются на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключу, тогда в текущую свободную ячейку вставляется ключевой элемент.

В аттаче asm-/rc-/exe-файлы и курсор

 

Сортировка вставками с бинарным поиском

Она же «Insertion sort (binary search)». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем (полностью отсортированный массив), в среднем и в худшем случае (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.97})[/math]. Место для вставки обнаруживается с помощью бинарного поиска. Наблюдается небольшое приращение скорости для среднего случая по сравнению с сортировкой простыми вставками с линейным поиском.

В аттаче asm-/rc-/exe-файлы и курсор

 

Сортировка парными вставками

Она же «Pairwise Insertion Sort». Относится к классу «сортировок со вставками». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n−1)}{18.9})[/math], в среднем ― [math]O(\frac{n\cdot(n−1)}{3.3})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.9})[/math]. Количество элементов в массиве [math]n[/math] должно быть нечетным. В буфер отправляются два рядом стоящих элемента. Элемент с бòльшим значением выставляется ближайшим к отсортированному подмассиву. Сперва метод простой вставки применяется к бòльшему элементу из пары. Место для вставки обнаруживается с помощью бинарного поиска. Затем метод простой вставки применяется к меньшему элементу из пары. Так как меньший элемент обрабатывается после вставки бòльшего, поэтому при поиске места вставки пропускается область, в которую произошла вставка бòльшего элемента. Это сокращает расходы на обработку меньшего элемента из пары.

В аттаче asm-/rc-/exe-файлы и курсор

 

Голубиная сортировка

Она же «Pigeonhole Sort», она же «Сортировка Дирихле», она же «сортировка по полочкам», она же «групповая сортировка». Относится к классу «сортировок с распределением».

Pigeon(голубь)+hole (дыра)=Pigeonhole​	жопа голубя
	отделение для бумаг
	закуток
	голубиное гнездо
	раскладывать по ящикам
	небольшое углубление для гнезда домашнего голубя
	абонентская ячейка на почте или банковская ячейка в банке
	категория, обычно чрезмерно ограничительная, к которой относят кого-то или что-то.
	положить (документ) в ячейку

Сложность сортировки в лучшем, среднем и в худшем случае [math]O(n+k)[/math], где [math]n[/math] ― размер массива, [math]k[/math] ― ранг массива. Первый раз проходим по массиву и находим минимальный и максимальный элементы массива. Вычисляем ранг массива [math]k=max-min+1[/math], заводим [math]k[/math] счетчиков. Второй раз проходим по массиву, от значения каждого элемента отнимаем значение [math]min[/math] и инкрементируем соответствующий счетчик. Подсчитываем сколько раз в массиве счетчиков встречается каждое значение, пропускаем счетчики заполненные нулем и заполняем исходный массив элементами равными (номер счетчика+значение [math]min[/math]) в соответствующих количествах.

В аттаче asm-/rc-/exe-файлы и курсор

 

Двухсторонняя сортировка выбором

Она же «Double Selection Sort». Относится к классу «сортировок выбором». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n−1)}{1.93})[/math], в среднем ― [math]O(\frac{n\cdot(n−1)}{1.92})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{0.97})[/math]. При проходе по массиву, отыскиваются максимум и минимум. Минимум устанавливается на первое место, максимум на последнее. Еще раз проходим по неотсортированной части массива (от второго элемента до предпоследнего) и опять находим в ней максимум и минимум, которые меняем со вторым и предпоследним элементом. Неотсортированная часть с каждым проходом уменьшается сразу на два элемента. Проходы продолжаются, пока массив не отсортируется полностью. По сравнению с обычной сортировкой выбором количество сравнений увеличилось в 2 раза, число перестановок осталось неизменным. Двухсторонний выбор незначительно увеличивает скорость сортировки. Возможна коллизия ― когда вместо найденного максимума оказался элемент, появившийся при обмене минимального и первого элемента массива. В таком случае проход с поиском минимального и максимального элемента повторяется.

В аттаче asm-/rc-/exe-файлы и курсор

 

Бинго-сортировка

Она же «Bingo Sort». Относится к классу «сортировок выбором». Сложность сортировки в лучшем случае (полностью отсортированный массив) [math]O(\frac{n\cdot(n−1)}{1.9})[/math], в среднем ― [math]O(\frac{n\cdot(n−1)}{2.2})[/math], в худшем (массив отсортирован в обратную сторону) ― [math]O(\frac{n\cdot(n−1)}{1.9})[/math]. Модификация простой сортировки выбором, позволяющая быстрее сортировать массивы, состоящие из повторяющихся элементов. В неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации. Это позволяет не искать повторяющиеся максимумы заново, а ставить их на свое место сразу, как только максимум в очередной раз встретили в массиве.

В аттаче asm-/rc-/exe-файлы и курсор.