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

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

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

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

Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива  и обмене местами соседних элементов, расположенных «неправильно», то есть таких, что i <j, а a(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. В результате минимальный элемент массива переместиться в начало массива.
  2. Поскольку самый маленький элемент находиться на своем месте, рассмотрим часть массива без него, то есть с последнего до 2-го элемента. Повторим предыдущие действия для этой части массива, в результате чего второй по величине элемент массива переместиться на первое место рассматриваемой части массива, то есть на 2-е место во всем массиве.
  3. Эти действия продолжаются до тех пор, пока количество элементов в текущей части массива не уменьшится до двух. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента.

При сортировке выполняется 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.

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

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

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

  2. Объявим переменные для использования в программном модуле
     Dim a(20) As Integer
     Dim n As Integer    'фактическая размерность массива
     Dim it As Integer   'число итераций обмена элементов
  3. Напишем процедуру заполнения массива с клавиатуры
     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
  4. Напишем процедуру сортировки методом простого обмена:
     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
  5. Создадим обработчик для кнопки Заполнить массив
    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
  6. Создадим обработчик события сортировки
    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
  7. Запустите проект и проверьте работу приложения.
    Щелкните по кнопке Заполнить массив, чтобы ввести размерность массива и элементы массива. В первый список выведется исходный массив.

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

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


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

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

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

Подписаться
Уведомить о
guest

0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии