«… Сортировка к тому же, еще и сама достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритмы нужно исходя из конкретной постановки задачи.
В общем, под сортировкой мы будем понимать процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики».
Н. Вирт — Алгоритмы + данные = программы
Немного теории
Итак, задача сортировки ставится следующим образом: имеется последовательность однотипных записей − строк разделенных на поля, в которые можно записывать данные различных типов. Одно из полей записей выбрано в качестве ключевого, далее будем называть его ключом сортировки. Необходимо чтобы тип данных ключа допускал операции сравнения ("равно", "больше", "меньше", "не больше " и "не меньше"). Как правило, ключом сортировки являются данные целого типа. Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания или убывания значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.
Различают сортировку массивов записей, целиком расположенных в основной памяти – внутреннюю сортировку, и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти − внешнюю сортировку. Для внутренней и внешней сортировки требуются различные методы. В нашей практической работе будем изучать наиболее известные, простые и понятные методы внутренней сортировки, используя средства языка программирования 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) |
Экспериментальное исследование алгоритмов
В результате выполнения этой практической работы Вам необходимо провести численный эксперимент и
- заполнить экспериментальными данными сравнительную таблицу эффективности алгоритмов (см. Таблицу 2 ниже);
- рассчитать теоретические значения показателей эффективности для массива вашего размера. Для этого рекомендуется использовать MS Exell;
- сравнить экспериментально полученные и расчетные значения;
- высказать свое мнение об эффективности алгоритмов.
Сравнительная таблица эффективности алгоритмов (Таблица 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. Не опаздывайте, впереди у вас обширное задание по курсовой работе до конца семестра.