Минимумды табу арқылы сұрыптау және қарапайым орын ауыстырып сұрыптау алгоритмдерінің айырмашылықтары

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

После k-го хода результат содержит k чисел, а исходный набор — N-k. Договоримся, что текущий результат мы будем хранить в первых k элементах массива. Разберем подробнее, как это можно реализовать. Для этого вновь обратимся к нашему примеру:3, 6, 1, 2, 9, 5.

На первом шаге мы находим наименьшее число — 1 — и должны переместить его на первое место. Но там уже записано число 3, куда же его деть? Ответ прост: на место числа 1. Таким образом, мы просто меняем местами два элемента массива:1 | 6, 3, 2, 9, 5.

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

На втором шаге мы находим минмиальное число в правой части — среди элементов массива со 2-го по 6-й (в общем случае — по N-й) — и меняем его местами с числом, стоящим на втором месте:1, 2 | 3, 6, 9, 5.

Далее нам следует поставить следующее минимальное число — 3 — на третье место, но оно уже и так там стоит. Впрочем, мы не будем обращать на это внимание, и просто как бы поменяем его само с собой:1, 2, 3 | 6, 9, 5.

Попробуем записать действия, которые нам предстоит проделать на шаге с номером k. Сначала нам нужно найти наименьшее среди чисел, записанных в k, k+1, ..., N позициях массива. После этого нам нужно поменять этот элемент с k-м.

Сколько таких шагов нужно сделать, чтобы полностью отсортировать массив? Напрашивается ответ "N", но не будем торопиться. Пусть сделан N-1 шаг. Тогда в правой, неотсортированной части массива останется одно число. Какое это число? Ясно, что это самое большое число в массиве. Где оно в итоге должно оказаться? На последнем месте в массиве. Но оно уже и так там! Поэтому N-й шаг алгоритма выполнять не нужно.

Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

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