Автор: Пользователь скрыл имя, 08 Мая 2012 в 09:12, курсовая работа
Free Pascal обладает целым рядом преимуществ по сравнению с остальными разработками Паскаля. Ведь Free Pascal - это свободно распространяемая версия языка Паскаль с открытыми исходными кодами. Он постоянно дорабатывается, обрастает новыми возможностями, расширениями языка, поддержкой новых платформ и процессоров. В комплекте идут полные исходные тексты компилятора.
Одной из особенностей языка Паскаль является использование блочного подхода. Это означает, что большую задачу можно разделить на более мелкие подзадачи, что успешно реализовывается в задачах по сортировкам. Именно такой подход носит название структурного или блочного программирования.
Введение 3
1. Сортировка вставками 4
2. Сортировка методом простого выбора 11
3. Сортировка методом прямого включения 14
4. Сортировка методом слияния 17
5. Обменная сортировка с разделением 20
Заключение 23
Список используемой литературы 24
i = 4 4 5 2 8 9
Число 9 стоит на своем месте.
Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.
i = 1 4 5 2 8 9
< не меняем
i = 2 4 5 2 8 9
> меняем
i = 3 4 2 5 8 9
Число 8 стоит на своем месте.
Третий просмотр: рассматриваемая часть массива содержит три первых элемента.
i = l 4 2 5 8 9
> меняем
i = 2 2 4 5 8 9
< не меняем
Число 5 стоит на своем месте.
Четвертый просмотр: рассматриваем последнюю пару.
i = 1 2 4 5 8 9
Число 4 стоит на своем месте. Для самого маленького элемента (2) остается только одно место — первое.
Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод называют также методом «пузырька».
Опишем процедуру «пузырьковой» сортировки.
Procedure sorting2(var a : ar );
var k , i , t : integer;
{k - номер просмотра (изменяется от 1 до n-1),
i - номер рассматриваемой пары,
t - промежуточная переменная для перестановки местами элементов}
Begin
for k : = l to n - 1 do {цикл по номеру просмотра}
for i : = l to n - k do
if a [ i ] > a [ i + l ] then {перестановка элементов}
Begin
t : = a [ i ]; a [ i ] : = a [ i + 1 ]; a [ i + l ] : = t
End;
End.
2. Сортировка методом простого выбора
Эта сортировка обычно применяется для массивов, не содержащих повторяющихся элементов. Для достижения поставленной цели можно действовать следующим образом:
1) выбрать максимальный элемент массива;
2) поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте);
3) повторить пп.1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним (n-1)-м элементом, затем с оставшимися n-2 элементами и так далее, пока не останется один (наименьший) элемент, уже стоящий на своем месте.
Пример решения задачи.
Задание:
Пусть исходный массив a состоит из 10 элементов и имеет вид
5 13 7 9 1 8 16 4 10 2
Решение:
После сортировки массив должен выглядеть так:
Процесс сортировки представлен ниже. Максимальный элемент текущей части массива заключен в кружок, а элемент, с которым происходит обмен, в квадратик. Скобкой помечена рассматриваемая часть массива.
1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент — 16
(стоит на седьмом месте), поменяем его местами с последним элементом — с 2.
Максимальный элемент записан на свое место.
2-й шаг: рассмотрим часть массива — с первого до девятого элемента. Максимальный
элемент этой части — 13, стоящий на втором месте. Поменяем его местами
с последним элементом этой части — с 10
Отсортированная часть массива состоит теперь уже из двух элементов.
3-й шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь
надо поменять местами второй элемент (его значение — 10) и последний элемент
этой части — 4.
5-й шаг: максимальный элемент этой части массива является последним в ней,
поэтому его надо оставить на старом месте.
Далее действуем аналогично.
6-й шаг:
7-й шаг:
8-и шаг:
9-й шаг:
Итого:
1 2 4 5 7 8 9 10 13 16
Для программной реализации этого процесса необходимо организовать цикл по i — длине рассматриваемой части массива, которая изменяется от n до 2.
В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части.
Теперь можем записать алгоритм сортировки:
For i : = n downto 2 do
Begin
найти максимальный элемент из а [ 1 ] , . . . , a [ i ];
запомнить его индекс в переменной к;
если i <> k поменять местами a [ i ] и а [к]
End;
Опишем этот алгоритм подробно в виде процедуры:
Procedure sortingl (var a : ar); {поскольку в процессе работы процедуры массив изменится, формальный параметр а описывается как параметр-переменная}
var i, j, k : integer;
m: integer; {значение максимального элемента рассматриваемой части массива}
Begin
for i : = 10 downto 2 do {цикл по длине рассматриваемой части массива}
Begin {поиск максимального элемента и его номера в текущей части
массива}
k : = i; m : = a [ i ]; {начальные значения макс, элемента и его
индекса в рассматриваемой части массива}
for j : = 2 to i - 1 do
if a [ j ] > m then
if k <> i then
Begin {перестановка элементов}
End;
End;
End.
3. Сортировка методом прямого включения
Сортировка этим методом производится последовательно шаг за шагом. На к-м шаге считается, что часть массива, содержащая первые к-1 элемент, уже упорядочена, то есть а [ 1 ] ≤ а [ 2 ] ≤...≤ а [ к – 1 ]. Далее необходимо взять к-й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое j (1 ≤ j ≤ k – 1 ), что a [ j ] ≤ а [ к ] ≤ a [ j + l ]. Затем надо вставить элемент а [ к ] на найденное место. С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить п-1 шаг.
Пример решения задачи.
Задание:
Требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения:
Решение:
Рассматриваем часть массива из одного элемента (13). Надо вставить в нее второй элемент массива (6) так, чтобы упорядоченность сохранилась. Так как 6 < 13, вставляем 6 на первое место. Отсортированная часть массива содержит два элемента (6 13).
Возьмем третий элемент массива (8) и подберем для него место в упорядоченной части массива. 8 > 6 и 8 < 13, следовательно, его надо вставить на второе место.
Следующий элемент — 11. Он записывается в
упорядоченную часть массива на третье место, так как 11 >
8, но 11 < 13.
Далее, действуя аналогичным образом, определяем, что 3
необходимо записать на первое место.
По той же причине 1 записываем на первое место.
Так как 5 > 3, но 5 < 6, то место 5 в упорядоченной части —
третье.
Место числа 9 — шестое.
Определяем место для предпоследнего элемента 15.
Оказывается, что этот элемент массива уже находится на
своем месте.
Осталось подобрать подходящее место для последнего
элемента (7).
Массив отсортирован полностью.
Сейчас можно коротко описать фрагмент алгоритма сортировки с помощью простого включения:
for k : = 2 tо n do {так как начинаем сортировку с поиска подходящего места для а [2], i изменяется от 2 до п}
Begin
x : = a [ k ];
"вставить х на подходящее место в а [ 1 ] , . . . , а [ к ] "
End;
Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Надо просматривать элементы a [ j ], j изменяется от k - 1 до 1.
Такой просмотр закончится при выполнении одного из следующих условий:
• найден элемент a [ j ] < x, что говорит о необходимости вставки х между a [ j – l ] и a [ j ];
• достигнут левый конец упорядоченной части массива, следовательно, надо вставить х на первое место.
До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на 1 позицию вправо, в результате чего в отсортированной части будет освобождено место под х.
Учитывая это, опишем процедуру сортировки:
Procedure Sorting3(var a : ar);
var k, j, x : integer;
Begin
for k : = 2 to n do
Begin
x : = a [ k ]; j : = k - l;
while ( j > 0 ) and ( x > = a [ j ] ) do
Begin
a [ j + l ] : = a [ j ]; dec ( j )
End;
a [ j + l ] : = x
End;
End.
4. Сортировка методом слияний
Этот метод состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности, и в последующем составлении из нескольких уже упорядоченных массивов искомого упорядоченного массива.
Пусть массив a [1..n] разбивается на части длиной к, тогда первая часть — а [1], a [2],..., а [к], вторая — а [к+1], а [к+2], ..., а[2к] и так далее. Если п не делится на к, то в последней части будет менее к элементов.
После того как массивы-части упорядочены, можно объединить их в упорядоченные массивы-части, состоящие не более, чем из 2к элементов, которые далее объединить в упорядоченные массивы длиной не более 4к, и так далее, пока не получится один искомый массив.
Таким образом, чтобы получить отсортированный массив этим методом, надо многократно «сливать» два упорядоченных отрезка массива в один упорядоченный отрезок. При этом другие части массива не затрагиваются.
Пример решения задачи.
Задание:
Пусть первая часть массива (часть a) состоит из пяти элементов:
а вторая часть (часть b) — из восьми элементов:
... 1 6 7 9 12 13 18 20...
Информация о работе Среда программирования Free Pascal, методы сортировки