Какие существуют алгоритмы нахождения медианы одномерного массива без использования сортировки?

Question

[SurelL]

Допустим, у нас есть одномерный массив. Какие есть алгоритмы нахождения его медианы без использования сортировки (например, пузырьком)?

Comments

[jcmvbkbc]

Ivan Sokolov: садись, два.
Пример: 1, 1, 1, 1, 1000000.

[AtomKrieg]

Ответ легко ищется поисковиком.

[jcmvbkbc]

Ivan Sokolov: попробуй получить этот ответ своим алгоритмом.

[jcmvbkbc]

Ivan Sokolov: молодец. Исправь мой пример так, чтобы твоим алгоритмом получилось 2.

Answer 1

[Андрей]

Мне кажется на codeforces адекватные ответы на этот вопрос (первая ссылка в Яндексе)

Answer 2

[uvelichitel]

Делать quicksort, но на рекурсивном шаге сортировать не оба полученных крыла, а только то которое ближе к медиане. Например если первый тур quicksort разбил массив на части 50 и 70 элементов то на втором туре сортировать только часть из 70. Пусть получили 30 и 40, тогда медиана в части 30 - ее и сортировать. Так до победы.

Answer 3

[Lertmind]

Вопрос уже был на тостере Как найти медиану одномерного массива, пригодится.