Среда программирования Free Pascal, методы сортировки
Федеральное агентство по образованию
ГОУ ВПО Тульский государственный педагогический
университет им. Л. Н. Толстого
Курсовая работа на тему:
Среда программирования Free Pascal
Методы сортировкиок
Выполнила:
Проверила:
Тула 2009
Содержание
Введение
1. Сортировка вставками
2. Сортировка методом простого выбора
3. Сортировка методом прямого включения 14
4. Сортировка методом слияния
5. Обменная сортировка с разделением 20
Заключение
Список используемой литературы 24
Введение
Free Pascal обладает целым рядом преимуществ по сравнению с остальными разработками Паскаля. Ведь Free Pascal - это свободно распространяемая версия языка Паскаль с открытыми исходными кодами. Он постоянно дорабатывается, обрастает новыми возможностями, расширениями языка, поддержкой новых платформ и процессоров. В комплекте идут полные исходные тексты компилятора.
Одной из особенностей языка Паскаль является использование блочного подхода. Это означает, что большую задачу можно разделить на более мелкие подзадачи, что успешно реализовывается в задачах по сортировкам. Именно такой подход носит название структурного или блочного программирования.
Таким образом, Free Pascal обладает рядом возможностей, очень удобных для пользователя при составлении программ по сортировкам. Для решения задач удобно сначала упорядочить данные по определенному признаку. А процесс упорядочения заданного множества объектов по заданному признаку и называется сортировкой. Поэтому темой нашей курсовой работы была выбрана: «Среда программирования Free Pascal. Методы сортировки».
В данной курсовой работе будут рассмотрены основные виды сортировок с подробными описаниями и примерами решения задач, выполненных в среде программирования Free Pascal.
1. Сортировка вставками (метод «пузырька»)
Разберем подробно несколько вариантов алгоритма сортировки простыми вставками, который используется в качестве примера при обсуждении других языков.
Итак, пусть требуется расположить в порядке неубывания (речь идёт о сортировке «по неубыванию», а не о сортировке «по возрастанию», поскольку в массиве могут быть элементы с одинаковыми значениями) n элементов массива a, содержащего вещественные числа. Запишем описание типа массива (при выборе названия типа для массива использовался принцип «венгерской нотации». Первая строчная буква t в имени типа tArray подчёркивает природу этого наименования (t – от type). Такой принцип обозначений был предложен сотрудником Microsoft, венгром по происхождению, Чарльзом Симонаи (Charles Simonyi)):
const
nmax = 10000;
type
tArray = array [l..nmax] of real;
Сортировка вставками - это простой и очень естественный алгоритм упорядочения. Именно таким способом мы часто выполняем сортировку вручную.
Для упорядочения по неубыванию элементов массива поступим так (рис. 1): выберем второй по порядку элемент и разместим его должным образом по отношению к первому. То есть если значение второго элемента больше или равно значению первого, то второй оставляем на своем месте, если нет — расположим его перед первым, сдвигая первый на второе место. Теперь первые два элемента упорядочены. Берем следующий, третий и вставим его в нужное место по отношению к первым двум. Теперь упорядочены первые три. Берем поочередно следующие, вплоть до последнего, и помещаем каждый в нужное место уже упорядоченной последовательности предыдущих. Отыскивая подходящее место для данного элемента, можно просто последовательно просматривать предшествующие, начиная с того, который расположен перед выбранным. Как только встречается элемент со значением меньшим или равным выбранному, помещаем выбранный сразу за таким элементом. В процессе просмотра и движения в сторону меньших номеров (влево на схеме) сдвигаем вправо на одну позицию каждый элемент, который будет располагаться правее выбранного в упорядоченном массиве.
Запишем этот алгоритм на Паскале. Обозначим i — номер выбранного элемента; х — значение i-го элемента.
for i : = 2 to n do begin
x : = a [ i ];
{Вставить x в последовательность предшествующих ему элементов}
end;
Детализируя вставку ί-го элемента в последовательность элементов с номерами от ί-1 до 1, обозначим j - номер элемента, с которым сравнивается значение х (ί-й элемент). Оформляя решение как процедуру, получаем:
{Сортировка простыми вставками}
procedure InsSort (var a: tArrav; n : integer);
var
i, j : integer;
x : real;
begin
for i : = 2 to n do begin
x : = a [ i ]; {выбор элемента}
j : = i - 1;
while (j > 0) and (x > a [ j ]) do begin
a [ j + l ] : = a [ j ]; {сдвиг вправо}
j : = j - 1; {движение влево}
end;
a [ j + l ] : = x; {x попадает на свое место}
end;
end;
Использованная запись условия в цикле while предполагает, что действует короткая схема вычисления логических выражений, то есть если условие (j>0), записанное перед and, не выполняется, то условие, записанное после and, вообще не проверяется, а, значит, не происходит и обращения к несуществующему (нулевому) элементу массива. Левая часть составного условия как бы защищает правую от вычисления при недопустимом значении j. Современные компиляторы Паскаля обеспечивают вычисления по короткой схеме.
Можно попытаться ускорить работу программы, а заодно избавиться от опасности обращения к несуществующему элементу массива. Для этого дополним массив нулевым элементом, для чего придется изменить описание типа:
type
tArray = array [0..nmax] of real;
Сортировать при этом по-прежнему будем элементы с номерами от 1 до n, а элемент а [0] будет исполнять роль барьера. Перед каждым циклом вставки будем помещать в элемент а [0] значение х. Это позволит упростить условие внутреннего цикла, отказавшись от проверки (j >0). Корректное завершение цикла при этом гарантируется тем, что при сравнении х с a [0] условие х < а [j] нарушается, поскольку при j = 0 значение х будет равно а [0]. Барьер не преодолеть. Проверка условия цикла выполняется многократно, и его упрощение позволяет надеяться на заметное ускорение работы программы.
{Сортировка вставками с барьером}
procedure InsSort (var a: tArray; n: integer);
var
i, j : integer;
x : real;
begin
for i : = 2 to n do begin
x : = a [ i ] ;
a [ 0 ] : = x; {установка барьера}
j : = i - 1;
while x < a [ j ] do begin
a [ j + l ] : = a [ j ]; {сдвиг вправо}
j : = j - 1; {движение влево}
end;
a [ j + l ] : = x; {x попадает на свое место}
end;
end;
Наконец, можно заметить, что от переменной х можно вообще отказаться, сэкономив на присваивании ей значения. Роль х будет исполнять а [0]. При этом можно рассчитывать, что время обращения к элементу массива а [0] будет не больше времени доступа к неиндексированной переменной х. Большинство компиляторов обращается с элементами массивов, имеющими константные индексы, как с простыми переменными.
{Сортировка вставками с барьером. Вариант 2}
procedure InsSort (var a: tArray; n: integer);
var
i, j : integer;
begin
for i : = 2 to n do begin
a [ 0 ] : = a [ i ]; {установка барьера}
j : = i - 1;
while a [ 0 ] < a [ j ] do begin
a [ j + l ] : = a [ j ]; {сдвиг вправо}
j : = j - 1; {движение влево}
end;
a [ j + l ] : = a [ 0 ]; {a [ i ] попадает на свое место}
end;
end;
При упорядочении массивов с большим числом элементов сортировка вставками неэффективна. Количество выполняемых ею действий в среднем пропорционально n2, что является плохим показателем для алгоритмов сортировки. Но если число элементов не превышает 20, да к тому же эти элементы частично упорядочены, то сортировка вставками работает быстрее других алгоритмов. Поэтому ее используют при построении усовершенствованных алгоритмов в качестве вспомогательного средства для сортировки коротких частей массива. Для такого случая можно предусмотреть еще одну оптимизацию.
Если массив частично отсортирован, то нередко будет встречаться ситуация, когда выбранный ί-й элемент массива возвращается на свое же место, поскольку оказывается больше или равен предыдущему элементу. При этом происходят несколько ненужных в этом случае присваиваний. Предусмотрев отдельную проверку для сравнения ί-го элемента с предыдущим, лишних присваиваний можно избежать.
{Сортировка короткого частично упорядоченного массива}
procedure InsSort(var a: tArray; n: integer);
var
i, j : integer;
x : real;
begin
for i : = 2 to n do begin
x : = a [ i ] ;
if x < a [ i – l ] then begin
a [ i ] : = a [ i - 1 ];
j : = i - 2;
while ( j > 0 ) and ( x < a [ j ] ) do begin
j : = j - 1; {движение влево}
end;
a [ j + l ] : = x; {x попадает на свое место}
end;
end;
end;
Хотя выигрыш от этой модификации не будет большим, получившаяся программа хороша для нас тем, что кроме циклов for и while включает и конструкцию if и при использовании в качестве примера, полнее иллюстрирует средства обсуждаемых языков программирования.
К этому варианту можно применить идею барьера, но если имеется в виду сортировка подмассивов, то для барьера нет места.
Пример решения задачи.
Задание:
Отсортировать по возрастанию методом простого обмена массив из пяти элементов:
Решение:
Длина текущей части массива — n – k + 1, где k — номер просмотра, i — номер проверяемой пары, номер последней пары — n - k. За вертикальной чертой располагаются отсортированные элементы.
Первый просмотр: рассматривается весь массив.
i = 1 5 4 8 2 9
> меняем
i = 2 4 5 8 2 9
< не меняем
i = 3 4 5 8 2 9
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...