Линейная сортировка массива

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

В предыдущем уроке рассказывалось об алгоритме поиска минимального (максимального) элемента в числовом массиве.

В этом уроке рассматриваются алгоритмы сортировки одномерного массива.

Под сортировкой числового массива понимается процесс перестановки элементов числового массива, целью которого является размещение элементов массива по возрастанию (или по убыванию).

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

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

Рассмотрим три метода сортировки по возрастанию для одного и того же массива. Использование одного массива позволит сравнить эффективность разных методов.

Для сравнения эффективности различных способов сортировки введем целую переменную, значение которой равно числу итераций обмена элементов.

Линейная сортировка (сортировка отбором)

Эта сортировка обычно применяется для массивов, не содержащих повторяющихся элементов

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

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

Упорядочение массива методом линейной сортировки на конкретном примере

Пусть у вас имеется целочисленный массив, состоящий из пяти элементов, и имеет вид:

78 6 82 67 55.

После сортировки массив должен выглядеть так:

6 55 67 78 82.

Процесс сортировки представлен ниже.

Первый проход. Найти минимальный элемент и поставить на первое место (поменять местами с А(1)). Для поиска минимального элемента требуется (n-1) сравнений. Элементов в массиве 5, следовательно количество итераций сравнения – 4.

Второй проход. Из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с А(2)), и т. д. Количество итераций сравнения – 3.

Третий проход. Количество итераций сравнения – 2.

Четвертый проход. Количество итераций сравнения – 1.

Для данного массива линейная сортировка осуществляется за 10 итераций.

Проект «Линейная сортировка»

Задание. Заполнить числовой массив, содержащий 5 элементов, с клавиатуры. Осуществить упорядочение числового массива по возрастанию методом линейной сортировки (методом отбора).

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

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

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

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

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

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

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

Напишем процедуру поиска минимального элемента Minimum(ByVal i , ByRef min), которая будем многократно вызываться из процедуры сортировки и будет содержать входной и выходной параметры:
- i – индекс минимального элемента массива после предыдущего шага;
- min –индекс минимального элемента массива после данного шага.
```
 Sub minimum(ByVal i, ByRef min)
   'Поиск индекса минимального  элемента
   Dim j As Integer
   'Обнуляем счетчик итераций
   min = i
   For j = i + 1 To n - 1
      it = it + 1
      If a(j) < a(min) Then min = j
   Next j
 End Sub
```

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

Private Sub sorting1()
  Dim i, k, r As Integer
  'Линейная сортировка массива по возрастанию 
  For I = 0 To n - 1
    'Вызов процедуры поиска индекса мин.элемента
    minimum(I, min)
    ' Перестановка элементов массива
    r = a(I) : a(I) = a(min) : a(min) = r
  Next i
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

Программный код для кнопки Сортировка:

Dim r, k As Integer
'Очистка полей списка ListBox2
ListBox2.Items.Clear()
sorting1()
'Вывод массива для каждого шага сортировки
For k = 0 To n - 1
   ListBox2.Items.Add(a(k))
Next
label2.text = Str(it)

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

В этом уроке мы рассмотрели алгоритм линейной сортировки одномерного массива.

В следующем уроке рассмотрим сортировку методом «пузырька».

Следующий урок: Пузырьковая сортировка

Урок 37. Сортировка числового массива

Линейная сортировка (сортировка отбором)

Проект «Линейная сортировка»