Сортировка массива простыми включениями

Метод простых вставок предполагает разделение всего массива элементов на упорядоченную часть, которая вначале содержит лишь один элемент, и неупорядоченную. Очередной элемент из неупорядоченной части вставляется в определенное место упорядоченной части, проходя сравнение с ее элементами. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы " просеивать" выбранный элемент, сравнивая его с очередным элементом a [j] и либо вставляя, либо пересылая a [i] направо и продвигаясь налево. Заметим, что " просеивание" может закончиться при двух различных условиях: найден элемент a [j] с ключом меньшим, чем ключ x или достигнут левый конец готовой последовательности.

При этом упорядоченная часть удлиняется на один элемент. Сортировка заканчивается при окончании неупорядоченной части.

При данной сортировке общее число сравнений приблизительно равно

,

При этом требуется количество проходов по данным P

Рисунок 5. Пример сортировки массива простыми включениями

Число Ci сравнений ключей при i-м просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число Мi пересылок (присваиваний) равно Ci+2 (учитывая барьер). Поэтому общее число сравнений и пересылок есть

Cmin = n-1 Mmin = 2 (n-1)

Cср. = (n2+n-2) /4 Mср. = (n2+9n-10) /4

Cmax = ((n2+n) - 1) /2 Mmax = (n2+3n-4) /2.

Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a [1], …, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.

Сортировка массива простым обменом (" метод пузырька")

Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива.

Очевидно, что в наихудшем случае, когда минимальное значение ключа элемента имеется у самого правого элемента, число просмотров равно size − 1.

ффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное − size -1, а среднее − size/2.

Следовательно,