Занятие 1. Сортировка массива. Способы сортировки массива.

Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта. Например, в преферансе игроки раскладывают карты по мастям и по значению. Так легче определить, каких карт не хватает. Или возьмем любой энциклопедический словарь – статьи в нем упорядочены в алфавитном порядке.

Перегруппирование заданного множества объектов в определенном порядке называют сортировкой.

Почему сортировке уделяется большое внимание? Вы это поймете, прочитав цитаты двух великих людей.

"Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования." /Д. Кнут/

"Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки." /Н. Вирт/

Отличительной особенностью сортировки является то обстоятельство, что эффективность алгоритмов, реализующих ее, прямо пропорциональна сложности понимания этого алгоритма. Другими словами, чем легче для понимания метод сортировки массива, тем ниже его эффективность.

Сегодня существует множество методов сортировки, но для понимания сути сортировки рассмотрим некоторые из них.

Но прежде чем перейти к рассмотрению конкретного алгоритма той или иной сортировки немного вспомним материал, который пригодится нам в дальнейшем.

Задача. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.

Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.

if x<y

then

begin

t:=x;

x:=y;

y:=t;

end;

Задача. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.

Пусть а, b, c – вводимые с клавиатуры числа, Max – максимальное из их значений. На первом шаге предположим , что а – максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то переопределим значение максимума.

. . .

m:=a;

if m<b

then

m:=b;

if m<c

then

m:=c;

. . .

Задача. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.

Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.

. . .

Max:=a[1];

for i := 2 to 10 do

if Max<a[i]

then

Max := a[i];

. . .

До написания программ Вам необходимо выполнить некоторую подготовительную работу – написать шаблон программы следующего содержания:

Рrogram Sorting;

Сonst

n = ... ; {количество элементов в массиве}

Type

TArray = array [1..n] of integer;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure FillArray (Var a: TArray);

Var

i: integer;

Begin

for i: = 1 to n do

a [i] := Random(100);

End; {конец процедуры}

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure PrintArray (a: TArray);

Var

i: integer;

Begin

for i: = 1 to n do

write (a [i]: 3, ' ');

writeln;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin {Главная программа}

writeln('Сортировка МЕТОДОМ . . .');

writeln('Заполняем исходный массив: ');

FillArray (a);

PrintArray (a);

AnySort (a, b);{имя процедуры, реализующей данный метод}

writeln('Отсортированный массив: ');

PrintArray (b);

End.

Для реализации различных методов сортировки Вам необходимо подготовить несколько вспомогательных процедур и функций.

1. Функция, которая ищет минимальный элемент правее некоторого заданного и возвращает его номер в качестве результата. Аргументами функции являются номер элемента массива и обрабатываемый массив:

2. Большинство методов сортировок основаны на обмене двух чисел. Для этой цели предназначена процедура, которая в качестве параметров берет два числа и меняет их значения

3. Также Вам пригодится процедура, которая берет элемент с индексом i, перемещает его на место элемента с номером j. А все элементы, которые имеют индексы от j до i-1 сдвигает на одну позицию вправо.

Задание. Подготовьте программу-шаблон, содержащую все рассмотренные выше процедуры и функции.