Простой выбор

Простейшая сортировка, построенная на этой идее, состоит из следующих шагов:

1. Найти наименьший ключ, после чего выбрать соответствующую

ему запись и переслать её в начало некоторой пустой области

памяти (т.н. область вывода).Так, как операция ввода соответствует чтению данных и не

удаляет физически запись из сортируемого файла, то удаление имитируется заменой ключа на значение “∞” (∞ по предположению больше любого реального ключа.)

2. Повторить шаг 1. На этот раз будет найден ключ, наименьший из оставшихся.

3. Повторять шаг 1 до тех пор, пока не будут выбраны все N записей.

Этот метод требует наличия всех исходных элементов до начала сортировки, а элементы вывода он порождает последовательно, один за другим. Картина по существу противоположна методу вставок, в котором исходные элементы должны поступать последовательно, но вплоть до завершения сортировки ничего не известно об окончательном выводе.

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

Недостатки этого метода очевидны, если использовать последовательное размещение записей файла в памяти:

- большое число сравнений N(N-1);

- необходима дополнительная память.

Этот метод можно модифицировать следующим образом:

выбранную на очередном шаге запись помещать в тот же самый файл на место, соответствующее месту в случае использования области вывода, а находящуюся на этом месте запись перенести на место выбранной. При этом отпадает необходимость в использовании ∞ и количество просматриваемых элементов с каждым шагом сокращается на 1.

Поиск по сайту: