Студопедия

Главная страница Случайная страница

Разделы сайта

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






Обменная сортировка

Сортировки

Сортировка простыми вставками

 

Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных. Пример: игрок в карты при раскладывании карт по мастям вставляет очередную карту в нужное место. Одним из более быстрых алгоритмов этой группы является сортировка с убывающим шагом (метод Шелла), но он здесь не рассматривается, т.к. приводится почти в любой книге по программированию.

В алгоритме идёт речь об упорядочении элементов массива k из n элементов.

 
 

Сортировка посредством выбора

 

Находим наименьший элемент и помещаем его в область вывода. Повторяем эти действия, пока не будут выбраны все элементы. Особенность: до начала сортировки необходимо знать величины всех сортируемых элементов.

 
 

Обменная сортировка

 

Если пара элементов расположена не по порядку, они меняются местами. Процесс повторяется, пока не будут упорядочены все элементы.

Рассматривается хорошо известная сортировка с выбором, называемая также «метод пузырька».

К этой же группе относятся:

· обменная сортировка со слиянием;

· обменная сортировка с разделением, известная как сортировка Хоора или «быстрая сортировка»;

· поразрядная обменная сортировка.

 
 

 

4 Сортировка подсчётом

 

Элемент сравнивается со всеми остальными. Его окончательное положение определяется подсчётом числа меньших ключей целыми словами,

j-ый ключ в сортированной последовательности больше или равен (j-1) ключа.

Алгоритм требует работы со вспомогательным массивом размера n, где будут помещены счётчики. Положение j-го элемента определяется как (с4j+1 ).

Это сортировка именно ключей – сами элементы ki остаются на своих местах. Удобно для работы с записями большой длины.

 
 

<== предыдущая лекция | следующая лекция ==>
 | 




© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.