Задание к лабораторной №1

Лабораторная работа №1 по дисциплине "Технология программирования"

"Программирование алгоритмов сортировки"

1. Теоретические сведения

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

Метод выбора (1)

В процессе первого прохода в исходном массиве находятся минимальный элемент, который помещается на место первого элемента. Первый элемент помещается на место минимального. На втором и последующих проходах поиск и обмен повторяются для оставшихся после предыдущего прохода элементов (с позициями: на втором проходе – со второй по последнюю, на третьем проходе – с третьей по последнюю и т.д.) до тех пор, пока не будет отсортирована вся последовательность. Общее число сравнений составляет приблизительно 0,5 N², N – здесь и далее число элементов.

Метод обмена (2)

В процессе сортировки производится попарное сравнение соседних элементов. Если порядок следования соседних элементов нарушен, то они меняются местами. В процессе первого прохода максимальный элемент попадает на последнее место и, следовательно, в последующих сравнениях не участвует. Остальные элементы "всплывают" на одну позицию вверх (поэтому метод часто называют сортировкой "пузырьком"). На каждом следующем проходе рассматривается последовательность для N-1, N-2 и т.д. элементов. Если при каком-либо проходе не было произведено ни одной перестановки, последовательность отсортирована. Максимальное число сравнений составляет приблизительно 0,5 N², среднее число сравнений пропорционально 0,25 N², среднее число обменов – 0,25 N².

Сортировка вставками (3)

Первый элемент исходного списка считается отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. В целом, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Среднее число сравнений пропорционально N².

Метод подсчета (4)

Метод основан на том, что k+1-ый элемент упорядоченной последовательности превышает ровно k элементов, и следовательно занимает k+1-ую позицию. В процессе сортировки на каждом i-ом проходе i-ый элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Инициализированный нулем перед началом прохода счетчик k увеличивается, если i-ый элемент оказался больше текущего. Таким образом, порядковый номер i-го элемента, по окончанию i-го прохода, равен k+1. Для сортировки последовательности из N элементов требуется N проходов, на каждом из которых выполняется N сравнений. Число сравнений равно N². Приведенный метод подсчета можно использовать, если достоверно известно, что в исходно последовательности нет записей с одинаковыми ключами.

Метод Шелла (5)

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

В одной из модификаций метода (в случае, предложенном Д. Шеллом) шаг кратен степеням двойки. Вначале последовательность из N элементов делится на N/2 групп, если N – четно, и на (N-1)/2 групп, если N – нечетно. Каждая группа содержит по два элемента, если количество элементов было нечетным, одна из групп содержит три элемента. Элементы каждой группы отстоят друг от друга на расстоянии N/2 или (N-1)/2. В течение первого прохода осуществляется упорядочение элементов каждой группы методом вставок. Для осуществления следующего прохода шаг уменьшается вдвое (как и число групп), по отношению к предыдущему шагу (у дробных чисел берется целая часть). Процесс повторяется до тех пор, пока шаг не станет равным единице. В этом случае методом вставок сортируется весь список (одна группа). С точки зрения программной реализации потребуется неоднократный вызов сортировки вставками с указанием, в качестве параметров (помимо исходного списка и числа элементов), индекса начального элемента группы и шага. Приблизительное число сравнений составляет N log₂ N.

Сортировка по дереву (6)

Процесс сортировки состоит из: фазы построения двоичного дерева поиска и фазы обхода. Структура двоичного дерева задается с помощью связного списка, каждый элемент которого может иметь, максимум, двух потомков (две ссылки). Двоичное дерево формируется по всем исходным элементам, по следующему правилу. Первый элемент исходной последовательности является первым узлом дерева. Следующий элемент последовательности сравнивается со значениями в узлах строящегося дерева, начиная с корня. Если значение текущего элемента больше значения элемента в узле дерева, следует переместиться вниз по правой ссылке от текущего узла, в противном случае – по левой ссылке. Перемещение по дереву продолжается до тех пор, пока не будет достигнута свободная ссылка, после чего осуществляется вставка элемента в дерево. После формирования дерева необходимо провести процедуру смешанного обхода. Он заключается в рекурсивном посещении (чтении) узлов, начиная с корня: левого поддерева, узла, правого поддерева. В результате получается отсортированная последовательность. Среднее число сравнений aN log₂ N, 1 < a < 2.

Сбалансированное N-ленточное слияние

Общей формой внешней сортировки является N-ленточное слияние. Для N-ленточного слияния потребуется 2N магнитных лент и 2N лентопротяжных устройств (которые можно заменить 2N файлами на устройстве внешней памяти). Исходная неупорядоченная последовательность размещается на первой магнитной ленте. Затем она разносится на N магнитных лент по следующему правилу: первая запись – на первую из N лент, вторая – на вторую, (N+1)-ая – снова на первую из N лент.

Сбалансированное N-ленточное слияние осуществляется в два этапа. На первом этапе из записей, хранящихся на каждой магнитной ленте, формируются упорядоченные цепочки. Так как все цепочки имеют одинаковую длину, слияние называется сбалансированным. Упорядочение цепочки происходит в оперативной памяти одним из методов внутренней сортировки. Упорядоченные цепочки размещаются на N свободных магнитных лентах, после чего начинается второй этап сортировки – слияние. Процесс слияния осуществляется в несколько циклов. После каждого цикла слияния длина упорядоченных цепочек увеличивается на N. В конечном итоге, формируется упорядоченная последовательность из N составляющих. Собственно слияние осуществляется следующим образом. Пусть имеются две цепочки длиной l, изначально упорядоченные. Необходимо получить одну упорядоченную цепочку. Для этого: сравниваются первые элементы двух цепочек, меньшая переписывается в результирующую цепочку; операция осуществляется с помощью трех счетчиков; после записи в результирующую последовательность увеличивается на единицу счетчик результирующей последовательности и счетчик последовательности, в которой был обнаружен меньший элемент; действие повторяется до тех пор, пока один из счетчиков исходной последовательности не достигнет значения конца последовательности, после чего оставшиеся элементы другой последовательности дописываются в конец результирующей. Таким образом, будут упорядочены каждая из N магнитных лент.

Цель работы

Приобретение навыков реализации программ сортировки данных.

Задание кафедры

Осуществить программную реализацию сортировки информации заданного вида сбалансированным N-ленточным слиянием (в оперативной памяти), используя выбранные, в соответствии с вариантом, из табл. 1 алгоритм внутренней сортировки и формат исходных данных.

№ п/п	Ключ	Запись 0 – только ключ, 1 – ключ и другие данные различных типов	Метод внутренней сортировки
1	int	1, char[], float	2
2	int[]	0	5
3	float	1, float[], char[]	4
4	float[]	0	3
5	char	1, int[], char	3
6	char[]	0	2
7	int	1, char, float	5
8	int[]	0	1
9	float	1, int[], char	1
10	float[]	0	4
11	char	0	4
12	char[]	0	1
13	int	1, char[]	4
14	int[]	0	2
15	float	1, char[], int	3
16	float[]	0	2
17	char	1, char[], int	5
18	char[]	0	4