![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка выбором
Основная идея метода состоит в том, чтобы идти по шагам j=1, 2,..., N-1, находя на j -м шаге среди неотсортированных записей запись с наименьшим ключом, и каким-либо образом помещать ее на соответствующее место. К методам сортировки посредством выбора относятся следующие: простой линейный выбор, квадратичный выбор, линейный выбор с обменом, турнир с выбыванием, пирамидальная сортировка и др., различающиеся способами выбора очередности сравнений и обмена.
а) простой линейный выбор (монеты, структурограмма, пример) б) линейный выбор с обменом Простой линейный выбор (монеты, структурограмма, пример)
5, 4, 1, 2, 3 J=1, I=2; 4 5 1 2 3 I=3; 1 5 4 2 3 I=4; 1 5 4 2 3 I=5; 1 5 4 2 3
J=2, I=3; 1 4 5 2 3 I=4; 1 2 5 4 3 I=5; 1 2 5 4 3
J=3, I=4; 1 2 4 5 3 I=5; 1 2 3 5 4
J=4, I=5; 1, 2, 3, 4, 5 Метод медленный т.к. очень много обменов. Число сравнений = N*(N-1)/2 Число обменов Минимальное =0 Максимальное = 2*N
|