Сортировка простым выбором

  Рассмотрим идею данного метода на примере. Пусть исходный массив состоит из 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 элемента.

4-й шаг.

5-й шаг. Максимальный элемент этой части массива   является последним в ней, поэтому его нужно оставить на месте.

6-й шаг.

7-й шаг.

8-й шаг.

9-й шаг.

Фрагмент программной реализации.

Procedure Sort; 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²).

Методические рекомендации. Выше приведен материал на 10— 15 минут занятия. В качестве заданий для самостоятельной работы можно предложить: 1. Модифицировать алгоритм так, чтобы осуществлялась сортировка: • четных элементов массива; • элементов, записанных на нечетных местах; • отрицательных элементов массива и т.д. 2. Пусть N является точным квадратом натурального числа, например, 3. Разделим массив на групп по элементов в каждой. Выберем максимальный элемент в каждой группе... Лучше рассмотреть пример попроще. Дан массив 7 10 3 5 15 9 6 12 8. При разбивке на группы - (7 10 3) (5 15 9) (6 12 8). Максимальные элементы 10 15 12. Максимальный из них 15, он во второй группе. Если оставшиеся элементы из второй группы, а это 5 и 9, меньше 10 и 12, то мы нашли сразу три элемента, записываемые на свои места. Если нет, то заменяем максимальные элементы элементами из группы. Этот метод был предложен Э.Х. Фрэндом в 1956 году и получил название метода квадратичного выбора. Количество сравнений имеет порядок O(N• ). Метод интересен с точки зрения проверки техники программирования.

Сортировка простым обменом

Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов: 5 1 8 4 9. Длина текущей (неупорядоченной) части массива — (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= 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²).

Задания для самостоятельной работы

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. Итак, чередуем направления, пока массив не будет отсортирован. 3. Интегрируя задания 1 и 2, мы получаем при соответствующей технике программирования красивый программный код с использованием рекурсии. Название этого алгоритма — "шейкер-сортировка".