Russian Qt Forum

Добрый день

Есть std ф-ция nth_element, напомню что она делает: упорядочивает массив/контейнер так чтобы все элементы меньше заданного значения стояли слева, в все больше - справа. Размеры левой и правой частей будут "как получится", внутри частей элементы не упорядочены.

Нужно: почти то же самое но так чтобы части были равны, пример
{ 9, 5, 7, 1, 3 }  // исходный
{ 3, 1, 5, 9, 7 }  // 5 точно посередине, слева все <= 5 справа все >= 5

Результат легко достигается сортировкой, но это заметно тормозит. "Ф-ции не нашел" в написать сам затрудняюсь. Что предложите?

Спасибо

 

Если я тебя понял, то тебе нужна функция которая делит массив пополам, и центральное число массива делит на массив так, что слева меньше, а справа больше?
Тогда сперва надо найти это число, переместить в центр, а затем на одном проходе массива переместить меньшие значения влево, а большие в право. Если можно создавать новый массив, то алгоритм получится банальный, если нельзя то получится мудреная тасовка. А вот как найти центральное число что-то в голову не приходит щас.

Да, именно так

Ясно что если бы "5" было заранее известно - просто вызвал бы nth_element, или сам бы написал без проблем, там ничего мудреного. Так его ж нет

Нагуглил как называется эта задача "Нахождение к-того минимального элемента". Можешь нагуглить нужное по запросу "Selecting k smallest", либо взять готовое из библиотеки GSL: http://www.gnu.org/software/gsl/ (http://www.gnu.org/software/gsl/)
Одна из этих функций подойдет для тебя: http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html (http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html)

Не то

Это прямая вставка в выходной массив который поддерживается сортированным

Но все равно - спасибо за хлопоты

Вот еще один алгоритм: http://pine.cs.yale.edu/pinewiki/QuickSelect (http://pine.cs.yale.edu/pinewiki/QuickSelect). Именно то что нужно, но он требует для своей работы два рабочих массива. Хотя если у тебя массивы не слишком большие и ты можешь держать в памяти два рабочих массива постоянно то думаю этот алгоритм подойдет.
Ну и статья в википедии: http://en.wikipedia.org/wiki/Selection_algorithm (http://en.wikipedia.org/wiki/Selection_algorithm)
Вот тут еще можешь поискать: http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on (http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on)

По моему имеет смысл поглядеть в исходники qsort.
Единственное что не нужно делать - рекурсивно сортировать подмассивы.

Наверное qSort или QuickSort (но не qsort из stdlib). Там ничего нового - просто nth_element, размеры подмассивов как получится

Тогда не совсем понятна постановка задачи.

Что значит:


Что должно получится на выходе, когда на вход попадает массив с четной длинной?

И почему не подходит

Подходит ли для тебя изменение массива переданного в функцию?
Меня задача заинтересовала, но решать не хочется пока не появятся критерии решения. А именно тестового проекта с текущим решением с замерами скорости работы и задачи во сколько надо ускорить работу.

Неоднократно замечал как сразу постановка становится "плохой" если задача не решается сразу, т.е. дело не сводится к простой эксплуатации знаний :) Ведь неск раз уже было сказано - nth делит на подмассивы размеры которых "как получится", а мне нужно "заданного". Так чего упираться и месить по-пустому?  :)


Не только подходит, но и является целью

Ну с временными массивами явное фуфло. Их там нужно не один а рекурсивно, и потом хз как их склеивать. А так у меня и сделано как пишут (передрал из книги Дженсена).

C++ (Qt)
void median_split(
	double * data,		// data array				
	int start,         	// start index in array
	int end,           	// end index in array
	int median ) 	// desired median index
{
	int left = start;
	int right = end;
 
	while (right > left) {
		double v = data[right];
		int i = left - 1;
		int j = right;
		for (;;) {
			while (data[++i] < v)
			;
			while (data[--j] > v && j > left)
			;
			if (i >= j) break;
			std::swap(data[i], data[j]);
		}
 
		std::swap(data[i], data[right]);
		if (i >= median)
			right = i - 1;
		if (i <= median)
			left = i + 1;
	}
}
 

И все бы ничего, но в какие-то моменты наступает жуткий тормоз, вот надо разобраться почему

Общая задача - построение дерева без доп данных (ну почти), ноды находятся по индексу

Ну да, конечно. Все должны уметь читать твои мысли. :)

По поводу


может стоит обратить внимание на второй аргумент этой функции?

И кстати, твой median_split(double * data,      // data array            
   int start,            // start index in array
   int end,              // end index in array
   int median
)

отлично переписывается при помощи nth_element вот таким образом

Скинь массив на котором тормоза происходят.

Не транспортабельный (порядка 2 Gb). Изучал в отладчике, вроде получается что тормоз настает когда массив сортирован (ну или почти)

Да! nth_element и делит как мне надо, "по индексу" (а не "по значению"), и это действие не равно тому что делает qSort. Перемудрил  :)

Спасибо Anchorite, V1KT0P