Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод сортировки выбором
|
|
Исходный массив длиной N разбивается на две части: итог и остаток. Участок массива, называемый итогом, располагается с начала массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит исходные числа не отсортированной части исходного массива.
Текстуальный алгоритм сортировки выбором.
Шаг 1. Полагается i =0, т.е. считается, что итоговый участок – пуст.
Шаг 2. В остатке массива ищется минимальный элемент и он меняется местом с первым элементом остатка (i -ым элементом массива). После чего значение i увеличивается на единицу, тем самым расширяя итоговый участок массива (отсортированную часть исходного массива).
Шаг 3. Если i < N, то повторяется Шаг 2. В противном случае – конец алгоритма, т.к. итог становится равным всему массиву.
Конец алгоритма.
Схема алгоритма методом сортировки выбора представлена на рис. 1.
Рисунок 1 – Схема алгоритма сортировки методом выбора
Метод сортировки включением
Этот метод похож на метод пузырька. Происходит такое же разбиение массива на отсортированную и не отсортированную части, но перемещение первого элемента остатка на принадлежащее ему место в итоге делается не сравнением двух соседних элементов, а с помощью метода двоичного поиска, который удобно оформить в виде отдельной процедуры.
Текстуальный алгоритм методом включением.
Шаг 1. Пусть i =1, т.е. итоговый участок состоит из одного элемента.
Шаг 2. Берется первый элемент остатка и перемещается в отсортированную часть массива так, чтобы итоговый участок остался упорядоченным.
Шаг 3. После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной i, тем самым увеличивая отсортированную часть массива. Если i < N, то управление передается на Шаг 2, в противном случае - работа алгоритма завершена.
Конец алгоритма.
Схема алгоритма метода сортировки включением представлена на рис. 3.
Рисунок 3 – Блок-схема алгоритма сортировки прямым включением
|
|