Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом, и так далее для всех элементов до n-1-го.
Можно так же найти элемент с максимальным значением и поменять его местами с последним элементом. На втором шаге найти элемент с максимальным значением на интервале от 1-го до n-1 го элемента и поменять его местами с предпоследним элементом и т.д.
Программа, реализующая рассмотренный метод, будет иметь следующий вид:
……………………………..
for s:=1 to n-1 do
Begin
{поиск минимального элемента в диапазоне от s-го элемента до n-го}
Min:= a[s];
Imin:=s;
for i:=s+1 to n do
if a[i]<Min then
Begin
Min:=a[i];
Imin:=i;
End;
{обмен местами минимального и s-го элементов}
a[Imin]:=a[s];
a[s]:=Min;
end;
……………………………….
В этой программе цикл for для переменной s используется для вставки минимального элемента на правильное s-тое место в массиве. Цикл for для переменной i используется для нахождения минимального элемента и его порядкового номера.
Рассмотрим принцип работы методом выбора на примере массива
При s=1 переменная Min принимает значение 5, а Imin=1. Цикл for для переменной i заканчивается при значениях Min=1, Imin=5. Меняя местами первый и пятый элемент, получаем массив
При s=2 переменная Min принимает значение 9, а Imin=2. Цикл for для переменной i заканчивается при значениях Min=3, Imin=3. Меняя местами второй и третий элемент, мы получаем массив
При s=3 переменная Min принимает значение 9, а Imin=3. Цикл for для переменной i заканчивается при значениях Min=4, Imin=6. Меняя местами третий и шестой элемент, мы получим массив
При s=4 переменная Min принимает значение 7, а Imin=4. Цикл for для переменной i заканчивается при значениях Min=5, Imin=5, а меняя местами четвертый и пятый элемент, мы получим массив
При s=5 переменная Min принимает значение 7, а Imin=5. Цикл for для переменной i заканчивается при значениях Min=7, Imin=5. В этом случаи меняется местами пятый элемент с пятым элементом, т.е. 7 остается на своем месте, и мы получаем отсортированный массив.
"Пузырьковая" сортировка
Идея метода:
Слева направо сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент ("всплыл" первый "пузырек"). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента и так далее. Всего требуется n-1 прохода.
Программа, реализующая метод обмена ("пузырька"), будет иметь следующий вид:
………………………………
For k:=n downto 2 do
{"Всплывание" очередного максимального элемента на k-ую позицию}
for i:=1 to k-1 do
if a[i]>a[i+1] then
Begin
B:=a[i];
a[i]:=a[i+1];
a[i+1]:=B;
end;
……………………………….
Здесь цикл for для переменной k предназначен для организации n-1 прохода, а цикл for для переменной i предназначен для сравнивания двух рядом стоящих элементов и, в случае неудовлетворения условия сортировки, перемены их мест.
Рассмотрим работу метода пузырька на примере массива
В цикле for переменная k пробегает значения от 6 до 2-х. При значении k=6 i принимает значения от 1 до 5. Мы получаем следующие результаты:
При i=1
При i=2
При i=3
При i=4
При i=5
При значении k=5 переменная i принимает значения от 1 до 4. Мы получаем следующие результаты:
При i=1
При i=2
При i=3
При i=4
При значении k=4 переменная i принимает значения от 1 до 3. Мы получаем следующие результаты:
При i=1
При i=2
При i=3
При значении k=3 переменная i принимает значения от 1 до 2. Мы получаем следующие результаты
При i=1
При i=2
При значении k=2 переменная i принимает значения от 1 до 1. Мы получаем следующие результаты
При i=1
После всего этого мы получаем отсортированный массив.
