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

Урок из серии «Программирование на 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 элементов, с клавиатуры. Осуществить упорядочение числового массива по возрастанию методом линейной сортировки (методом отбора).

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

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

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

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

  2. Объявим переменные для использования в программном модуле>/p>
     Dim I, min As Integer
     Dim a(20) As Integer ' числовой массив
     Dim n As Integer    'фактическая размерность массива
     Dim it As Integer = 0 'число итераций обмена элементов
  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. Напишем процедуру поиска минимального элемента 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
  5. Программный код процедуры линейной сортировки будет иметь вид:
    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
  6. Напишем программный код обработки события щелчок на кнопке Заполнение массива.
    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
  7. Программный код для кнопки Сортировка:
    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)
  8. Запустите проект. Щелкните по кнопке Заполнить массив. В первый список будут выведены значения элементов массива.
  9. Щелкнуть по кнопке Сортировать. Во второй список будет выведен отсортированный по возрастанию массив, в поле надписи — количество итераций.Линейная сортировка

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

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

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

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

1 Комментарий
Новые
Старые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии
ZZZ
ZZZ
9 месяцев назад

сортировка отбора точно линейная? Не экспоненциальная?