Методические указания для выполнения практического задания «Алгоритмы сортировки»

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

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

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

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

Различают сортировку массивов записей, целиком расположенных в основной памяти — внутреннюю сортировку, и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти − внешнюю сортировку. Для внутренней и внешней сортировки требуются различные методы. В нашей практической работе будем изучать наиболее известные, простые и понятные методы внутренней сортировки, используя средства языка программирования 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 для описанных выше алгоритмов может смело подходить с направлением из деканата и зачёткой. Курсовая работа — «автоматом».

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

Что необходимо сделать?

На языке Python запишем алгоритм одного из методов сортировки — метод простого выбора.

import random

dim = 20
arr = [random.randint(0, 100) for i in range(dim)]

print("Исходный массив")
print(arr)

#метод простого выбора Select
#в переменной k хранится индекс элемента, подлежащего обмену (двигаемся слева на право)
k = 0
mcount = 0
ccount = 0
for k in range(dim - 1): #-1, т.к. последний элемент обменивать уже не надо
    m = k #в m хранится текущее минимальное значение
    i = k + 1 #откуда начинать поиск минимума (элемент следующий за k)
    for i in range(i, dim):
        ccount += 1
        if arr[i] < arr[m]:
            m = i
    if k != m:
        t = arr[k]
        arr[k] = arr[m]
        arr[m] = t
        mcount += 1
 
print("\nУпорядоченный массив: метод простого выбора")
print(arr)
print("\nЭлементов в массиве: ", dim)
print("Сравнений: ", ccount)
print("Перестановок: ", mcount)

Что бы понять эту программу используйте шпаргалку "Python конспективно, за 15 минут"

Алгоритмы оставшихся двух функций Вам надо написать самостоятельно. Не бойтесь ошибок, в дальнейшем мы их вместе исправим. Сейчас главное — понять в чем суть методов сортировки.

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

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

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

Есть вопросы или комментарии — пишите в комментариях или в нашу группу в WhatsApp.