Автор работы: Пользователь скрыл имя, 10 Января 2013 в 18:04, курсовая работа
В данной курсовой работе будут рассмотрены основные виды сортировок с подробными описаниями и примерами решения задач, выполненных в среде программирования Free Pascal.
Введение 3
1. Сортировка вставками 4
2. Сортировка методом простого выбора 11
3. Сортировка методом прямого включения 14
4. Сортировка методом слияния 17
5. Обменная сортировка с разделением 20
Заключение 23
Список используемой литературы 24
второе место в c надо занести а [k + 1] = 3. Затем надо увеличить на 1 значения i и l.
3-й шаг: на третье место массива c претендуют два одинаковых элемента —
а [k + 2] = 5 и b [m + 2] = 5. В этом и подобных случаях договоримся заносить в c
первым элемент из части a. Таким образом, с [ 3 ] = а [k + 2], а значение l = 4, i = k + 3,
j остается равным т + 2.
4 - 11-й шаги: рассуждая аналогичным образом, надо занести в c элементы 6, 7, 8, 9, 11, 12, 13, 16. После выполнения 11-го шага первая часть будет занесена в c полностью, значение j равно т + 7, значение l равно 12.
12-й шаг: так как часть a закончилась, а «хвост» части b упорядочен по условию,
то двенадцатым элементом массива с будет первый элемент «хвоста» b, то
есть b [ m + 7 ] = 18.
13-й шаг: последним элементом массива с будет последний элемент b - 20.
На рисунке схематично изображен процесс заполнения массива с.
Сейчас можем описать
n и m в третий упорядоченный массив, размерность которого p (р = n + m).
Procedure sorting4 (k, m, n : integer);
Begin
i : = k + l;
j : = m + l;
k : = l;
while ( i < = m ) and ( j < = n ) do {пока не закончилась хотя бы одна часть}
Begin
if a [ i ] < = b [ j ] then
Begin
c [ k ] : = a [ i ]; inc ( i );
End
else
Begin
End;
inc ( k );
End; {один из массивов-частей обработан полностью, осталось перенести
в 'с' остаток другого массива-части}
while i < = m do
Begin
c [ k ] : = a [ i ]; inc ( i ); inc ( k )
End;
while j < = n do
Begin
c [ k ] : = b [ j ]; inc ( j ); inc ( k )
End
End.
Далее остается лишь переписать результат
слияния рассматриваемых
5. Обменная сортировка с разделением (сортировка Хоара)
Сортировка методом вставок (методом «пузырька») часто является самой неэффективной. Это обусловлено самой идеей метода, которая требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы.
Можно существенно улучшить метод сортировки, основанный на обмене.
Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением.
Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч.Э.Р.Хоар в 1962 г. Поскольку производительность этого метода просто впечатляюща, автор назвал его «быстрой сортировкой».
Идея метода:
1. В исходном неотсортированном массиве выбрать некоторый элемент х = а[к] (барьерный элемент).
2. Переставить элементы массива таким образом, чтобы слева от х оказались элементы массива, меньшие или равные х, а справа — элементы массива, большие х.
Пусть при этом элемент х попадет в позицию с номером к, тогда массив будет иметь вид ( a [1], а [2], ..., а [к-1] ), а [к], ( а [к+1], ..., а [n] ).
Каждый из элементов a [1], a [2], ..., а [к - 1] меньше либо равен а [к], каждый из элементов а [к+1],..., а [n] больше а [к]. Отсюда можно сделать вывод, что элемент а [к] стоит на своем месте. А исходный массив при этом разделится на две неотсортированные части, барьером между которыми является элемент а [к].
Для дальнейшей сортировки необходимо применить пп.1, 2 для каждой из этих частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.
Одной из целей сортировки является облегчение последующего поиска элементов в отсортированном множестве. Результатом поиска служит элемент множества, равный эталону, или отсутствие такового.
Пример решения задачи.
Задание:
Составить программу «быстрой сортировки».
Решение:
Пусть исходный массив состоит из восьми элементов:
8 12 3 7 19 11 4 16
В качестве барьерного элемента будем брать средний элемент массива. Барьерный элемент - 7. Произведя необходимые перестановки для разделения, получим:
Число 7 стоит на своем месте. Далее сортируем подмассивы, элементы которых заключены в скобки. Этот процесс будем повторять до тех пор, пока не получим полностью отсортированный массив.
Массив отсортирован полностью.
Алгоритм «быстрой» сортировки можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива.
Program Example;
var a : array[1..10] of integer;
Procedure init; {формирование массива из файла}
var f : text;
i: integer;
Begin
assign ( f , ' c : \ s . dat ' ); reset ( f );
for i : = l to 10 do read ( f , a [ i ] );
End;
Procedure Print; {печать массива}
var i : integer;
Begin
for i : = l to 10 do Write ( a [ i ] : 5);
writeln
End;
Procedure Quick_sorting ( m, 1: integer);
var i, j, x, w: integer;
Begin
i : = m; j : = l; x : = a [ ( m + l ) div 2 ];
repeat
while a [ i ] < x do inc ( i );
while a [ j ] > x do dec ( j );
if i < j then
Begin
w : = a [ i ]; a [ i ] : = a [ j ]; a [ j ] : = w; inc ( i); dec ( j );
End
until i > j;
if m < j then quick_sorting ( m, j ) ;
if i < l then quick_sorting ( i, 1 );
End;
Begin {основная программа}
writeln ( 'массив: ' ); init; print; quick_sorting ( 1, 10 );
writeln ( 'отсортированный массив' ); print;
End.
Заключение
Основными достоинствами языка Паскаль являются лёгкость при изучении и наглядность и простота написания программ. Кроме того, в Паскале отражена концепция структурного программирования, имеется богатый набор различных типов данных и программные средства, позволяющие доказывать правильность написанных программ, в том числе и программ, использующих алгоритмы сортировки.
В курсовой работе нами были подробно описаны следующие виды сортировок:
А также рассмотрены примеры задач и приведены алгоритмы их выполнения на Паскале с применением данных сортировок.
Сравнивая различные методы сортировок,
можно сделать следующие
Список используемой литературы
по системному программированию: Пер. с англ. - М.: Наука, 1979.
Информация о работе Среда программирования Free Pascal. Методы сортировки