|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir A. Pertzel 2:5020/400 17 Jul 2002 11:27:44
To : Max Alekseyev
Subject : Re: сортировка почти отсортированных данных
--------------------------------------------------------------------------------
Мир Вашему Дому!
"Max Alekseyev" > news:1026764972@f60.n5015.z2.ftn ...
> Предположим, что массив данных размерности n является почти
отсортированным
> (чтобы формализовать это понятие, скажем, достаточно не более
log(n)
> элементарных операций для получения из него отсортированного
массива). Какие
> есть алгоритмы для быстрой сортировки таких массивов? Хотелось
бы линейного
> времени, а лучше саб-линейного.
Требуемое время не менее линейного, поскольку если мы
не узнавали значения некоторого элемента, то в ситуации,
когда он стоит не на своем месте, задача окажется
нерешенной.
Однако, прежде всего, хотелось бы понять, минимальным должно
быть "среднее" время сортировки или гарантированный результат?
Вот решение с двунаправленными сортированными списками:
Создаем список списков и инициируем его исходным.
Исходный список объявляем текущим списком.
Его элемент, что находится с того конца, где предполагаются
минимальные элементы, объявляем текущим элементом списка.
Двигаемся в сторону предполагаемого возрастания. Цикл: {
Как только следующий элемент Y оказывается меньше
предыдущего Z, разрываем текущий список по связке
между ними, и хвост объявляем началом нового текущего
(заметим, что хотя бы один из элементов Y и Z стоит
не на своем месте, поэтому списков не более 2*log(n))
}
Создаем из минимальных элементов списков priority queue,
в качестве приоритета используя убывание. Цикл по ней: {
Извлекаем из priority queue список, объявляем его
текущим. Список, оказавшийся в начале очереди объявляем
списком-кандидатом, а минимальный элемент списка-кандидата
объявляем элементом-кандидатом. Цикл по текущему списку,
двигаемся в сторону возрастания: {
Если текущий элемент меньше элемента-кандидата,
вставляем его в итоговый список,
(всего эта операция будет выполнена ровно n раз)
иначе
возвращаем текуший список в priority queue и выходим
из цикла по текущему списку. (поскольку либо
элемент-кандидат,
либо текущий элемент стояли не на своем месте, всего эта
операция будет выполнена не более (2*log(n) раз)
}
}
--
/\ /\ С почти африканским приветом,
((ovo)) Владимир Анатольевич Перцель
():::() http://voldemar.relhum.org
--PVA---------------------------------------
Блаженны умеющие смеяться над собой, ибо не
иссякнет источник их услады до конца дней их.
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: сортировка почти отсортированных данных