Вторник, 19.03.2024, 09:07
Приветствую Вас, Гость |
Меню сайта
Наш опрос
Нужен ли форум на этом сайте?
Всего ответов: 1296
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

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

      В данной статье будет описан алгоритм карманной сортировки, а так же приведён пример реализации алгоритма на паскале. Карманную сортировку так же называют блочной или корзинной.
       Карманная сортировка  — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно карманной сортировкой, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

       Алгоритм карманной сортировки требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.

Первый этап карманной сортировки: распределение по карманам


Второй этап карманной сортировки: сортировка карманов и восстановление массива.

Преимущества:
          Алгоритм карманной сортировки относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

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

Пример карманной сортировки на паскале (pascal)
Форма входа
Поиск
Мы в сети
Реклама
Для того чтобы не видеть рекламу в правом верхнем углу сайта пройдите простую процедуру регистрации
ФОРУМ
У нас наконецто появился форум! Добро пожаловать! Будьте первыми, задайте направление форуму! =)
--- Не стесняемся - заходим на форум! ---