Реализация слияния в переполнении стека

#include <iostream>

using namespace std;

void merge(int*,int*,int,int,int);
void mergesort(int *a, int*b, int low, int high)
{
int pivot;
if(low<high)
{
pivot=(low+high)/2;
mergesort(a,b,low,pivot);
mergesort(a,b,pivot+1,high);
merge(a,b,low,pivot,high);
}
}
void merge(int *a, int *b, int low, int pivot, int high)
{
int h,i,j,k;
h=low;
i=low;
j=pivot+1;

while((h<=pivot)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
**if(h>pivot)
{
for(k=j; k<=high; k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h; k<=pivot; k++)
{
b[i]=a[k];
i++;
}
}**
for(k=low; k<=high; k++) a[k]=b[k];
}

int main()
{
int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24};
int num;

num = sizeof(a)/sizeof(int);

int b[num];

mergesort(a,b,0,num-1);

for(int i=0; i<num; i++)
cout<<a[i]<<" ";
cout<<endl;
}

Я не могу понять одну вещь в этом коде. Это было дано в моей книге.
Я проследил этот код относительно того, что произойдет, если я возьму 8 несортированных номеров.

Зачем мы это делаем? (Часть с двумя звездами в начале и конце)

if ( h > pivot )
{
......
}
else
{
......
}

Цикл while над ним сам поместит только отсортированные элементы (и все они) в массив b. И, наконец, мы можем, наконец, поместить его в массив a (по последнему циклу for).
Я попытался запустить код без отмеченной части, и он, очевидно, показывает неправильный ответ, но я не могу понять, почему это происходит?

Спасибо!

1

Решение

Эта часть кода объединит оставшиеся элементы. Например, если у вас есть {3,4} и {1,2,6,7}
слить затем часть выше этого if(h>pivot) условие дает {1,2,3,4}.

Поэтому для копирования остальных элементов мы используем эти условия.

1

Другие решения

Это когда вы объединяете массивы, и вы достигли конца одного массива, это для копирования других элементов другого массива, и наоборот.

1

Эта часть предназначена для хранения оставшихся элементов.
Например, если бы мы имели

A: 1, 3, 5, 4, 6, 7
B: empty
compare 1, 4
A: *1, 3, 5, 4, 6, 7
B: 1
compare 3,4
A: *1, *3, 5, 4, 6, 7
B: 1, 3
compare 5, 4
A: *1, *3, 5, *4, 6, 7
B: 1, 3, 4
compare 5, 6
A: *1, *3, *5, *4, 6, 7
B: 1,3,4,5

теперь цикл while заканчивается, потому что счетчик в первой половине на A пересек опору. Но мы еще не закончили, мы должны добавить оставшиеся элементы, оставшиеся после разворота, то есть 6, 7. Это мы можем просто упасть в b, они уже отсортированы по предыдущим вызовам слияния. Вот для чего нужны последние оператор if и цикл.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector