Метод естественного слияния
P.S. Кстати, была бы весьма желательна соответствующая блок-схема.
В твоем источнике описана, как я понимаю, сортировка для файлов, а меня интересуют массивы. И чтобы убрать все неопределенности, напишу обо всем более подробно.
Под методом естественного слияния я понимаю следующее.
Исходная последовательность p0 сначала определяется упорядоченной группой, которые сформировались непроизвольно. При этом определяется количество упорядоченных групп. Затем каждая пара последовательности упорядоченных групп сливаются в одну упорядоченную группу и т.д. до упорядочивания последовательности в целом.
Мне кажется, что вышесказанное немного не совпадает содержимым лекции, которую ты прислал. К тому же там нет самого главного: там нет исходника. Итак, могу ли я рассчитывать на чью-либо помощь?
:confused:
В твоем источнике описана, как я понимаю, сортировка для файлов, а меня интересуют массивы.
абсолютно не важно как написан пример (лиж бы правильный был).
если есть желание, садишься и разбираешься в сортировке и применяешь ее к массивам, а если нет желания - ждешь когда кто нибудь за тебя все сделает.
если есть желание, садишься и разбираешься в сортировке и применяешь ее к массивам, а если нет желания - ждешь когда кто нибудь за тебя все сделает.
1. Я вообще сомневаюсь, что этот пример - именно то, что мне нужно (см. мое предыдущее сообщение).
2. В данный момент я действительно жду, "когда кто-нибудь" сделает то, что я прошу или укажет ссылку на исходник. Очень надеюсь на помощь. :(
Что ж, буду иметь в виду. Так сможет ли кто-нибудь прислать мне код на Си?
Очень признателен за эти ссылки. Но, к сожалению, с их помощью мне не удалось полностью выполнить задание.
Дорогие друзья! Помогите, пожалуйста. Мне очень срочно нужна сортировка методом естественного слияния. Я пытался разобраться с материалами, на которые мне указывали, но полноценной программы до сих пор составить не смог.
P.S. И у меня есть сомнения в том, что слияние и естественное слияние - это равноправные понятия.
Да, это действительно так. Я прошу о "сортировке файлов".
Повторяю:
Под методом естественного слияния я понимаю следующее.
Исходная последовательность p0 сначала определяется упорядоченной группой, которые сформировались непроизвольно. При этом определяется количество упорядоченных групп. Затем каждая пара последовательности упорядоченных групп сливаются в одну упорядоченную группу и т.д. до упорядочивания последовательности в целом.
Как вы думаете: подходят ли указанные алгоритмы под это определение? :confused:
При естественном слиянии из исходной последовательности выделяются две частично упорядоченные последовательности (возможно разного размера) и сливаются они. Процесс выбора продолжается, пока исходная последовательность не закончится. Процесс сортировки завершается, если можно выделить только одну последовательность.
#include <iostream>
#include <math.h>
using namespace std;
template<class T> void Merge(T const *const A, int const nA,
T const *const B, int const nB,
T *const C)
{
int a(0), b(0);
while( a+b < nA+nB )
{
if( (b>=nB) || ( (a<nA) && (A[a]<=B) ) )
{
C[a+b] = A[a];
++a;
} else {
C[a+b] = B;
++b;
}
}
};
template<class T> void NaturalSort(T *A, int const n)
{
T *B( new T[n] );
while(true)
{
int start1, end1;
int start2(-1),end2(-1);
while(true)
{
//Íà÷àëî ïåðâîãî ó÷àñòêà äëÿ ñëèÿíèÿ íàõîäèòñÿ ïîñëå
// êîíöà âòîðîãî ó÷àñòêà ïðåäûäóùåé ïàðû:
start1 = end2+1;
end1 = start1;
//Äâèãàåìñÿ âïðàâî äî íàðóøåíèÿ ñîðòèðîâêè:
while( (end1<n-1) && (A[end1]<=A[end1+1]) ) ++end1;
//Ïåðâûé ó÷àñòîê ïàðû ïðîñòèðàåòñÿ äî êîíöà ìàññèâà:
if( end1 == n-1 ) break;
//Íà÷àëî âòîðîãî ó÷àñòêà äëÿ ñëèÿíèÿ íàõîäèòñÿ ïîñëå
// êîíöà ïåðâîãî ó÷àñòêà òåêóùåé ïàðû:
start2 = end1+1, end2 = start2;
//Äâèãàåìñÿ âïðàâî äî íàðóøåíèÿ ñîðòèðîâêè:
while( (end2<n-1) && (A[end2]<=A[end2+1]) ) ++end2;
//Âûïîëíÿåì ñëèÿíèå äâóõ îòñîðòèðîâàííûõ ó÷àñòêîâ
Merge(A+start1, end1-start1+1, A+start2, end2-start2+1, B+start1);
//Âòîðîé ó÷àñòîê ïàðû ïðîñòèðàåòñÿ äî êîíöà ìàññèâà:
if( end2 == n-1 ) break;
}
//Äàííûå ïîëíîñòüþ îòñîðòèðîâàíû è íàõîäÿòñÿ â ìàññèâå A:
if( (start1==0) && (end1==n-1) ) break;
//Åñëè ïîñëåäíèé êóñî÷åê îñòàëñÿ áåç ïàðû, ïðîñòî êîïè-
// ðóåì åãî èç A â B:
if( end1 == n-1 )
{
for(; start1<n; ++start1) B[start1]=A[start1];
}
T *temp(B);
B=A;
A=temp; //Ìåíÿåì ìåñòàìè óêàçàòåëè
}
for(int i=0; i<n;i++) cout<<A<<'\t';
cout<<endl;
delete B; //Óäàëÿåì âðåìåííûé áóôåð
}
int main()
{
clock_t start, end;
int n=5;
int A[n];
for(int i=0; i<n; i++) A = rand()%100;
start = clock();
NaturalSort(A, n);
end = clock();
cout<<"Time: "<<((double)(end-start))/CLOCKS_PER_SEC<<" sec"<<endl;
system("PAUSE");
}