Вставка в связных списках

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

Public Sub LinkInsertionSort(ListTop As ListCell)

Dim new_top As New ListCell

Dim old_top As ListCell

Dim cell As ListCell

Dim after_me As ListCell

Dim nxt As ListCell

Set old_top = ListTop.NextCell

Do While Not (old_top Is Nothing)

Set cell = old_top

Set old_top = old_top.NextCell

‘ Найти, куда необходимо поместить элемент.

Set after_me = new_top

Do

Set nxt = after_me.NextCell

If nxt Is Nothing Then Exit Do

If nxt.Value >= cell.Value Then Exit Do

Set after_me = nxt

Loop

‘ Вставить элемент после позиции after_me.

Set after_me.NextCll = cell

Set cell.NextCell = nx

Loop

Set ListTop.NextCell = new_top.NextCell

End Sub

Т.к. этот алгоритм перебирает все элементы, может потребоваться сравнение каждого элемента со всеми элементами в отсортированном списке. В этом наихудшем случае вычислительная сложность алгоритма порядка O(N²).

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

В усредненном случае, алгоритму придется провести поиск примерно по половине отсортированного списка для того, чтобы найти местоположение элемента. При этом алгоритм выполняется примерно за 1 + 1 + 2 + 2 + … + N/2, или порядка O(N²) шагов.

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

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

Пузырьковая сортировка

Пузырьковая сортировка (bubblesort) — это алгоритм, предназначенный для сортировки списков, которые уже находятся в почти упорядоченном состоянии. Если в начале процедуры список полностью отсортирован, алгоритм выполняется очень быстро за время порядка O(N). Если часть элементов находятся не на своих местах, алгоритм выполняется медленнее. Если первоначально элементы расположены в случайном порядке, алгоритм выполняется за время порядка O(N²). Поэтому перед применением пузырьковой сортировки важно убедиться, что элементы в основном расположены по порядку.

При пузырьковой сортировке список просматривается до тех пор, пока не найдутся два соседних элемента, расположенных не по порядку. Тогда они меняются местами, и процедура продолжается дальше. Алгоритм повторяет этот процесс до тех пор, пока все элементы не займут свои места.

На рис. 9.2 показано, как алгоритм вначале обнаруживает, что элементы 6 и 3 расположены не по порядку, и поэтому меняет их местами. Во время следующего прохода, меняются местами элементы 5 и 3, в следующем — 4 и 3. После еще одного прохода алгоритм обнаруживает, что все элементы расположены по порядку, и завершает работу.

Можно проследить за перемещениями элемента, который первоначально был расположен ниже, чем после сортировки, например элемента 3 на рис. 9.2. Во время каждого прохода элемент перемещается на одну позицию ближе к своему конечному положению. Он движется к вершине списка подобно пузырьку газа, который всплывает к поверхности в стакане воды. Этот эффект и дал название алгоритму пузырьковой сортировки.

Можно внести в алгоритм несколько улучшений. Во‑первых, если элемент расположен в списке выше, чем должно быть, вы увидите картину, отличную от той, которая приведена на рис. 9.2. На рис. 9.3 показано, что алгоритм вначале обнаруживает, что элементы 6 и 3 расположены в неправильном порядке, и меняет их местами. Затем алгоритм продолжает просматривать массив и замечает, что теперь неправильно расположены элементы 6 и 4, и также меняет их местами. Затем меняются местами элементы 6 и 5, и элемент 6 занимает свое место.

При просмотре массива сверху вниз, элементы, которые перемещаются вверх, сдвигаются всего на одну позицию. Те же элементы, которые перемещаются вниз, сдвигаются на несколько позиций за один проход. Этот факт можно использовать для ускорения работы алгоритма пузырьковой сортировки. Если чередовать просмотр массива сверху вниз и снизу вверх, то перемещение элементов в прямом и обратном направлениях будет одинаково быстрым.

Во время проходов сверху вниз, наибольший элемент списка перемещается на место, а во время проходов снизу вверх — наименьший. Если M элементов списка расположены не на своих местах, алгоритму потребуется не более M проходов для того, чтобы расположить элементы по порядку. Если в списке N элементов, алгоритму потребуется N шагов для каждого прохода. Таким образом, полное время выполнения для этого алгоритма будет порядка O(M * N).

