Алгоритмы сортировки: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Нет описания правки |
||
Строка 46:
1, 2, '''3''' | 6, 9, 5.
Попробуем записать действия, которые нам предстоит проделать на шаге с номером ''k''. Сначала нам нужно найти наименьшее среди чисел, записанных в ''k'', ''k''+1, ..., ''N'' позициях массива. После этого нам нужно поменять этот элемент с ''k''-м.
Сколько таких шагов нужно сделать, чтобы полностью отсортировать массив? Напрашивается ответ "''N''", но не будем торопиться. Пусть сделан ''N-1'' шаг. Тогда в правой, неотсортированной части массива останется одно число. Какое это число? Ясно, что это самое большое число в массиве. Где оно в итоге должно оказаться? На последнем месте в массиве. Но оно уже и так там! Поэтому ''N''-й шаг алгоритма выполнять не нужно.
Таким образом, алгоритм можно записать следующим образом (на некотором условном языке, который мы нигде не будем описывать, но всюду будем использовать: надеемся, он будет интуитивно понятен всем читателям):
for k:=1 to N-1 do begin
Выполнить k-й шаг алгоритма
end
В чем заключается k-й щаг, мы уже тоже выяснили, поэтому можно расписать алгоритм подробнее:
for k:=1 to N-1 do begin
Найти наименьший среди элементов массива с номерами k..N
Поменять его местами с k-м элементом
end
Будем считать, что массив называется a, и напишем соответствующий код, вспомнив, как искать минимальный элемент и как менять два элемента местами:
for k:=1 to N-1 do begin
min:=k;
for i:=k+1 to N do
if a[i]<a[min] then min:=i;
temp:=a[min]; a[min]:=a[k]; a[k]:=temp;
end
Алгоритм сортировки поиском минимума реализован.
| |||