Практикум №2 — Методы сортировки

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

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

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

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

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

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

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

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

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей Arr₀, Arr₁, …, 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(N²).

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

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

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

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

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

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

При сортировке массива Arr₀, Arr₂, …, Arr_N‑1 методом простого выбора среди всех элементов находится элемент с наименьшим значением Arr_i, и Arr₀ и Arr_i обмениваются значениями. Затем этот процесс повторяется для получаемого подмассива Arr₁, Arr₂, …, Arr_N‑1, … Arr_j, Arr_j+1, …, Arr_N‑1 до тех пор, пока мы не дойдем до подмассива Arr_N‑1, содержащего к этому моменту наибольшее значение.
Для метода сортировки простым выбором оценка требуемого числа сравнений – N(N‑1)/2. Порядок требуемого числа пересылок, которые требуются для выбора минимального элемента, в худшем случае составляет O(N²). Однако порядок среднего числа пересылок есть 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 эти алгоритмы уже реализованы и можно просто вызвать нужную функцию из библиотеки. Надо своими мозгами пошевелить, а уже в более сложных задачах пользоваться готовым.