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

         На алгоритмах сортировки наглядно демонстрируется насколько разными путями можно прийти к одной цели – получению упорядоченного массива.

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

         Зачем нужна сортировка? Когда элементы отсортированы, их проще найти, производить с ними различные операции. Легче определить пропущенные элементы. Легче найти общие элементы двух массивов. Сортировка влияет на скорость алгоритма, в котором нужно обратиться к определённому элементу массива.

         Чаще всего выполняют сортировки по возрастанию (<), по убыванию (>), по невозрастанию (>=) и по неубыванию (<=).

1. Сортировка обменом (метод пузырька).

         Суть метода. Все соседние элементы массива попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше последующего. В результате этого максимальный элемент постепенно смещается вправо и в конце концов занимает крайнее правое место в массиве, после чего исключается из дальнейшей обработки. Затем процесс повторяется, и сове место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так до тех пор, пока вся последовательность не будет упорядочена.

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

Как улучшить. Можно включить условие проверки – если на очередном проходе не сделано ни одного обмена, то массив стал упорядоченным, и его сортировку можно прекратить.

Модификация пузырькового метода. Шейкер-сортировка. Сортировка проходит в массиве в обоих направлениях, а не только от его начала к концу.

         В работе с большими массивами преимущество шейкер-сортировки уменьшается за счёт использования двух циклов.

2. Сортировка выбором.

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

3. Сортировка методом прямого включения (простыми вставками).

Суть метода. Просматриваются элементы массива, начиная со второго. Каждый новый элемент А[i] вставляется на подходящее место в уже упорядоченную последовательность А[1], ..., A[i-1]. Это место определяется последовательными сравнениями элемента A[i] с упорядоченными элементами A[1], …, A[i-1].

         Сортировки обменом, выбором, методом прямого включения требуют порядка  (N²-N)/2 операций сравнения.

4. Обменная сортировка с разделением (быстрая сортировка Хоара).

Суть метода. В исходном неотсортированном массиве выбрать некоторый элемент х=а[k] (барьерный элемент). Переставить элементы массива таким образом, чтобы слева от х оказались элементы, меньшие или равные х, а справа – элементы, большие х. разделив таким образом массив, можно сделать то же самое с обеими полученными частями, а затем – с частями этих частей и т.д., пока каждая часть будет содержать только один элемент.

Метод бинарного поиска элементов в массиве.

         Часто требуется провести поиск элемента в упорядоченном массиве. Например, массив фамилий упорядочен по алфавиту, массив результатов соревнований по прыжкам в длину упорядочен по убыванию.

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

         Суть метода. Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается. Если же средний элемент меньше искомого, то все элементы левее его также будут меньше искомого. следовательно, их можно исключить из дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остается левая.

         На втором этапе выполняются аналогичные действия над оставшейся половиной массива. В результате после второго этапа остается j-ая часть массива.

         Итак далее, пока элемент не будет найден или длина зоны поиска станет равной нулю. В последнем случае искомый элемент найден не будет.

Схема алгоритма бинарного поиска:

Шаг 1.

Поиск индекса среднего элемента i:=(m+k) Div 2. ( в нашем случае 4). Так как а[4]<15, то левая часть массива исключается из поиска и m:= i+1

Шаг 2.

Поиск индекса среднего элемента i:=(m+k) Div 2. ( в нашем случае 6). Так как а[6]>15, то правая часть массива исключается из поиска и k:= i-1

Шаг 3.

Поиск индекса среднего элемента i:=(m+k) Div 2. ( в нашем случае 5). а[5]=15

(Диктую условие задачи и предлагаю решить на компьютере в Pascale)

Задача: Дан упорядоченный по возрастанию массив. При помощи бинарного                         поиска, найти данный элемент.

         Программа бинарного поиска в упорядоченном по возрастанию массиве.

Program bin;

Const n=7;

Var

A: Array[1..n] Of integer;

i, m, k, x, p: integer;

Begin

For i:=1 to n do

begin

Write (‘Введите   ’, i, ‘  элемент’);

Readln(A[i]);

end;

write (‘Введите элемент для поиска:’);

readln(x);

m:=1; k:=n;

p:=0;

while (m<=k) and (p=0) do

begin

i:=(m+k) div 2;

If A[i]=x

Then p:=1

Else If A[i]<x

       Then m:=i+1

       Else k:=i-1;

end;

If A[i]=x

Then Writeln(‘Элемент  ’, x, ’в массиве имеет номер’, i)

Else Writeln(‘Элемента  ’, x, ’в массиве нет.’);

Readln

End.