Единое окно доступа к образовательным ресурсам

Методы внутренней сортировки массивов: Учебное пособие к лабораторным работам

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
           ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ




  ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


УДК 681.3.(07)
К721
                            В. В. Костерин

          МЕТОДЫ ВНУТРЕННЕЙ
         СОРТИРОВКИ МАССИВОВ
                 Учебное пособие к лабораторным работам




                              Челябинск
                                2006


       Министерство образования и науки Российской Федерации
               Федеральное агентство по образованию
           Южно-Уральский государственный университет
               Кафедра «Информационные системы»




УДК 681.3.(07)
К721


                          В. В. Костерин



           МЕТОДЫ ВНУТРЕННЕЙ
          СОРТИРОВКИ МАССИВОВ

              Учебное пособие к лабораторным работам




                            Челябинск
                       Издательство ЮУрГУ
                               2006


УДК 681.3.05(075.8) + 681.3.068(075.8)
К721
                                      Одобрено
                            учебно-методической комиссией
                    факультета «Экономика и предпринимательство»


                                       Рецензеты:
                              В.Д. Гунченко, Сафронова И.В.




       Костерин, В.В.
К721 Методы       внутренней сортировки массивов: Учебное пособие к
       лабораторным работам / В.В. Костерин – Челябинск: Изд-во ЮУрГУ,
       2006 – 28 с.


            Комплекс лабораторных работ условно разделен на две части: первая −
       экспериментальное исследование трех базовых алгоритмов сортировки, вычисление
       показателей эффективности этих алгоритмов на различных выборках и сравнение
       полученных результатов с теоретическими вычислениями; вторая часть посвящена
       созданию «мультфильмов», иллюстрирующих последовательность перемещений
       элементов одномерного целочисленного массива при сортировке ранее
       реализованными алгоритмами. Первая часть позволяет студентам освоить
       классические    приемы     создания    алгоритмов    методами    структурного
       программирования, а вторая часть привносит значительную эмоциональную
       составляющую, которая способствует усвоению материала на подсознательном
       уровне.
            Пособие предназначено для студентов специальности 351400 «Прикладная
       информатика (управление, юриспруденция)».




                                                   УДК 681.3.05(075.8) + 681.3.068(075.8)
                                                                 © В.В. Костерин, 2006
                                                        © Издательство ЮУрГУ, 2006


                                       ОГЛАВЛЕНИЕ



НЕМНОГО ТЕОРИИ: МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ ................... 4
   Сортировка включением..................................................................................... 5
   Обменная сортировка.......................................................................................... 5
   Сортировка выбором........................................................................................... 6
   Сравнение методов внутренней сортировки .................................................... 6
СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ ..................................................... 7
   Часть 1. Экспериментальное исследование алгоритмов ................................. 7
   Последовательность выполнения работы ....................................................... 10
   Часть 2. Создание демонстрационных программ-мультфильмов................ 13
   Последовательность выполнения работы ....................................................... 13
ОТЧЁТ О ЛАБОРАТОРНОЙ РАБОТЕ ............................................................... 18
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ.................................................................. 19
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.................................................................. 20
ПРИЛОЖЕНИЕ 1 .................................................................................................. 21
ПРИЛОЖЕНИЕ 2 .................................................................................................. 22




                                                      3


НЕМНОГО ТЕОРИИ: МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ

    «… Сортировка к тому же, еще и сама достаточно хороший пример задачи,
которую можно решать с помощью многих различных алгоритмов. Каждый из
них имеет и свои достоинства, и свои недостатки, и выбирать алгоритмы нужно
исходя из конкретной постановки задачи.
    В общем, сортировку следует понимать как процесс перегруппировки
заданного множества объектов в некотором определенном порядке. Цель
сортировки – облегчить последующий поиск элементов в таком отсортированном
множестве. Это почти универсальная, фундаментальная деятельность. Мы
встречаемся с отсортированными объектами в телефонных книгах, в списках
подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах –
почти везде, где нужно искать хранимые объекты. Даже малышей учат держать
свои вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок
задолго до того, как познакомятся с азами арифметики» [1].
    Итак, задача сортировки ставится следующим образом: имеется
