Сортировка кубическим выбором

Сортировка квадратичным выбором.

Сортировка подсчетом.

Карманная сортировка.

Сортировка распределением.

Метод Шелла (сортировка с убывающим шагом).

Методы сортировки.

Методы программирования.

Преподаватель: Ефимов Сергей Сергеевич.

18.02.10 г.

Автоматы(!) возможны.

· «Отлично» – 90% - 100% (A)

· «Хорошо» – 75%-90% (B, C)

· «Удовлетворительно» – 60% - 75% (D, E)

· «Неудовлетворительно» - <60% (F)

Количество элементов в массиве - степень числа 2. Элементы группируются с шагом d_i: d₁=8, d₂=4, d₃=2, d₄=1. Трудоемкость пропорциональна O(N^3/2). Шаг может быть и другим. Последовательность Седжвика – d_i = 9*2ⁱ – 9*2^i/2 +1; d_i = 8*2ⁱ – 6*2^(i+1)/2+1. Последовательность до 4000 символов, самая эффективная – Марцина Циура.

ü Начиная со старших разрядов.

Основная операция – пересылки. Берем элемент и переносим его в необходимую область. Количество пересылок – N*R, где N – число элементов, R – число разрядов; это и есть трудоемкость алгоритма.

ü Начиная с младших разрядов.

Число этапов равно R. первый этап – распределение на 10 групп по младшему, по крайнему правому. Проходим по массиву целиком, выполняя сортировку по второму справа разряду, и т.д. По трудоемкости – такой же, но программная реализация проще.

ü С двумя массивами.

Область использования – выполняется для ключей, которые располагаются в данной области по порядку. Карманов столько, какого разница между наибольшим и наименьшим значением. Берем значения и раскладываем в нужные «карманы». Зависимость линейная – 1000 элементов – 1000 перемещений. Недостаток – необходимо большое количество памяти.

ü В исходном массиве.

Отыскивается ключ с минимальным и максимальным номером. Берется первый элемент и проверяется, на своем ли он месте.

ü Подсчет сравнений.

ü Подсчет распределений.

Создается массив-счетчик, в котором изначально значения сбрасываются либо в 0, либо в 1 количество совпадений. Если исходное число больше, чем сравниваемое, то в счетчик прибавляется 1, если сравниваемое, то в его счетчик +1. Далее сортируется по отсортированному.

Предположим, что число элементов является квадратом количества элементов. 16 à 4 элемента. В каждой группе отыскивается максимальный элемент. Выбираются элементы и тоже находятся максимальные. Помещается в конец итогового массива. На следующем этапе отыскивается максимальный элемент. Группа становится короче. В общем виде из √N. метод сортировки работает быстрее. Трудоемкость пропорциональна o(N√N). чем больше N, тем ощутимее разница в трудоемкости.

Берется число и извлекается куб. далее схема идентична сортировке квадратичным выбором. Формируются группы из трех элементов. Из последней группы из трех элементов находится максимальный. Трудоемкость о(N√³N).

Дата добавления: 2014-01-05