Если первоначально список организован случайным образом, большая часть элементов будет находиться не на своих местах. В примере, приведенном на рис. 9.3, элемент 6 трижды меняется местами с соседними элементами. Вместо выполнения трех отдельных перестановок, можно сохранить значение 6 во временной переменной до тех пор, пока не будет найдено конечное положение элемента. Это может сэкономить большое число шагов алгоритма, если элементы перемещаются на большие расстояния внутри массива.

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

Таким же образом, после прохода снизу вверх, можно сдвинуть позицию, с которой начнется очередной проход сверху вниз, и будут заканчиваться последующие проходы снизу вверх.

Реализация алгоритма пузырьковой сортировки на языке Visual Basic использует переменные min и max для обозначения первого и последнего элементов списка, которые находятся не на своих местах. По мере того, как алгоритма повторяет проходы по списку, эти переменные обновляются, указывая положение последней перестановки.

Public Sub Bubblesort(List() As Long, ByVal min As Long, ByVal max As Long)

Dim last_swap As Long

Dim i As Long

Dim j As Long

Dim tmp As Long

‘ Повторять до завершения.

Do While min < max

‘ «Всплывание».

last_swap = min - 1

‘ То есть For i = min + 1 To max.

i = min + 1

Do While i <= max

‘ Найти «пузырек».

If List(i - 1) > List(i) Then

‘ Найти, куда его поместить.

tmp = List(i - 1)

j = i

Do

List(j - 1) = List(j)

j = j + 1

If j > max Then Exit Do

Loop While List(j) < tmp

List(j - 1) = tmp

last_swap = j - 1

i = j + 1

Else

i = i + 1

End If

Loop

‘ Обновить переменную max.

max = last_swap - 1

‘ «Погружение».

last_swap = max + 1

‘ То есть For i = max -1 To min Step -1

i = max - 1

Do While i >= min

‘ Найти «пузырек».

If List(i + 1) < List(i) Then

‘ Найти, куда его поместить.

tmp = List(i + 1)

j = i

Do

List(j + 1) = List(j)

j = j - 1

If j < min Then Exit Do

Loop While List(j) > tmp

List(j + 1) = tmp

last_swap = j + 1

i = j - 1

Else

i = i - 1

End If

Loop

‘ Обновить переменную min.

Min = last_swap + 1

Loop

End Sub

Для того чтобы протестировать алгоритм пузырьковой сортировки при помощи программы Sort, поставьте галочку в поле Sorted (Отсортированные) в области Initial Ordering (Первоначальный порядок). Введите число элементов в поле #Unsorted (Число несортированных). После нажатия на кнопку Go (Начать), программа создает и сортирует список, а затем переставляет случайно выбранные пары элементов. Например, если вы введете число 10 в поле #Unsorted, программа переставит 5 пар чисел, то есть 10 элементов окажутся не на своих местах.

Для второго варианта первоначального алгоритма, программа сохраняет элемент во временной переменной при перемещении на несколько шагов. Этот происходит еще быстрее, если использовать функцию API MemCopy. Алгоритм пузырьковой сортировки в программе FastSort, используя функцию MemCopy, сортирует элементы в 50 или 75 раз быстрее, чем первоначальная версия, реализованная в программе Sort.

В табл. 9.2 приведено время выполнения пузырьковой сортировки 2000 элементов на компьютере с процессором Pentium с тактовой частотой 90 МГц в зависимости от степени первоначальной упорядоченности списка. Из таблицы видно, что алгоритм пузырьковой сортировки обеспечивает хорошую производительность, только если список с самого начала почти отсортирован. Алгоритм быстрой сортировки, который описывается далее в этой главе, способен отсортировать тот же список из 2000 элементов примерно за 0,12 сек, независимо от первоначального порядка расположения элементов в списке. Пузырьковая сортировка может превзойти этот результат, только если примерно 97 процентов списка было упорядочено до начала сортировки.

Несмотря на то, что пузырьковая сортировка медленнее, чем многие другие алгоритмы, у нее есть свои применения. Пузырьковая сортировка часто дает наилучшие результаты, если список изначально уже почти упорядочен. Если программа управляет списком, который сортируется при создании, а затем к нему добавляются новые элементы, пузырьковая сортировка может быть лучшим выбором.