Developing.ru

Написать программу упорядочивания массива из 10 элементов методом быстрой сортировки, используя рекурсию.

Пример ввода:
12 45 78 91 21 43 11 12 1 8

Пример вывода:
1 8 11 12 12 21 43 45 78 91

P.S. Идея алгоритма состоит в следующем. Применим к массиву так называемую процедуру разделения относительно среднего элемента. Вообще-то, в качестве «среднего» можно выбрать любой элемент массива, но для наглядности мы будем выбирать действительно, по возможности, средний по своему номеру элемент. Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие, чем элемент, выбранный в качестве среднего, а в правой — большие. Это достигается путем просмотра массива попеременно с обоих концов, при этом каждый элемент сравнивается с выбранным средним, и элементы, находящиеся в «неподходящей» части, меняются местами. После завершения процедуры разделения средний элемент оказывается на своем окончательном месте, т. е. его «судьба» определена и мы можем про него забыть. Далее процедуру разделения необходимо повторить отдельно для левой и правой части: в каждой части выбирается среднее, относительно которого она делится на две, и так далее. Понятно, что одновременно процедура не может заниматься и левой, и правой частями, поэтому необходимо каким-то образом запомнить запрос на обработку одной из двух частей (например, правой), и заняться оставшейся частью (например, левой). Так продолжается до тех пор, пока не окажется, что очередная обрабатываемая часть содержит ровно один элемент. Тогда нужно вернуться к последнему из необработанных запросов, применить к нему все ту же процедуру разделения и так далее... В конце концов массив окажется полностью упорядочен.

Когда-то работало, но коду хз сколько времени, могут возникнуть какие нить траблы)

Код: Выделить всё

template <class T>
inline void swap(T array[], int pos1, int pos2)
{
	T temp = array[pos1];
	array[pos1] = array[pos2];
	array[pos2] = temp;

};

template <class T>
inline int partiton(T array[], int start, int end, int pe_index)
{
	T pe = array[pe_index];
	swap(array, pe_index, end);
	int head = start, tail = end - 1;

	while(true)
	{
		while(array[head] < pe) ++head;
		//assert(array[head] >= pe);

		while((array[tail] > pe) && (tail > start)) --tail;
		//assert(array[tail] <= pe);

		if(head >= tail) break;
		swap(array, head++, tail--);
	};
	swap(array, head, end);
	assert(array[head] == pe);

    return head;
};

template <class T>
inline int get_pe(T array[], int lower, int upper)
{
	int mid = (upper + lower) / 2;
	if(array[lower] <= array[mid])
	{
		if(array[mid] <= array[upper]) return mid;
		else if (array[upper] <= array[lower]) return lower;
			 else return upper;		
	}
	else
	{
		if(array[lower] <= array[upper]) return lower;
		else if (array[upper] <= array[mid]) return mid;
			 else return upper;
	}
	//return lower;
};

template <class T>
inline void qsort_base(T array, int head, int tail)
{
	int diff = tail - head;

	if(diff < 1) return;

	if(diff == 2)
	{
		if(array[head] > array[tail]) swap(array, head, tail);
		return;
	}
	
	int pe_index = get_pe(array, head, tail);
	
	int mid = partiton(array, head, tail, pe_index);
	assert((mid >= head) && (mid <= tail));

	qsort_base(array, head, mid-1);
	qsort_base(array, mid+1, tail);
	
};

template <class T>
inline void qsort(T array, int size)
{
	int head = 0, tail = size - 1;
	qsort_base(array, head, tail);
};

Developing.ru

Рекурсия...помогите...плиз... (С++)

Re: Рекурсия...помогите...плиз... (С++)

Re: Рекурсия...помогите...плиз... (С++)