последовательность однотипных записей − строк разделенных на поля, в которые
можно записывать данные различных типов. Одно из полей записей выбрано в
качестве ключевого, далее будем называть его ключом сортировки. Необходимо
чтобы тип данных ключа допускал операции сравнения ("равно", "больше",
"меньше", "не больше " и "не меньше"). Как правило, ключом сортировки
являются данные целого типа. Задачей сортировки является преобразование
исходной последовательности в последовательность, содержащую те же записи,
но в порядке возрастания или убывания значений ключа. Метод сортировки
называется устойчивым, если при его применении не изменяется относительное
положение записей с равными значениями ключа.
    Различают сортировку массивов записей, целиком расположенных в
основной памяти – внутреннюю сортировку, и сортировку файлов, хранящихся во
внешней памяти и не помещающихся полностью в основной памяти − внешнюю
сортировку. Для внутренней и внешней сортировки требуются различные методы.
В нашей лабораторной работе будем изучать наиболее известные, простые и
понятные методы внутренней сортировки, используя средства языка
программирования С в инструментальной среде Borland Builder C++.
    Требованием, предъявляемые к внутренней сортировке является то, что
методы не должны требовать дополнительной памяти: все перестановки с целью
упорядочения элементов массива должны производиться в пределах того же
массива. Мерой эффективности алгоритма внутренней сортировки являются
число требуемых сравнений значений ключа (от английского Compare – C) и
число перестановок элементов (от английского Move – M).



                                         4


    Заметим, что поскольку сортировка основана только на значениях ключа и
никак не затрагивает оставшиеся поля записей, можно говорить о сортировке
массивов ключей. Таким образом, задачу сортировки можно сформулировать
следующим образом: задан одномерный целочисленный массив Arr[N] размером
N = DIM, необходимо расположить элементы этого массива в порядке
возрастания или убывания значений.

Сортировка включением
     Одним из наиболее простых и естественных методов внутренней сортировки
является сортировка простыми включениями. Идея алгоритма очень проста.
Пусть имеется массив ключей Arr[0], Arr[1], ..., Arr[N–1]. Для каждого элемента
массива, начиная со второго, производится сравнение с элементами с меньшим
индексом. Элемент Arr[i] последовательно сравнивается с элементами Arr[j], где
jЄ[i–1;0], т.е. изменяется от i–1 до 0. До тех пор, пока для очередного элемента
Arr[j] выполняется соотношение Arr[j] > Arr[i], Arr[i] и Arr[j] меняются местами.
Если удается встретить такой элемент Arr[j], что Arr[j] <= Arr[i], или если
достигнута нижняя граница массива, производится переход к обработке элемента
Arr[i+1]. Так продолжается до тех пор, пока не будет достигнута верхняя граница
массива.
    Легко видеть, что в лучшем случае, когда массив уже упорядочен для
выполнения алгоритма с массивом из N элементов потребуется N–1 сравнение и 0
пересылок. В худшем случае, когда массив упорядочен в обратном порядке
потребуется N(N–1)/2 сравнений и столько же пересылок. Таким образом, можно
оценивать сложность метода простых включений как O(N2).
    Можно сократить число сравнений, применяемых в методе простых
включений, если воспользоваться тем, что при обработке элемента Arr[i] массива
элементы Arr[0], Arr[1], ..., Arr[i–1] уже упорядочены, и воспользоваться для
поиска элемента, с которым должна быть произведена перестановка, методом
двоичного деления. В этом случае оценка числа требуемых сравнений становится
O(NLogN). Заметим, что поскольку при выполнении перестановки требуется
сдвижка на один элемент нескольких элементов, то оценка числа пересылок
остается O(N2). Алгоритм сортировки включением, оформленный в виде функции
приведен в файле UInsert.cpp и в приложении 1.

Обменная сортировка
    Простая обменная сортировка, называемая «методом пузырька», для массива
Arr[0], Arr[2], ..., Arr[N–1] работает следующим образом. Начиная с конца массива
сравниваются два соседних элемента Arr[N–1] и Arr[N–2]. Если выполняется
условие Arr[N–2] > Arr[N–1], то они меняются местами. Процесс продолжается
для Arr[N–2] и Arr[N–3] и т.д., пока не будет произведено сравнение Arr[1] и
Arr[0]. Понятно, что после этого на месте Arr[0] окажется элемент с наименьшим

                                          5


значением. На втором шаге процесс повторяется, но последними сравниваются
Arr[2] и Arr[1]. И так далее. На последнем шаге будут сравниваться только
текущие значения Arr[N–1] и Arr[N–2]. Понятна аналогия с пузырьком, поскольку
наименьшие элементы, самые «легкие», постепенно «всплывают» к верхней
границе массива.
   Для метода обменной сортировки требуется число сравнений N(N–1)/2,
минимальное число пересылок 0, а среднее и максимальное число пересылок −
O(N2).
    Метод пузырька допускает три простых усовершенствования. Во-первых,
если на некотором шаге не было произведено ни одного обмена, то выполнение
алгоритма можно прекращать. Во-вторых, можно запоминать наименьшее
значение индекса массива, для которого на текущем шаге выполнялись
перестановки. Очевидно, что верхняя часть массива до элемента с этим индексом
уже отсортирована, и на следующем шаге можно прекращать сравнения значений
соседних элементов при достижении такого значения индекса. В-третьих, метод
пузырька работает неравноправно для «легких» и «тяжелых» значений. Легкое
значение попадает на нужное место за один шаг, а тяжелое на каждом шаге
опускается по направлению к нужному месту на одну позицию.

Сортировка выбором
    При сортировке массива Arr[0], Arr[2], ..., Arr[N–1] методом простого выбора
среди всех элементов находится элемент с наименьшим значением Arr[i], и Arr[0]
и Arr[i] обмениваются значениями. Затем этот процесс повторяется для
получаемого подмассива Arr[1], Arr[2], ..., Arr[N–1], ... Arr[j], Arr[j+1], ..., Arr[N–1]
до тех пор, пока мы не дойдем до подмассива Arr[N–1], содержащего к этому
моменту наибольшее значение.
    Для метода сортировки простым выбором оценка требуемого числа
сравнений – N(N–1)/2. Порядок требуемого числа пересылок, которые требуются
для выбора минимального элемента, в худшем случае составляет O(N2). Однако
порядок среднего числа пересылок есть O(NLgN), что в ряде случаев делает этот
метод предпочтительным.

Сравнение методов внутренней сортировки
     Для рассмотренных простых методов сортировки существуют точные
формулы, вычисление которых дает минимальное, максимальное и среднее число
сравнений ключей C и пересылок элементов массива M. Таблица 1 содержит
данные, приводимые в книге Никласа Вирта «Алгоритмы + данные = программы»
[1].




                                              6


                                                                         Таблица 1

                  Характеристики простых методов сортировки


                               Min                 Avg               Max


                      C        N–1            (N2 + N – 2)/4     (N2 –N)/2 – 1
Прямое включение
                      M       2(N–1)         (N2 – 9N – 10)/4    (N2 –3N – 4)/2


                      C     (N2 – N)/2          (N2 – N)/2         (N2 – N)/2
  Прямой выбор
                      M       3(N–1)         N(Ln(N) + 0,57)     N2/4 + 3(N–1)


                      C     (N2 – N)/2          (N2 – N)/2         (N2 – N)/2
   Прямой обмен
                      M         0              0,75(N2 – N)       1,5(N2 – N)


СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ

    Лабораторная работа разделена на две части.

    1. Экспериментальное       исследование     алгоритмов.     Реализация
вышеописанных алгоритмов и их тестовая проверка на трех различных массивах:
упорядоченном, обратно упорядоченном и случайном, с подсчетом количества
операций сравнений и перестановок.
    2. Создание программ-мультфильмов, показывающих на экране монитора
