|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Protopopov Michael 2:5020/400 25 Dec 2002 11:11:20
To : Alexx Ovodov
Subject : Re: быстpая соpтиpовка
--------------------------------------------------------------------------------
> и еще. сyществyет ли метод опpеделения медианы без соpтиpовки массива?
>
Существует метод нахождения медианы (а в принципе и любого k-го по величине)
с частичной сортировкой массива. Основан он на уже описанной здесь быстрой
сортировке Хоара.
Суть в том, что разделив исходный массив на два подмассива мы можем точно
сказать, в каком из них находится медиана и какой по порядку она должна быть
в нем, и дальше работать только с этим подмассивом.
При этом, т.к. второй подмассив уже не нужен, можно обойтись без выделения
лишней памяти для запоминания его парметров или, что фактически тоже самое,
для организации рекурсии.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
