Сортировка числовых массивов

1. Изучить алгоритм сортировки массива методом отбора (линейная сортировка).
2. Создать проект на Visual Basic.NET, реализующий данный метод сортировки.

Тип урока: практическая работа

1.Новый материал

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

Следует знать:

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

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

Наиболее распространенные методы сортировки:

• линейная сортировка (сортировка отбором);
• сортировка методом пузырька;
• быстрая сортировка с разделением (сортировку Хоара).

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

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

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

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

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

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

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

78 6 82 67 55.

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

6  55  67  78  82.

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

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

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

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

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

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

Процедура упорядочения массива по возрастанию  методом линейной сортировки

    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

2.Практическая работа

Задание. Создать проект на Visual Basic.NET, реализующий упорядочение числового массива по возрастанию методом  линейной сортировки (методом отбора).

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

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

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

Объявим переменные для использования в программном модуле
    Dim I, min As Integer

    Dim a(20) As Integer

    Dim n As Integer          'фактическая размерность массива

    Dim it As Integer = 0     'число итераций обмена элементов

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

    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

2. Напишем процедуру поиска минимального элемента Minimum

    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

3. Программный код процедуры линейной сортировки будет иметь вид:
   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

4. Программный код обработчика события щелчок на кнопке Заполнение массива.

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

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

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click

        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)

    End Sub

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

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

Подведение итогов. Просмотр работ

Задание для самостоятельного выполнения.

Изучит алгоритм сортировки методом «пузырька». На основе предыдущего проекта создать новый проект, реализующую сортировку массива методом «пузырька». Сравнить эффективность  методов сортировки для массивов разного  размера. Составить сравнительную таблицу.