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

From

Nagval ()

To

Max Alekseyev

Date

2002-07-16T10:41:48Z

Area

RU.ALGORITHMS

From: "Nagval" <shura@nrcc.ru>

> Предположим, что массив данных размерности n является почти
отсортированным
> (чтобы формализовать это понятие, скажем, достаточно не более log(n)
> элементарных операций для получения из него отсортированного массива).
Какие
> есть алгоритмы для быстрой сортировки таких массивов? Хотелось бы
линейного
> времени, а лучше саб-линейного.
Почитай Кнута: адаптивные методы сортировки.


--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)