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

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

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

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

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

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

Автор: yaja 23.6.2005, 21:26

Честно говоря я не понял, почему это сортировка циклическим слиянием, код похож на обычную сортировку слиянием... Интересно что за книга такая?? smile

Работает следующим образом: Если у нас есть два отсортированных куска массива, то мы можем их легко слить в один сортированный кусок. Делается это в твоей функции sliv (согласно RGR.cpp) спомощью двух дополнительных массивов, куда заранее копируются соот. куски общего массива, а затем устанавливаем указатели на начала соот. массивов и сравниваем элементы. Пусть в первом, элемент меньше, тогда мы его копируем на нужное место в большом массиве и увеличиваем счетчик на одни, аналогично в противном случае.
В функции div мы просто для каждого куска запускаем рекурсивно функцию, для двух кусков, которые потом сливаем.
Добавлено @ 21:31
что-то я облажался. написал не туды smile

Искренне извиняюсь... smile