Быстрая сортировка

Урок из серии: «Программирование на 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 итераций.

Проект «Быстрая сортировка»

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

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

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

Dim a(20) As Integer
Dim n As Integer ' фактическая размерность массива
Dim k 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

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

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

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

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
  Quick_sorting(0, n - 1) 'Вызов процедуры сортировки
  For i = 0 To n - 1 'Отсортированный массив выводим список ListBox2
     ListBox2.Items.Add(a(i))
  Next
     Label2.Text = k
End Sub

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

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

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

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

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

Идея метода

Проект «Быстрая сортировка»