Можно ли так

RZ_RZ, сортировка в общем случае это N*log(N) у тебя же алгоритм N^2. Т.е. сортировку использовать предпочтительнее.
Автору топика нужен алгоритм оптимальнее N*log(N). Я предполагаю, что это будет сложность N.

Спасибо за простоту!
P.S. Хотя наверное есть более эффективные аналоги...

[QUOTE=Green]RZ_RZ, сортировка в общем случае это N*log(N) у тебя же алгоритм N^2. Т.е. сортировку использовать предпочтительнее.
Автору топика нужен алгоритм оптимальнее N*log(N). Я предполагаю, что это будет сложность N.[/QUOTE]
Сортировка эффективнее конечно. Но у меня исходный массив должен остаться неизменным, т.е. чтобы его отсортировать, нужно сначала создать что-то вроде vector, записать в него содержимое double * (попутно вопрос-это вообще возможно одной операцией), а затем отсортировать vector. Т.е. операций порядочно.
А пользоваться CRT и qsort еще более неэффективнее...
Хотя можно конечно у Кнута посмотреть более эффективную процедуру.

Создаем еще 2 масива

1 проход - находим среденее арифметическое исходного масива
2 проход - раскидываем элементы(или индексы) по созданым двум масивам - в один большие среднего, в другой - меншие, и заодно подсчитываем длины наших масивов. Теперь по разности длин масивов можно будет определить индекс медианы.

Может то, что я написал, даже будет давать правильные результаты :)

[QUOTE=Alexandoros]Создаем еще 2 масива

1 проход - находим среденее арифметическое исходного масива
2 проход - раскидываем элементы(или индексы) по созданым двум масивам - в один большие среднего, в другой - меншие, и заодно подсчитываем длины наших масивов. Теперь по разности длин масивов можно будет определить индекс медианы.

Может то, что я написал, даже будет давать правильные результаты :)[/QUOTE]
К сожалению, этот алгоритм не рабочий. :)
Для поиска медианы среднее арифметическое вообще не имеет смысла.
Пример:
6, 7, 8, 5, 104
среднее арифметическое = 26
разность длин массивов = 4 - 1 = 3
ничего нам не дает, т.к. медиана равна 7 (второму элементу).

[QUOTE=michael_is_98]Сортировка эффективнее конечно. Но у меня исходный массив должен остаться неизменным,
[/QUOTE]
Должен остаться неизменным - сделай копию.

[QUOTE=michael_is_98] т.е. чтобы его отсортировать, нужно сначала создать что-то вроде vector, записать в него содержимое double * (попутно вопрос-это вообще возможно одной операцией),
[/QUOTE]
Можно
vector<double> v(p, p+size);
где p - указатель на первый элемент массива,
size - размер массива.
[QUOTE=michael_is_98]а затем отсортировать vector. Т.е. операций порядочно.
А пользоваться CRT и qsort еще более неэффективнее...
[/QUOTE]
Что значит операций порядочно?
Что значит использовать qsort неэффективно?
Как я уже сказал в общем случае количество операций будет пропорционально N*log(N) (это для qsort), а не N^2, как в приведенном выше примере. Т.е. уже эффективнее.

[QUOTE=michael_is_98]Хотя можно конечно у Кнута посмотреть более эффективную процедуру.[/QUOTE]
Более эффективную, чем быстрая сортировка не найдешь.
Но есть один момент, который позволяет съоптимизировать быструю сортировку и привести сложность от N*log(N) к 2N.
Это достигается тем, что в рекурсии не нужно сортировать обе партиции, а лишь одну.

P.S. Кстати, для этого не надо читать три тома Кнута, а можно прочесть книгу всего 250 страниц - "Жемчужины программирования", Бентли.

Понятно, если у тебя есть эта книга в эл. виде - отправь ее мне.
А насчет qsort я хотел сказать, что STL vector более эффективен, чем в qsort CRT. Хотя алгоритм может быть один и тот же. Или я не прав?

[QUOTE=michael_is_98]Понятно, если у тебя есть эта книга в эл. виде - отправь ее мне.
[/QUOTE]
К сожалению, нет. :(
[QUOTE=michael_is_98]
А насчет qsort я хотел сказать, что STL vector более эффективен, чем в qsort CRT. Хотя алгоритм может быть один и тот же. Или я не прав?[/QUOTE]
vector - это контейнер, а qsort - это функция (реализация алгоритма), поэтому их сравнивать никак нельзя. Это все равно что сравнивать объем и скорость.
Сравнить можно qsort и std::sort. Действительно, std::sort несколько быстрее в общем случае, хотя обе функции имеют общий принцим (алгоритм Хоара).

Общий принцип такой (http://algolist.manual.ru/sort/mqs/fast_strings2.php):
1) берем любое число из массива;
2) числа меньше выбранного помещаем в одну партицию, а больше либо равно в другую;
3) повторяем рекурсивно с п.1 для получившихся партиций.
Алгоритм можно по-разному оптимизировать, но базовый принцип тот же.

Для твоей задачи можно отбрасывать сортировку ненужных партиций.
Известно, что после сортировки медиана будет иметь интекс n/2, где n - размер массива.
Т.о. выполняя быструю сортировку можно сразу отбрасывать (точнее, дальше не обрабатывать) ту партицию, которая не не содержит индекс n/2.

Например:
3, 6, 7, 8, 5, 11, 104
размер массива 7, n/2 = 3.

1) выбираем случайно (настоящий алгоритм выбора - это одна из оптимизаций) к примеру число 8;
2) определяем партиции (a<8 | a>=8):
3, 6, 7, 5 | 8, 11, 104
3) первая партиция теперь занимает у нас ячейки массива от 0 до 3, т.к. медиана будет в ячейке n/2 = 3, то оставляем эту партицию, вторую отбрасываем.
3, 6, 7, 5, х, х, х

4) повторяем с п.1, выбираем к примеру 6;
5) формируем партиции (a<6 | a>=6):
3, 5 | 6, 7, х, х, х
6) теперь третий элемент принадлежит второй партиции поэтому первую отбрасываем
х, х, 6, 7, x, x, x

7) производим сортировку в последней оставшейся партиции (у нас и так получилось отсортировано)
и берем значение по третему индексу, т.е. 7
это и есть наша медиана.

именно это и хотел сказать. чем объяснить разницу в скорости между qsort и std::sort?

std::sort имеет ряд оптимизаций, хотя все зависит от конкретной реализации STL.
Более конкретно надо искать в интернете.

[QUOTE=Green]std::sort имеет ряд оптимизаций, хотя все зависит от конкретной реализации STL.
Более конкретно надо искать в интернете.[/QUOTE]
Ну в общем я так понял, что для этой задачи все-таки лучше сначала отсортировать массив.