Написать программу упорядочивания массива из 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);
};