Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Сортировка циклическим слиянием

Автор: MegBegb 23.6.2005, 17:57

Помогите пожалуйста!!! Завтра отчитываться по этой сортировке, а сижу уже 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;
}

Автор: Earnest 23.6.2005, 18:31

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

Код


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 части, с их последующей сортировкой (рекурсивно) по отдельности, а потом - слиянием этих массивов.
Подробнее нужно?

Автор: MegBegb 23.6.2005, 18:37

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

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

Автор: Earnest 23.6.2005, 19:00

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

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

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

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

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

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

Автор: MegBegb 23.6.2005, 19:59

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