АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. Методы выбора инновационной политики
  2. IV. Выбор и проектирование инновационных образовательных технологий
  3. А) Аутентичность - полное осознание настоящего момента, выбор способа жизни в данный момент, принятие ответственности за свой выбор
  4. БЕЗДЕТНАЯ СЕМЬЯ В РОССИИ: ПОЛИТИКА ГОСУДАРСТВА И ВЫБОР СУПРУГОВ
  5. В обеих формах реализации права граждан на выбор места работы проявляется важнейший принцип правового регулирования рынка труда - принцип свободы трудового договора.
  6. В) Уклонение от участия в политической жизни и от участия в голосовании на выборах.
  7. Вам предложены задания с выбором ответа (в каждом задании только один ответ правильный). Выберите верный ответ (10 баллов).
  8. Вопрос № 44. Выбор метода ценообразования туристского предприятия
  9. Вопрос. Определение выборочной совокупности
  10. Выбор архитектуры и оценка стоимости создания автоматизированной системы управления НСИ
  11. Выбор вентилятора.
  12. Выбор выключателя на резерве собственных нужд

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

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

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

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

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

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

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

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

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

 

 
 

Пример: Сортируемый файл Область вывода

 

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

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

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

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

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)