Программная реализация

Сортировка и поиск

1. ПОНЯТИЕ СОРТИРОВКИ.

Сортировка - это упорядочение данных по определенному признаку.

Рассмотрим одномерный массив целых чисел:

Const NMax=...;
Type MyArray=Array[l..NMax] Of Integer;
Var A:MyArray;

Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки. Эффективность оценивается количеством операций сравнения (порядком этого значения).

Элементы массива можно сортировать:
• по возрастанию — каждый следующий элемент больше предыдущего — А [1] < А [2] <... < A[N];

• по неубыванию — каждый следующий элемент не меньше предыдущего А[1] <= А [2] <=... <= A[N];

• по убыванию — каждый следующий элемент меньше предыдущего А[1] > А [2] >... > A[N];
• по невозрастанию — каждый следующий элемент не больше предыдущего А [1] >= А [2] >=... >= A [N].
СОРТИРОВКА ПРОСТЫМ ВЫБОРОМ

Рассмотрим идею данного метода на примере. Пусть исходный массив состоит из 10 элементов:
5 13 7 9 1 8 16 4 10 2
После сортировки массив должен выглядеть так:
1 2 4 5 7 8 9 10 13 16
Процесс сортировки представлен ниже. Максимальный элемент текущей части массива заключен в кружок, а элемент, с которым происходит обмен, — в квадратик. Скобкой помечена рассматриваемая часть массива, т.е. еще не упорядоченная.
1. Найдем в массиве максимальный элемент — 16 (стоит на седьмом месте), поменяем его местами с последним элементом — с числом 2.

Максимальный элемент помещен на свое место.

2. Рассмотрим часть массива — с первого до девятого элемента. Максимальный элемент этой части — 13, стоящий на втором месте. Поменяем его местами с последним элементом неупорядоченной части — с числом 10.

Отсортированная часть массива состоит теперь уже из двух элементов.

3. Уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент (его значение — 10) и последний элемент этой части — число 4.

В отсортированной части массива — 3 элемента.

Программная реализация.

Procedure Sortirovka;
Var i, j, k: Integer;
m:Integer; {Значение максимального элемента рассматриваемой части массива.}
Begin
For i:=N DownTo 2 Go Begin
{Цикл по длине рассматриваемой части массива.}
{Поиск максимального элемента и его номера в текущей части массива.}
k: =i; m: =А [ i ];
{Начальные значения максимального элемента и его индекса в рассматриваемой части массива.}
For j:=l To i-1 Do If A[j]>m Then
Begin:k:=j; m:=A[k] End;
If k<>i Then
{Перестановка элементов.)
Begin A[k]:=A[i],;A[i]:=m;End;
End;
End;

ЭФФЕКТИВНОСТЬ АЛГОРИТМА:

Оценим количество сравнений. При первом просмотре N — 1, при втором — N — 2, при последнем — 1. Общее количество С = N — 1+N — 2 +...+ 1= N• (N- l)/2, или C=O(N²).

ЗАДАНИЯ:

I уровень:

1. Модифицировать алгоритм так, чтобы осуществлялась сортировка:
• четных элементов массива;
• элементов, записанных на нечетных местах;
• отрицательных элементов массива.

СОРТИРОВКА ПРОСТЫМ ОБМЕНОМ (метод "пузырька")

Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более "легкие" элементы (элементы с заданным свойством) всплывают на "поверхность".

Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов: 5 2 8 4 9. Длина текущей (неупорядоченной) части массива — (N — k + 1), где k — номер просмотра,

i — номер первого элемента проверяемой пары,

N — k - номер последней пары.
Первый просмотр: рассматривается весь массив.
i= 1 5 4 8 2 9 (k=1, i=1, N-k=4) > меняем

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= 1 4 2 5 8 9 > меняем
i= 2 2 4 5 8 9 < не меняем 5 — на своем месте.

Четвертый просмотр: рассматриваем последнюю пару элементов.
i= 1 2 4 5 8 9 < не меняем 4 — на своем месте.
Наименьший элемент — 2 оказывается на первом месте. Количество просмотров элементов массива равно N-1.
РЕАЛИЗАЦИЯ АЛГОРИТМА:

Procedure Sort;
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+l];A[i+l]:=t;
End; End;

ЭФФЕКТИВНОСТЬ АЛГОРИТМА:

При сортировке методом "пузырька" выполняется N — 1 просмотров, на каждом i -м просмотре производится N — i сравнений. Общее количество С равно N* (N—1)/2,или O(N²).

ЗАДАНИЯ: II уровень:

1.Дан массив 12 3 5 7 9 10. За один просмотр он становится отсортированным, остальные просмотры ничего не дают. Исключить лишние просмотры.
2. Массив 12 3 5 7 9 10 сортируется за один просмотр, а массив 5 7 9 10 12 3 — за пять. Сократить количество просмотров можно путем смены направлений, т.е. сначала в направлении —> получаем 5 7 9 10 3 12, а затем в направлении <-- результат — 3 5 7 9 10 12. Итак, чередуем направления, пока массив не будет отсортирован.

III уровень:
3. Интегрируя задания 1 и 2, мы получаем при соответствующей технике программирования красивый программный код с использованием рекурсии. Название этого алгоритма — "шейкер-сортировка". Реализовать его.