Помогите пожалуйста!!! Завтра отчитываться по этой сортировке, а сижу уже 4 час и никак не пойму как она работает!!! Взята из книги сортировок и никакого описания! Может кто поможет разобраться как она работает?? Выкладываю полную программу под Borland C 31

Цитата

void sort (int *arr, int st, int en, int med) //Сортировка { int *p1, *p2; p1=new int [med-st+1]; p2=new int [en-med]; int j, k1=0, k2=0; for(j=st;j<en+1;j++) {   if(j<med+1)   p1[k1++]=arr[j];   if(j>med)   p2[k2++]=arr[j]; } for(j=st, k1=0, k2=0;j<en+1;) {   if(k1==med+1-st)              arr[j++]=p2[k2++];   else if(k2==en-med)            arr[j++]=p1[k1++];   else if(p1[k1]<p2[k2])        arr[j++]=p1[k1++];   else if(p1[k1]>=p2[k2])        arr[j++]=p2[k2++]; } delete p1; delete p2; } void div(int *arr,int st, int en)  //Рекурсивно запускает функцию sort     с требуемыми параметрами { if(en>st) {   div(arr,st,st+(en-st)/2);   div(arr,st+(en-st)/2+1,en);   sort(arr,st,en,st+(en-st)/2); } else  return; }

Названия функциям явно давал какой-то умник - видимо, с целью запутать студентов.
Вот базовый код сортировки слиянием из Седжвика:

Код

void mergesort(int* a, int l, int r) {     int m = (r+l)/2;     if (r <= l) return;     mergesort(a,l,m);     mergesort(a,m+1,r);     merge(a,l,m,r); }

Здесь функция merge делает именно то, что в вашем примере называется sort.
A mergesort - это, соответственно, ваша div. Тогда все становится на свои места.
Сортировка выполняется путем деления массива a на 2 части, с их последующей сортировкой (рекурсивно) по отдельности, а потом - слиянием этих массивов.
Подробнее нужно?

А это разве не обычное слияние... И вообще в чем разница между обычным и циклическим! Мне просто сегодня ее дали, а до этого я с такими сортировками и не встречался... И если можно поподробнее о процессе ее работы

Заранее благодарен

Да, в общем, обычное. Честно говоря, термин "циклическое" я не знаю как понимать. Но судя по приведенному коду - обычная сортировка слиянием.

Как она работает.
Ну, функция merge, которая у вас называется sort, просто сливает две половины исходного массива.
В первом цикле исходный массив перекладывается в два вспомогательных под-массива. Кстати сказать, написано достаточно криво: какой смысл все время проверять, не стал ли индекс больше чем med. Логичнее уж написать 2 цикла - первая половина копируется в первый массив, вторая - во второй. Но это так, ворчание в скобках.

Во втором цикле, эти два подмассива просматриваются параллельно, выбирается наименьший элемент и инкрементируется соответствующий индекс. Когда элементы в одном из массивов кончаются, все остальное берем их второго.

Суть метода в том, что эти подмассивы ОТСОРТИРОВАНЫ. Именно поэтому в результате тоже получается отсортированный массив.

А отсортированы подмассивы потому, что перед этим функция сортировки вызывается рекурсивно для каждого из них.

Из всех книг, где описаны сортировки и алгоритмы вообще, мне больше всего нравится "Фундаментальные алгоритмы на С++" Р. Седжвика. Сортировкам посвящена часть 3. По-моему здесь, в разделе Литература есть ссылка на эту книгу в сети.

Это сообщение отредактировал(а) Earnest - 23.6.2005, 19:05

Спасибо большое