Методы сортировки массивов (стр. 1 из 4)
СОДЕРЖАНИЕ:
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.2.Сортировка с помощью дерева. 14
2.2.3. Сортировка с помощью разделения. 18
Введение.
Около трех с половиной десятилетий минуло с тех пор, как в педвузах введено в качестве учебной дисциплины программирование для ЭВМ. При колоссальной скорости изменений в самом предмете, всегда существенно превышавшей скорость центральных издательских механизмов, специально ориентированные на программы педвузов книги выходили не чаще, чем раз в десятилетие – едва ли не соразмерно скорости смены поколений ЭВМ. Сегодня полки книжных магазинов ломятся от изданий по информатике. Однако преподавателю (а более всего студенту) специальные учебные книги, содержание и направленность которых отвечают заданному учебному плану и программе все-таки очень нужны. Сейчас помимо программирования на некоторых специальностях в педвузах введены и другие более сложные спецкурсы, находящиеся на стыке прикладной (дискретной) математики и информатики.
В данной курсовой работе можно познакомится с массивами и узнать о простых и сложных методах их сортировки, а также о том, какие из них наиболее эффективны и в каких случаях.
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