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

В общем, под сортировкой мы будем понимать процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики».
Н. Вирт — Алгоритмы + данные = программы

Немного теории

Итак, задача сортировки ставится следующим образом: имеется последовательность однотипных записей − строк разделенных на поля, в которые можно записывать данные различных типов. Одно из полей записей выбрано в качестве ключевого, далее будем называть его ключом сортировки. Необходимо чтобы тип данных ключа допускал операции сравнения («равно», «больше», «меньше», «не больше» и «не меньше»). Как правило, ключом сортировки являются данные целого типа. Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания или убывания значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

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

Требованием, предъявляемые к внутренней сортировке является то, что методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (от английского Compare – C) и число перестановок элементов (от английского Move – M).

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

Сортировка включением

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей Arr0, Arr1, …, ArrN‑1. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом. Элемент Arri последовательно сравнивается с элементами Arrj, где jЄ[i‑1;0], т.е. изменяется от i‑1 до 0. До тех пор, пока для очередного элемента Arrj выполняется соотношение Arrj > Arri, Arri и Arrj меняются местами. Если удается встретить такой элемент Arrj, что Arrj ≤ Arri, или если достигнута нижняя граница массива, производится переход к обработке элемента Arri+1. Так продолжается до тех пор, пока не будет достигнута верхняя граница массива.

Легко видеть, что в лучшем случае, когда массив уже упорядочен для выполнения алгоритма с массивом из N элементов потребуется N‑1 сравнение и 0 пересылок. В худшем случае, когда массив упорядочен в обратном порядке потребуется N(N‑1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(N2).

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем, что при обработке элемента Arri массива элементы Arr0, Arr1, …, Arri‑1 уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(N*Log(N)). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(N2). Алгоритм сортировки включением, оформленный в виде функции приведен ниже.

Обменная сортировка

Простая обменная сортировка, называемая «методом пузырька», для массива Arr0, Arr2, …, ArrN‑1 работает следующим образом. Начиная с конца массива сравниваются два соседних элемента ArrN‑1 и ArrN‑2. Если выполняется условие ArrN‑2 > ArrN‑1, то они меняются местами. Процесс продолжается для ArrN‑2 и ArrN‑3 и т.д., пока не будет произведено сравнение Arr1 и Arr0. Понятно, что после этого на месте Arr0 окажется элемент с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются Arr2 и Arr1. И так далее. На последнем шаге будут сравниваться только текущие значения ArrN‑1 и ArrN‑2. Понятна аналогия с пузырьком, поскольку наименьшие элементы, самые «легкие», постепенно «всплывают» к верхней границе массива.

Для метода обменной сортировки требуется число сравнений N(N‑1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок − O(N2).

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

Сортировка выбором

При сортировке массива Arr0, Arr2, …, ArrN‑1 методом простого выбора среди всех элементов находится элемент с наименьшим значением Arri, и Arr0 и Arri обмениваются значениями. Затем этот процесс повторяется для получаемого подмассива Arr1, Arr2, …, ArrN‑1, … Arrj, Arrj+1, …, ArrN‑1 до тех пор, пока мы не дойдем до подмассива ArrN‑1, содержащего к этому моменту наибольшее значение.
Для метода сортировки простым выбором оценка требуемого числа сравнений – N(N‑1)/2. Порядок требуемого числа пересылок, которые требуются для выбора минимального элемента, в худшем случае составляет O(N2). Однако порядок среднего числа пересылок есть O(N*Lg(N)), что в ряде случаев делает этот метод предпочтительным.

Что бы теория была понятна «визуальщикам»

ПРИМЕЧАНИЕ: Кто сделает подобный мультик на Python для описанных выше алгоритмов может смело подходить с направлением из деканата и зачёткой. Курсовая работа и экзамен — «автоматом».

Об этих и более продвинутых методах сортировки можно прочитать здесь

Сравнение методов внутренней сортировки

Для рассмотренных простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей C и пересылок элементов массива M (см. Таблицу 1 ниже).

Характеристики простых методов сортировки (Таблица 1)

Метод   Min Avr 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 ниже);
  2. рассчитать теоретические значения показателей эффективности для массива вашего размера. Для этого рекомендуется использовать MS Exell;
  3. сравнить экспериментально полученные и расчетные значения;
  4. высказать свое мнение об эффективности алгоритмов.

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

Массив Показатель [DIM] элементов
    Insert Select Bubble
Упорядоченный C [Value] [Value] [Value]
M [Value] [Value] [Value]
Обратно упорядоченный C [Value] [Value] [Value]
M [Value] [Value] [Value]
Случайный Avr(C) [Value] [Value] [Value]
 Avr(M) [Value] [Value] [Value]

По структуре таблицы сравнительной эффективности легко видеть, что Вам необходимо проделать как минимум 9 опытов (3 метода х 3 реализации одномерного массива), в каждом из которых должны быть определены два числа C и M. Но в третьем случае, случайного массива, в отличие от двух первых, заранее нельзя предсказать значения показателей эффективности (смотри теорию выше). Естественно, что сравнительный анализ алгоритмов возможен только по средним значениям (в таблице Вы видите функцию Avr(C) – Average, что значит среднее значение С). Для этого необходимо провести серию опытов, желательно, 100–150 для каждого алгоритма (для получения устойчивых значений), т.е. всего 300–450 опытов. Именно это «жуткое» количество экспериментов и определяет структуру построения программы для реализации плана практической работы первой части курсовой работы.

Итак, каждый алгоритм сортировки должен быть оформлен в виде самостоятельной программной единицы – функции, в Python это подключаемый к основной программе модуль. Записать эти модули необходимо в различные файлы, например, insert.py, select.py и bubble.py. Пример одного из них, метод простого включения, файл insert.py,

#метод простого включения Insert
def insert(arr, dim):
    alg_count = [0, 0]              # массив для показателей эффективности
    
    for i in range(1, dim):         # Основной цикл со 2-го элемента право 
        temp = arr[i]               # Запомним элемент для сравнения 
        j = i - 1
        while j >= 0:               # Ищем влево ближайший меньший  
            alg_count[0] += 1       # Считаем операции сравнения 
            if arr[j] > temp:
                alg_count[1] += 1   # Считаем операции перестановки 
                arr[j+1] = arr[j]   # Сдвигаем элемент влево, а на его место ставим наименьший
                arr[j] = temp
            j -= 1        
    return alg_count

А вот оставшиеся две функции Вам надо написать самостоятельно. Обратите внимание на оформление текста программы и комментарии к алгоритму. Комментарии не позволят Вам забыть эти алгоритмы через неделю после сдачи отчета о своей работе. Кроме того, в отдельный файл (например, sort-exp.py) необходимо записать программу, которая реализует весь численный эксперимент. Естественно, результаты вычислений необходимо сохранять в отдельном файле, который можно прочитать и использовать при заполнении таблицы 2.

Отчет по этой практической работе является частью I вашей большой курсовой работы. Время на выполнение — 2 недели с момента выдачи задания, в нашем случае deadline наступает 14 марта 2019. Не опаздывайте, впереди у вас обширное задание по курсовой работе до конца семестра.

И не надо мне говорить, что в Python эти алгоритмы уже реализованы и можно просто вызвать нужную функцию из библиотеки. Надо своими мозгами пошевелить, а уже в более сложных задачах пользоваться готовым.

Опубликовано Вадим В. Костерин

ст. преп. кафедры ЦЭиИТ. Автор более 130 научных и учебно-методических работ. Лауреат ВДНХ (серебряная медаль).

Оставьте комментарий

Ваш адрес email не будет опубликован.