Сортировка вставкой – еще один алгоритм сложности O(N2). Основан на внедрении в отсортированную часть массива элемента, следующего за этой частью, если он удовлетворяет условию сортировки. Алгоритм просматривает исходный список в порядке возрастания и ищет место, где необходимо вставить новый элемент. Затем он помещает новый элемент в найденную позицию.
На первом проходе второй элемент сравнивается с первым, на втором – третий элемент сравнивается с первым и вторым и т.д. Если проверяемый i+1-ый элемент удовлетворяет условию сортировки среди i элементов, то он вставляется на j-е место без нарушения порядка, т.е. элементы с индексами >=j и <=i-1 увеличивают свой индекс на 1.
For i = 2 To n 'сравнение всегда начинается b = a(i): j = 1 'с первого Do While b > a(j) 'определяется номер j = j + 1 'для вставки Loop For k = i To j + 1 Step –1 'освобождается a(k) = a(k - 1) 'место для вставки Next k a(j) = b 'осуществляется вставка For l = 1 To n Picture2.Print a(l); " "; Next Picture2.Print Next I End Sub
Всего проходов n-1.
Подобный алгоритм много времени тратит на поиск правильной позиции для нового элемента. Работает медленнее, чем сортировка выбором.
Пузырьковая сортировка – это алгоритм, предназначенный для сортировки списков, которые уже находятся в почти упорядоченном состоянии. Если это условие выполнено, то алгоритм выполняется очень быстро, за время порядка O(N). Если элементы изначально расположены в произвольном порядке, алгоритм выполняется за O(N2) шагов.
При пузырьковой сортировке список просматривается до тех пор, пока не найдутся два смежных элемента, которые следуют не по порядку. Они меняются местами, и список продолжает исследоваться дальше. После первого прохода на первом месте (по возрастанию) окажется самый маленький элемент. Следующий проход будет осуществляться до этого элемента, т.е. сортируется оставшаяся часть массива. Алгоритм повторяет этот процесс, пока не упорядочит все элементы.
Суть сортировки:
N элементов массива разбивается на K групп, причем в группе не более 2 элементов, элементы располагаются на расстоянии D друг от друга. D – шаг группы.
Производится сортировка в группах.
Шаг группы D уменьшается вдвое.
Повторяются пункты 2 – 3 до тех пор, пока шаг не станет меньше 1.
2 4 5 3 10 8 1
В разных вариантах метода Шелла может быть задана разная последовательность уменьшения шагов и способов определения начального значения D.Начальное значение шага D можно задать, как степень числа 2, таким образом, что D ≥ N/2. При больших значениях N время сортировки методом Шелла значительно меньше, чем в методе пузырька.
d = 1
Do While n > d
d = 2 * d
Loop
d = Int((d - 1) / 2)
Do While d <> 0
Picture2.Print " d= "; d
For i = 1 To n - d
For j = i To 1 Step -d
l = j + d
If a(l) <= a(j) Then
buf = a(j)
a(j) = a(l)
a(l) = buf
End If
Next
Picture1.Print a(i);
Next
Picture1.Print
d = Int((d - 1) / 2)
Loop
For i = 1 To n
Picture1.Print a(i);
Next
Пирамидальная сортировка (бинарные деревья)
Пирамида – полное двоичное дерево, в котором каждый узел больше, чем его два дочерних. Оба дочерних узла, должны быть меньше, чем родительский, но любой из них может быть больше другого. Корневой узел всегда самый большой в пирамиде.
Любой массив можно представить в виде пирамиды, поместив первый элемент массива в корень пирамиды.
Например, 2 4 5 3 10 8 1
Поддерево, начинающееся в любом узле пирамиды, тоже является пирамидой.
Используя этот факт, можно построить пирамиду снизу вверх. Из каждого из поддеревьев с тремя узлами нужно сформировать пирамиду. Для этого нужно сравнить верхний узел с двумя его дочерними. Если любой из дочерних узлов больше, нужно поменять его с верхним узлом. Если оба дочерних узла больше, нужно поменять родительский с большим из дочерних. Этот шаг повторяется до тех пор, пока все поддеревья не станут пирамидами:
Затем, создаются более крупные пирамиды: маленькие пирамиды с вершинами 10 и 8 объединяются с элементом 2.
В итоге на самой вершине пирамиды оказывается максимальный элемент последовательности. Выкидываем его из пирамиды, а на его место ставим крайний справа элемент на нижнем уровне. Из оставшихся элементов снова строим пирамиду. На вершине получаем следующий наибольший элемент и т. д.
Затем, создаются более крупные пирамиды: маленькие пирамиды с вершинами 10 и 8 объединяются с элементом 2.