порядок сравнений и перестановок тремя вышеописанными методами.

Часть 1. Экспериментальное исследование алгоритмов

    В результате выполнения этой части Вам необходимо:

   1) заполнить экспериментальными           данными     сравнительную    таблицу
эффективности алгоритмов (табл. 2);



                                         7


    2) рассчитать теоретические значения показателей эффективности для
массива вашего размера;
    3) сравнить экспериментально полученные и расчетные значения;
    4) высказать свое мнение об эффективности алгоритмов.

                                                                     Таблица 2

              Сравнительная таблица эффективности алгоритмов


            Массив            Показатель/Метод     Insert   Select   Bubble


                                      C
        Упорядоченный
                                      M


                                      C
    Обратно упорядоченный
                                      M


                                    Avr(C)
          Случайный
                                   Avr(M)


    По структуре таблицы сравнительной эффективности легко видеть, что Вам
необходимо проделать как минимум 9 опытов, в каждом из которых должны быть
определены два числа C и M. Но в третьем случае, случайного массива, в отличие
от двух первых, заранее нельзя предсказать значения показателей эффективности
(смотри теорию выше). Естественно, что сравнительный анализ алгоритмов
возможен только по средним значениям (в таблице Вы видите функцию Avr(C) –
Average, что значит среднее значение С). Для этого необходимо провести серию
опытов, желательно, 10–15 для каждого алгоритма, т.е. всего 30–45 опытов.


                                          8


Именно это «жуткое» количество экспериментов и определяет структуру
построения программы для реализации плана первой части лабораторной работы.
    Итак, каждый алгоритм сортировки должен быть оформлен в виде
самостоятельной программной единицы – функции, которая может быть
использована многократно. Записать эти функции необходимо в различные
файлы, например, UInsert.cpp, USelect.cpp и UBubble.cpp. Пример одной из них,
метод простого включения, Вы найдете в файле UInsert.cpp и в приложении 1 в
конце этого пособия, а вот оставшиеся две Вам надо написать самостоятельно.
Обратите внимание на оформление текста программы и комментарии к
алгоритму. Комментарии не позволят Вам забыть эти алгоритмы через неделю
после сдачи отчета о своей работе. Кроме того, в отдельный файл (например,
UMain.cpp) необходимо записать основную функцию main(), в которой
реализован план части 1. Пример такой функции в файле UMain.cpp и в
приложении 2 в конце пособия. Код несколько прямолинеен и, конечно, его
можно оптимизировать, но за то он понятен, что сейчас самое главное.
    Прочитаем внимательно комментарии, отбросив исходный код. Ниже
приведен листинг программы без операторов языка «С» – только комментарии.
    // Попытаемся открыть файл для сохранения результата
    // Если задано имя файла в качестве аргумента функции, то откроем его
    // Формируем картинку на экране для вывода показателей эффективности
    // 1) АНАЛИЗ УПОРЯДОЧЕННОГО МАССИВА
    // Формируем исходный массив и выводим его на экран
    // Последовательно обнуляем счетчики показателей эффективности
    // CCount, MCount и вызываем методы Select(...), Insert(...) и Bubble(...)
    // Результаты выводим на экран и при успешном открытии файла
       записываем
    // Ожидаем реакции оператора. При нажатии <Esc> завершаем программу
    // 2) АНАЛИЗ ОБРАТНО УПОРЯДОЧЕННОГО МАССИВА
    // Формируем исходный массив и выводим его на экран
    // Последовательно обнуляем счетчики показателей эффективности
    // CCount, MCount и вызываем методы Select(...), Insert(...) и Bubble(...)
    // Результаты выводим на экран и при успешном открытии файла
       записываем.
    // Ожидаем реакции оператора. При нажатии <Esc> завершаем программу
    // 3) АНАЛИЗ СЛУЧАЙНОГО МАССИВА


                                            9



    
Яндекс цитирования Яндекс.Метрика