Март
23rd

Урок 39. Метод быстрой сортировки с разделением

Рубрика: Visual Basic.NET для школьников | Автор:admin

Урок из серии: “Программирование на Visual Basic для школьников”

В предыдущем уроке рассказывалось о сортировке числового массива методом “пузырька”.

Оба выше рассмотренных метода просты и наглядны, но не эффективны. Значительно быстрее работает алгоритм сортировки Хоара, который называют сортировкой с разделением или «быстрой сортировкой».

Сортировка методом простого обмена требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы.

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

Идея метода

1. В исходном неотсортированном массиве выбрать некоторый элемент x = a(k) (барьерный элемент).

2. Переставить элементы массива таким образом, чтобы слева от x оказались элементы массива, меньшие или равные x, а справа ­ элементы массива, большие чем х.

Сортировка Хоара

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

Рассмотрим применение метода «быстрой сортировки» на примере.

Исходный массив состоит из 5 элементов:

78  6  82  67  55  .

Разделение:

1. Выбрать средний элемент массива (x = 67)

Сортировка Хоара

2. Установить L = 1, R=n.

3. Увеличивая L, найти первый элемент a(L), который >= x (который должен стоять справа)

4. Уменьшая R, найти первый элемент a(R), который < x (который должен стоять слева).

5. Если L < R, поменять местами a(L) и a(R) и перейти к п. 3

6. Если L > R, разделение закончено.

Сортировка Хоара

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

Проект “Быстрая сортировка”

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

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

    Сортировка Хоара

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

    Dim a(20) As Integer
    Dim n As Integer ' фактическая размерность массива
    Dim k 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. Напишем программный код процедуры быстрой сортировки:

    Private Sub Quick_sorting(ByVal L As Integer, ByVal R As Integer)
    
     Dim i, j, x, w As Integer
     i = L 'левая граница массива - первый элемент 
     j = R 'правая граница массива - последний элемент
     x = a((L + R) \ 2) ' определить середину массива
     Do
        Do While a(i) < x
          i = i + 1
        Loop
        Do While a(j) > x
          j = j - 1
        Loop
        'увеличиваем число итераций обмена элементов 
        k = k + 1
        If i <= j Then ' обменять местами элементы
          w = a(i) : a(i) = a(j) : a(j) = w
          i = i + 1 : j = j - 1
        End If
        Loop Until (i > j)
        ' рекурсивный вызов процедуры сортировки
        If L < j Then Quick_sorting(L, j)
        If i < R Then Quick_sorting(i, R)
    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
      Quick_sorting(0, n - 1) 'Вызов процедуры сортировки
      For i = 0 To n - 1 'Отсортированный массив выводим список ListBox2
         ListBox2.Items.Add(a(i))
      Next
         Label2.Text = k
    End Sub
  7. Запустите проект и проверьте работу приложения.
    Щелкните по кнопке Заполнить массив, чтобы ввести размерность массива и элементы массива. В первый список выведется исходный массив.

    Сортировка Хоара

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


В этом уроке мы рассмотрели один из самых быстрых методов сортировки – сортировку с разделением или сортировку Хоара.

На этом мы заканчиваем изучение алгоритмов сортировки числовых массивов.

Поделиться с друзьями


Оставить комментарий или два