регистрация /  вход

Методы сортировки массивов (стр. 1 из 4)

СОДЕРЖАНИЕ:

Введение. 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

Узнать стоимость написания работы
Оставьте заявку, и в течение 5 минут на почту вам станут поступать предложения!