Re: быстpая соpтиpовка

From

Protopopov Michael ()

To

Alexx Ovodov

Date

2002-12-25T10:11:20Z

Area

RU.ALGORITHMS

From: "Protopopov Michael" <mkp@ist.ru>

> и еще. сyществyет ли метод опpеделения медианы без соpтиpовки массива?
>
Существует метод нахождения медианы (а в принципе и любого k-го по величине)
с частичной сортировкой массива. Основан он на уже описанной здесь быстрой
сортировке Хоара.
Суть в том, что разделив исходный массив на два подмассива мы можем точно
сказать, в каком из них находится медиана и какой по порядку она должна быть
в нем, и дальше работать только с этим подмассивом.
При этом, т.к. второй подмассив уже не нужен, можно обойтись без выделения
лишней памяти для запоминания его парметров или, что фактически тоже самое,
для организации рекурсии.



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)