Нужен оптимальный алгоритм решения

[barss]

Здравствуйте.
задача такова.

есть множество обьектов скажем например штук 1000
есть некая функция которая присваивает 10-ти обьектам ранг от 1 до 10.

Нужно раставить обьекты в множестве по мере спада ранга.

решение есть:
1.берем первые 10, определяем какой из них с самым меньшим рангом
2. на его место ставим 11 элемент и опять определяем обьект с самым меньшим рангом..
3. повторяем пункт 2 пока не дойдем до конца
так мы определим обьект с самым большим рангом.. откидываем его, а с оставшимися обьектами проводим все по пунктам 1,2,3..
Те элементы что откидывали образуют отсортированное множество.
При таком алгоритме количество обращений к функции определения ранга ~1милион

Подскажите пожалуйста алгоритм при котором число обращений к функции определения ранга было минимальным.

[venco]

Например, так:
1. Выбираем 1 случайный элемент. Сравниваем с ним по 9 остальных элементов и делим их на те, что меньше референсного, и те, что больше.
2. Рекурсивно сортируем получившиеся 2 под-массива.

Для улучшения можно взять несколько (2...9) референсных элементов, предварительно их отсортировав.
Самостоятельно проанализируйте, какое количество референсных элементов оптимально.

-- Ср июн 02, 2010 13:58:24 --

barss в сообщении #326877 писал(а):

решение есть:
1.берем первые 10, определяем какой из них с самым меньшим рангом
2. на его место ставим 11 элемент и опять определяем обьект с самым меньшим рангом.

Кстати, даже Ваш вариант легко ускорить в 9 раз, если на каждой итерации сравнивать текущий минимальный с 9-ю новыми.
А можно ускорить и в 25 раз, если за один проход искать сразу 5 минимальных элементов.
Но это всё равно будет квадратичный алгоритм, а то, что предложил я - $O(N\log N)$, причём с константой сильно меньше единицы, т.е. быстрее, чем quicksort.

[barss]

огромное спасибо Вам!