Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм сортировки прямым выбором
1. Обнуляем индекс i. 2. Среди элементов a [ i ], a [ i + 1],…, a [ N – 1] находим минимальный элемент и запоминаем его индекс k. 3. Меняем местами элементы a [ i ] и a [ k ], увеличиваем i на единицу. 4. Если i < N – 1 идем на шаг 2.
Приведем пример. Заметим, что часть массива, в которой на очередном шаге ищется минимальный элемент, выделена синим цветом, найденный минимальный элемент – красным..
Сортировка методом прямого выбора не является устойчивой. Покажем это на примере, где два одинаковых элемента выделены разными цветами.
Блок-схема этой сортировки выглядит следующим образом:
Подсчитаем теперь число сравнений для алгоритма прямого выбора. На первой итерации минимум ищется во всем массиве, то есть требуется N сравнений элементов массива с текущим минимумом (в блок-схеме – min), на второй итерации – (N –1) сравнение, и т. д. На последней итерации требуется одно сравнение. Значит, общее число сравнений есть . Кроме того, если элемент массива оказывается меньше, чем минимум, то переменной min присваивается новое значение. В худшем случае таких присвоений будет также . В конце каждой итерации происходит обмен значений элементов, значит, общее число таких обменов равно числу итераций N. В целом трудоемкость имеет порядок .
Сортировка прямой вставкой
Сортировка с помощью прямой вставки относится ко второй категории – сортировки с помощью включения. Суть этого метода в следующем: элементы массива просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Другими словами, массив “делится” на две части: упорядоченную (левую) и неупорядоченную (правую). Крайний левый элемент из правой неупорядоченной части вставляется в упорядоченную таким образом, чтобы порядок не нарушился, тем самым, увеличивая упорядоченную левую часть массива и уменьшая правую неупорядоченную. Кроме того, следует иметь в виду, что массив из одного элемента упорядочен. Приведем алгоритм сортировки.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-08; просмотров: 553; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.58.197.26 (0.006 с.) |