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

Идея сортировки посредством выбора в следующем: на i -ом этапе сортировки выбирается запись с наименьшим ключом среди записей R[i],..., R[п] и меняется местами с записью R[i]. В результате после i-ro этапа все записи R[1],..., R[i] будут упорядочены. Сортировку посредством выбора можно описать следующим образом:

Листинг 8. Сортировка посредством выбора

Var

lowkey:keytype;

{ текущий наименьший ключ,

найденный при проходе

по элементам R[i],..., R[n] }

lowindex: integer;

{ позиция элемента с ключом lowkey }

Begin

(1) for i:= 1 to n - 1 do

Begin

(2) lowindex:= i;

(3) lowkey:= R[i].K;

(4) for j:= i + 1 to n do

{ сравнение ключей с текущим ключом lowkey }

(5) if R[j].K < lowkey then

Begin

(6) lowkey:= R[j].K;

(7) lowindex:= j

end;

(8) swap(R[i], R[lowindex])

End

end;

Для разнообразия блок-схема представлена поиском максимального элемента из еще неотсортированных.

Заметим, что в методе пузырьком производится меньше сравнений, чем при простом выборе, и она, как может показаться, предпочтительнее. Но в действительности "пузырек" в два раза медленнее простого выбора из-за того, что в "пузырьке" производится слишком много обменов, а в простом выборе обменов всего их не более N-1.

Возможно ли усовершенствование алгоритма простого выбора? То есть можно ли находить максимум более быстрым способом? Ответ: НЕТ.

Лемма. В любом алгоритме нахождения максимума из n элементов, основанном на сравнении пары элементов, необходимо выполнить по крайней мере n –1 сравнений.

Доказательство. Если произведено менее n-1 сравнений, то найдутся по крайней мере два элемента (максимальный и нерассмотренный), для которых не было обнаружено ни одного элемента, превосходящего их по величине. Следовательно, мы не узнаем, который из этих двух элементов больше, и, значит, не сможем определить максимум. (конец)