Re: сортировка почти отсортированных данных

From

Vladimir A. Pertzel ()

To

Max Alekseyev

Date

2002-07-17T11:27:44Z

Area

RU.ALGORITHMS

From: "Vladimir A. Pertzel" <voldemar@relhum.org>

Мир Вашему Дому!

"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)