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

Метод простых вставок предполагает разделение всего массива элементов на упорядоченную часть, которая вначале содержит лишь один элемент, и неупорядоченную. Очередной элемент из неупорядоченной части вставляется в определенное место упорядоченной части, проходя сравнение с ее элементами. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы "просеивать" выбранный элемент, сравнивая его с очередным элементом 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], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.

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

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

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

                                12     44                  18      55

                                               12     42     44     18      06     55     67     94

                                                                             18     44

                                                                                            06      44

                                            12     42    18       06      44     55     67     94

                                                                    18    42

                                                 06     42

                           12     18    06      42        44     55     67     94

                                        06    18

                           12     06    18      42        44     55     67     94

                               06     12

                                          06     12    18      42        44     55     67     94

Рисунок 6. Пример сортировки массива простым обменом

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

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