Демонстрационная программа сортировки методом «пузырёк»

Общие сведения о сортировке данных

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

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

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

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

Демонстрационная программа сортировки методом «пузырёк»

Сортировка методом простого обмена, или пузырьковая сортировка, может быть использована практически для любых массивов. Данный метод состоит в последовательных просмотрах массива и осуществлении обмена местами между соседними элементами, которые расположены в «неверном» порядке, то есть такими, что i a(j). Своё наименование метод получил от образного представления, при котором в процессе реализации сортировки более «легкие» элементы постепенно «всплывают на поверхность».

Алгоритм процесса пузырьковой сортировки состоит из следующих операций:

1. Выполняется просмотр всего массива, а начинаться он должен с последней пары элементов (а(n) и а(n-1)). Если левый элемент этой пары окажется больше правого, то есть, а(n-1) > а(n), то следует поменять их местами, а в противном случае всё остаётся без изменений. Далее следует перейти ко второй паре элементов, то есть, а(n-1) и а(n-2), и если а(n-2) > a(n-1), то их нужно поменять местами, и так далее. При выполнении первого проход массива должны просматриваться все пары элементов массива a(i) и a(i-1) для i от n до двух. В итоге самый маленький элемент массива должен быть перемещён в начало массива.
2. Так как наименьший элемент уже расположен на подобающем ему месте, то далее следует рассматривать часть массива без этого элемента, то есть, от последнего до второго элемента. Следует повторить предыдущие операции для данного участка массива, по завершении которых второй по величине элемент массива должен быть перемещён на первое место в рассматриваемом участке массива, а именно, на второе место во всем массиве.
3. Эти процедуры необходимо продолжать до тех пор, пока число элементов в текущей части массива не сократится до двух. В таком случае следует исполнить последнюю операцию сравнения, то есть, упорядочить последнюю пару элементов.

Таким образом, при реализации такой сортировки должно быть выполнено n — 1 просмотров массива, после чего массив считается отсортированным.

Рассмотрим конкретный пример сортировки методом простого обмена, или методом «пузырька». Предположим, что имеется целочисленный массив, который состоит из пяти элементов:

78 6 82 67 55.

Очевидно, что по завершении сортировки массив должен иметь следующий вид:

6 55 67 78 82.

Приведём пошаговый процесс сортировки:

• Начиная снизу, выполним сравнение двух соседних элементов, и если они стоят «неверно», то поменяем их местами. За первый проход по массиву один элемент (наименьший) должен встать на свое место.

  
  
  Рисунок 1. Схема сортировки. Автор24 — интернет-биржа студенческих работ

• После второго прохода:

  
  
  Рисунок 2. Схема сортировки. Автор24 — интернет-биржа студенческих работ

• После третьего прохода:

  
  
  Рисунок 3. Схема сортировки. Автор24 — интернет-биржа студенческих работ

• После четвертого прохода

  
  
  Рисунок 4. Схема сортировки. Автор24 — интернет-биржа студенческих работ

Для того чтобы отсортировать массив, состоящий из n элементов нужен n-1 проход, то есть, достаточно переставить на свои места n-1 элемент. В рассмотренном выше примере в массиве имеется пять элементов, а число проходов массива равняется четырём.

Далее приведём пример демонстрационной программы сортировки пузырьковым методом:

• Сначала следует создать графический интерфейс проекта.

• Далее следует объявить переменные, которые будут использоваться в программном модуле

  Dim a(20) As Integer

  Dim n As Integer //фактические размерности массива

  Dim it As Integer //количество итераций по обмену элементов

• Далее запишем программу сортировки пузырьковым методом:

  Sub sorting2(ByVal n As Integer)

  //t является промежуточной переменной, используемой при перестановке элементов

  Dim i, j, t As Integer

  it = 0

  For i = 1 To n - 1

  For j = n - 1 To i Step -1

  // увеличиваем количество итераций обмена элементов

  it = it + 1

  // если элемент справа больше элемента слева,

  //то «вытесняем» его, то есть пузырек «всплывает»

  If a(j - 1) > a(j) Then //перестановка элементов

  t = a(j - 1)

  a(j - 1) = a(j) : a(j) = t

  End If

  Next

  Next

  End Sub