Пример сортировки массива по возрастанию методом выбора
Начинаем с первого элемента, который назовем изменяемым, потому что его значение будет изменяться.
Изменяемый элемент сравниваем по очереди с каждым из элементов массива, которые следуют за ним. Эти элементы будем называть текущими. Если значение текущего элемента оказывается меньше значения изменяемого, то значения этих элементов массива меняются местами.
Когда будут просмотрены все текущие элементы, то значение изменяемого элемента окажется меньшим из всех текущих.
Проиллюстрируем алгоритм этой сортировки рисунками. Исходное расположение элементов массива показано на рисунке 8.2.
Рисунок 8.2 – Исходная схема сортируемого массива
После обмена местами A[1] и A[2] массив будет иметь вид, показанный на рисунке 8.3.
Рисунок 8.3 – Схема сортируемого массива после первого обмена элементов
Далее будут сравниваться элементы A[3] и A[1], но так как A[3]не меньше A[1] , то A[3] остается на месте.
Анализ элемента A[4] показывает, что он меньше, чем A[1], поэтому его следует поменять местами с A[1]. Результат изменений показан на рисунке 8.4.
Рисунок 8.4 – Схема сортируемого массива после второго обмена элементов
Далее будут сравниваться элементы A[5] и A[1], но так как A[5]не меньше A[1] , то A[5] остается на месте.
На этом первый проход сортируемого массива заканчивается. В результате этого прохода в первой позиции массива оказался наименьший элемент.
Теперь необходимо осуществить второй проход по массиву, но в качестве изменяемого берется уже второй элемент массива. Со вторым элементом будут сравниваться элементы, начиная с третьего. В результате чего на второе место будет поставлен минимальный элемент среди элементов со 2-го по 5-й. Результаты второго прохода по массиву представлены на рисунке 8.5.
Рисунок 8.5 – Схема второго прохода при сортировке массива методом выбора
При третьем проходе в качестве изменяемого элемента выступает третий элемент массива, и с ним будут последовательно сравниваться элементы, начиная с четвертого. В результате третий и четвертый элементы поменяются местами.
При последнем, четвертом проходе изменяемым будет четвертый элемент, а сравниваться он будет с единственным, следующим за ним, элементом номер пять. Но в данном примере менять местами эти элементы не нужно.
Рисунок 8.6 – Схема последних проходов по массиву при сортировке методом выбора
Процедура сортировки массива методом выбора
procedure SortChoise (var a: TArray100; count: integer);
var i, j, x: integer;
begin
for i := 1 to count - 1 do
begin
for j := i + 1 to count do
if a[j] > a[i] then
begin
x := a[i];
a[i] := a[j];
a[j] := x;
end;
end;
end;
-
Сортировка обменом (метод пузырька)
Алгоритм основан на принципе сравнения и обмена пары соседних элементов.
Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами.
Рисунок 8.7 – Алгоритм сортировки по возрастанию методом обмена
В результате после первого прохода, при сортировке по возрастанию, наибольший элемент окажется на последнем месте.
Затем все повторяется заново и наибольший среди оставшихся элементов оказывается на предпоследнем месте.
Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут). Этот метод получил название метод пузырька, что, очевидно, если располагать массивы вертикально.
Могут быть случаи, когда значения в первоначальном массиве расположены так, что массив будет отсортирован намного раньше, чем будет сделан последний проход по массиву. Учитывая это, количество проходов в программе можно сократить, проверяя после окончания каждого очередного прохода по массиву, был ли сделан хоть один обмен значений элементов. Если обменов не было, сортировка закончена.
Схема алгоритма сортировки массива методом обмена показана на рисунке 8.7.
Сортировка реализуется с помощью двух циклов. Внешний цикл выполняется до тех пор, пока при завершении очередного прохода по массиву не окажется, что перестановок элементов делать не пришлось. В этом случае переменная ok сохранит значение true, и это будет означать, что массив отсортирован. Так как условие отсутствия перестановок элементов при проходе по массиву можно проверить только после завершения прохода, то очевидно, что в данном случае следует использовать цикл repeat ... until.
Во внутреннем цикле последовательно сравниваются соседние элементы массива, причем количество таких сравнений заранее известно. Поэтому для организации прохода по массиву используется цикл for. Максимальное значение параметра этого цикла после каждого прохода уменьшается, так как в результате каждого прохода максимальный элемент рассмотренной части массива оказывается в конце этой части, то есть занимает свое место в отсортированном массиве.