Методы сортировки массивов

СОДЕРЖАНИЕ:
Введение. 2
1. Задачи сортировки.2
1.1.Общие положения.2
1.2. Постановка задачи сортировки массивов.4
2. Методы сортировки массивов.5
2.1. Простые методы сортировки массивов.5
2.1.1. Сортировка с помощью прямого включения.5
2.1.2.Сортирвка с помощью прямого выбора.8
2.1.3. Сортировка с помощью прямого обмена. 9
2.2. Улучшенные методы сортировки массивов.12
2.2.1.Метод Шелла.12
2.2.2.Сортировка с помощью дерева. 14
2.2.3. Сортировка с помощью разделения. 18
Тесты.. 21
Заключение. 31
Используемая литература. 33
Введение.
Около трех с половиной десятилетий минуло с тех пор, как в педвузах введено в качестве учебной дисциплины программирование для ЭВМ. При колоссальной скорости изменений в самом предмете, всегда существенно превышавшей скорость центральных издательских механизмов, специально ориентированные на программы педвузов книги выходили не чаще, чем раз в десятилетие – едва ли не соразмерно скорости смены поколений ЭВМ. Сегодня полки книжных магазинов ломятся от изданий по информатике. Однако преподавателю (а более всего студенту) специальные учебные книги, содержание и направленность которых отвечают заданному учебному плану и программе все-таки очень нужны. Сейчас помимо программирования на некоторых специальностях в педвузах введены и другие более сложные спецкурсы, находящиеся на стыке прикладной (дискретной) математики и информатики.
В данной курсовой работе можно познакомится с массивами и узнать о простых и сложных методах их сортировки, а также о том, какие из них наиболее эффективны и в каких случаях.
1. Задачи сортировки.
1.1.Общие положения.
Основная задача – продемонстрировать различные методы сортировки и выделить наиболее эффективные из них. Сортировка – достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритм нужно, исходя из конкретной постановки задачи.
В общем сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты.
Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Первоначальный интерес к сортировке основывается на том, что при построении алгоритмов мы сталкиваемся со многими весьма фундаментальными приемами. Почти не существует методов, с которыми не приходится встречаться при обсуждении этой задачи. В частности, сортировка – это идеальный объект для демонстрации огромного разнообразия алгоритмов, все они изобретены для одной и той же задачи, многие в некотором смысле оптимальны, большинство имеет свои достоинства. Поэтому это еще и идеальный объект, демонстрирующий необходимость анализа производительности алгоритмов. К тому же на примерах сортировок можно показать, как путем усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности.
Выбор алгоритма зависит от структуры обрабатываемых данных – это почти закон, но в случае сортировки такая зависимость столь глубока, что соответствующие методы разбили на два класса – сортировку массивов и сортировку файлов (последовательностей). Иногда их называют внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой, оперативной, внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но и более емкой внешней памяти, на устройствах, основанных на механических перемещениях (дисках или лентах).
Прежде чем идти дальше, введем некоторые понятия и обозначения. Если у нас есть элементы а, a, …… , а то сортировка есть перестановка этих элементов в массив аk, ak, …… ,akгде ak <= ak <= ….. <= ak.
Считаем, что тип элемента определен как INTEGER .
Constn=???; //здесь указывается нужная длина массива
Var A: array[1..n] of integer;
Выбор INTEGER до некоторой степени произволен. Можно было взять и
другой тип, на котором определяется общее отношение порядка.
Метод сортировки называют устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некотором вторичным ключам ( т.е. свойствам ), не влияющим на основной ключ.
1.2. Постановка задачи сортировки массивов.
Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес. Мы будем сначала классифицировать методы по их экономичности, т. е. по времени их работы. Хорошей мерой эффективности может быть C – число необходимых сравнений ключей и M – число пересылок (перестановок) элементов. Эти числа суть функции от n – числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n*logn сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка n2 сравнений ключей. Начинать разбор с прямых методов, не трогая быстрых алгоритмов, нас заставляют такие причины:
1. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
2. Программы этих методов легко понимать, и они коротки.
3. Усложненные методы требуют большого числа операций, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
Методы сортировки “ на том же месте “ можно разбить в соответствии с определяющими их принципами на три основные категории:
· Сортировки с помощью включения (byinsertion).
· Сортировки с помощью выделения (byselection).
· Сортировка с помощью обменов (byexchange).
Теперь мы исследуем эти принципы и сравним их. Все программы оперируют массивом а.
Constn=
a: array[1..n] ofinteger;
2. Методы сортировки массивов.
2.1. Простые методы сортировки массивов.
2.1.1. Сортировка с помощью прямого включения.
Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже “готовую” последовательность а, … , а и исходную последовательность. При каждом шаге, начиная с I = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i- й элементы и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
ПРОГРАММА 2.1. ССОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.
PROGRAM SI;
VAR
I,J,N,X:INTEGER;
A:ARRAY[0..50] OF INTEGER;
BEGIN
WRITELN(‘Введите длину массива’);
READ(N);
WRITELN(‘Введитемассив’);
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
BEGIN
X:=A[I];
A[0]:=X;
J:=I;
WHILE X<A[J-1] DO
BEGIN
A[J]:=A[J-1];
DEC(J)
END;
A[J]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Такой типичный случай повторяющегося процесса с двумя условиями
окончания позволяет нам воспользоваться хорошо известным приемом
“барьера” (sentinel).
Анализ метода прямого включения. Число сравнений ключей (Ci) при i- м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – I/2. Число же пересылок Mi равно Ci + 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:
Cmin = n-1 (2.1.) Mmin = 3*(n-1) (2.4.)
Cave = (n2+n-2)/4 (2.2.) Mave = (n2+9*n-10)/4 (2.5.)
Cmax = (n2+n-4)/4 (2.3.) Mmax = (n2+3*n-4)/2 (2.6.)
Алгоритм с прямыми включениями можно легко улучшить, если обратить внимание на то, что готовая последовательность, в которую надо вставить новый элемент, сама уже упорядочена. Естественно остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением ( binaryinsertion).
ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ.
PROGRAM BI;
VAR
I,J,M,L,R,X,N:INTEGER;
A:ARRAY[0..50] OF INTEGER;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
BEGIN
X:=A[I];L:=1;R:=I;
WHILE L<R DO
BEGIN
M:=(L+R) DIV 2;
IF A[M]<=X THEN L:=M+1 ELSE R:=M
END;
FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1];
A[R]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Анализ двоичного включения. Место включения обнаружено, если L=R. Таким образом, в конце поиска интервал должен быть единичной длины; значит, деление его пополам происходит I*logI раз. Таким образом:
C = Si: 1<=i<=n: [logI ] (2.7.)
Аппроксимируем эту сумму интегралом
Integral (1:n) log x dx = n*(log n – C) + C (2.8.)
Где C = loge = 1/ln 2 = 1.4426… . (2.9.)
2.1.2.Сортирвка с помощью прямого выбора.
Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом
2. Он меняется местами с первым элементом а1.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
ПРОГРАММА 2.3. СОРТИРВКА С ПОМОЩЬЮ ПРЯМОГО ВЫБОРА.
PROGRAM SS;
VAR
I,J,R,X,N:INTEGER;
A:ARRAY[0..50] OF INTEGER;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO READ(A[I]);
FOR I:=1 TO N-1 DO
BEGIN
R:=I;
X:=A[I];
FOR J:=I+1 TO N DO IF A[J]<X THEN
BEGIN
R:=J;
X:=A[R]
END;
A[R]:=A[I];
A[I]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Анализ прямого выбора. Число сравнений ключей (С), очевидно не зависит от начального порядка ключей. Для С мы имеем C = (n2 – n)/2 (2.10.).
Число перестановок минимально: Mmin = 3*(n-1) (2.11.).
В случае изначально упорядоченных ключей и максимально Mmax = n2/4 + 3*(n-1) (2.12.)
Определим Мavg . Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением Fi = lni + g + 1 (2.13.), где g = 0.577216… - константа Эйлера.
Среднее число пересылок Mavg в сортировке с выбором есть сумма Fiс i от 1 до n
Mavg = n*(g + 1) + (Si: 1<=i<=n: ln i) (2.14.)
Вновь аппроксимируя эту сумму дискретных членов интегралом
Integral (1:n) ln x dx = x*(ln x – 1) = n*ln (n) – n + 1 (2.15.)
Получаем приблизительное значение
Mavg = n*(ln (n) + g) . (2.16.)

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию