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

Урок из серии «Программирование на Visual Basic.Net для школьников»

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

В этом уроке рассмотрим еще один алгоритм для сортировки массива — сортировку методом простого обмена или методом «пузырька».

Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива и обмене местами соседних элементов, расположенных «неправильно», то есть таких, что i <j, а a(i) > a(j).

Название метода происходит от образной интерпретации, при которой в процессе выполнения сортировки более «легкие» элементы мало-помалу всплывают на «поверхность».

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

Опишем сортировку методом простого обмена подробнее.

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

При сортировке выполняется n — 1 просмотр массива, после этого массив отсортирован.

Сортировка методом простого обмена на конкретном примере

Пусть у вас имеется тот же, что и в предыдущем примере, целочисленный массив, состоящий из пяти элементов:
78 6 82 67 55.
После сортировки массив должен выглядеть так:
6 55 67 78 82.
Процесс сортировки представлен ниже.

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

Второй проход.

Третий проход.

Четвертый проход

Для сортировки массива из n элементов нужен n-1 проход (достаточно поставить на свои места n-1 элемент). В нашем случае в массиве 5 элементов, количество проходов массива — 4.

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

Проект «Сортировка методом простого обмена»

Задание. Отсортировать по возрастанию методом простого обмена массив из 5 элементов:

78 6 82 67 55.

Ход выполнения проекта

Создадим графический интерфейс проекта. Поместим на форму:
- список ListBox1 для вывода значений исходного массива;
- список ListBox2 для вывода отсортированного массива;
- кнопку Button1 для заполнения массива;
- кнопку Button2 для запуска процесса сортировки;
- две надписи Button1 и Button2 для вывода количества итераций.

Объявим переменные для использования в программном модуле

 Dim a(20) As Integer
 Dim n As Integer    'фактическая размерность массива
 Dim it As Integer   'число итераций обмена элементов

Напишем процедуру заполнения массива с клавиатуры

 Private Sub init1(ByVal n As Integer)
   ' Заполнение массива с клавиатуры
   Dim i As Integer
     For i = 0 To n - 1
        a(i) = Val(InputBox("Введите " + Str(i + 1) + " элемент:"))
     Next i
 End Sub

Напишем процедуру сортировки методом простого обмена:

 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

Создадим обработчик для кнопки Заполнить массив

Private Sub Button1_Click(ByVal sender As System.Object, 
_ByVal e As System.EventArgs) Handles Button1.Click
  ' Заполнение массива с клавиатуры
  Dim i As Integer
  n = Val(InputBox("Введите количество элементов массива", "Ввод данных"))
  init1(n)        'вызов процедуры заполнения массива с клавиатуры
  ListBox1.Items.Clear()  'очистить список  ListBox1 
  For i = 0 To n - 1      'вывести исходный массив в список ListBox1
     ListBox1.Items.Add(a(i))
  Next
End Sub

Создадим обработчик события сортировки

Private Sub Button2_Click(ByVal sender As System.Object, 
_ByVal e As System.EventArgs) Handles Button2.Click
  ' сортировка 
  Dim i As Integer
  sorting2(n)         'вызов процедуры сортировки
  For i = 0 To n - 1  'вывод отсортированного  массива в ListBox2
     ListBox2.Items.Add(a(i))
  Next
  Label2.Text = it
End Sub

Запустите проект и проверьте работу приложения.
Щелкните по кнопке Заполнить массив, чтобы ввести размерность массива и элементы массива. В первый список выведется исходный массив.

Щелкните по кнопке Сортировать массив. Во второй список будет выведен отсортированный массив, в поле надписи — количество итераций.

В этом уроке мы рассмотрели один из самых популярных методов сортировки — «пузырьковый», который основан на том, что в процессе исполнения алгоритма более легкие элементы массива постепенно «всплывают».

В следующем уроке рассмотрим метод быстрой сортировки или сортировку Хоара.

Следующий урок : Метод быстрой сортировки с разделением

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

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

Проект «Сортировка методом простого обмена»