برنامه merg sort با روشهای تقسیم و حل

[lionking_1360]

سلام
کسی می تونه در برنامه merg sort بجای تقسیم به 2 زیر آرایه از 3 زیر آرایه به من کمک کنه

[MiRHaDi]

سلام
پروژه دانشگاته ؟
من میتونم ! حالا سوالت چیه ؟
خوب ببین ! یکم باید الگوریتمتو عوض کنی
به جای اینکه نصفه پاینی و بالایی رو جدا سورت کنی 3 قسمت میکنیش ! یعنی از اول تا 3/1 از 3/1 تا 3/2 و از 3/2 تا آخر ! بعد مرج میکنی و یه تا اشاره گر به 3 تا لیستت میذاری و یکی یکی مثل حالت دو تایی میری جلو
بای

[lionking_1360]

سلام
نه پروژه دانشگاه نیست یه تمرین
من خودم قبلا اینکارو کردم ولی جواب نداده
اینهم چیزی که نوشتم

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
//**************************
int a[12];
int temp = 0;
//**************************
void Merg(int low , int high)
{
int i , j , k , mid;
int temp[10];
mid = (low + high)/2;
for(i = low ; i <= mid ; i++)
temp[i] = a[i];
for(i = mid+1 ; i <= high ; i++)
temp[mid+1+high-i] = a[i];
j = low ; k = high;
for(i = low ; i <= high ; i++)
a[i] = (temp[j] < temp[k]) ? temp[j++] : temp[k--];
}
//**************************
void MergSort(int low , int high)
{
int mid , mid1;

if(high > low){
mid = (low + high)/3;
mid1 = (2 * mid) + 1;
MergSort(low, mid);
MergSort(mid+1,mid1);
MergSort(mid1+1 , high);
Merg(low , high);
}
}
//**************************
void main()
{
int n;
clrscr();
cin>>n;
//*************Input********************
for(int i = 0 ; i < n ; i++) cin>>a[i];
//*****************Sort******************
MergSort(0 , n-1);
//****************OutPut*****************
for( i = 0; i < 5 ; i++)
cout<<a[i];
}
//***************************
اگر بتونی اشکال برنامه رو بگی یا اونو دورست کنی ممنون میشم

[B-Vedadian]

با سلام،

الگوریتم Merge فوق تنها برای تقسیم به دو بخش عمل درست را انجام میدهد. کافیست آن را برای حالت سه بخشی دوباره بنویسید.

[Developer Programmer]

متاسفانه این سوال رو در امتحان پایان ترم داده بودند

[lionking_1360]

سلام
آقای B-Vedadian من هم می خوام همینو بدونم که چطوری این کارو انجام بدم اگر شما می دونید لطفا کمک کنید

[B-Vedadian]

نمی دونم الآن چقدر به درد می خوره ولی الگوریتم معمولش رو که ما استفاده می کردیم اینیه که بعد توضیح مینویسمش، اگه بدون دیدن خود برنامه بتونید از توضیحات پیاده سازیش کنید قاعدتا خیلی به نفعتونه.

فرض کنید اسم سه بخش که باید با هم مخلوط شن A,B,C و نتیجه D باشه.

روش عامش به این صورته که از عنصر صفر D شروع میکنیم و در بین عناصر باقیمانده از A,B,C بزرگترین و یا کوچکترین رو انتخاب کرده در عنصر صفر D قرار میدیم و از لیست عناصر باقیمانده خطش می زنیم، برای عناصر بعدی هم دقیقا همین کار رو انجام میدیم.










void merge(s1,e1,s2,e2,s3,e3,sr)
{
int i=0,j=0,k=0;
for(int l=0;l++;l<e1-s1+e2-s2+e3-s3+3)
{
if(i<e1-s1+1)
if(a[s1+i]>a[s2+j] && a[s1+i]>a[s3+k])
{
a[sr+l]=a[s1+i];
i++;
}
if(j<e2-s2+1)
if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k])
{
a[sr+l]=a[s2+j];
j++;
}
if(k<e3-s3+1)
if(a[s3+k]>a[s1+i] && a[s3+k]>a[s2+j])
{
a[sr+l]=a[s3+k];
k++;
}
}
}

در متن زیربرنامه مرتب ساز هم



.
.
.

Merge(low,mid,mid+1,mid1,mid1+1,high,low,high);

.
.
.

[lionking_1360]

خیلی ممنون
برنامه رو امتحان میکنم اگر مشکلی بود بازم میپرسم

[lionking_1360]

سلام آقای B-Vedadian
من این کد رو که نوشتید امتحان کردم اصلا کار نمیکرد
لطفا اگه برنامه اش رو نوشتید یا اگه بتونید یه توضیح بیشتری بدید ممنون میشم

[zizi_zizi69]

در الگوریتم merge از یک آرایه کمکی (auxiliary array) برای مرتب کردن دو لیستی که می خواهند ادغام شوند استفاده می شود . در نهایت هم نتیجه از این آرایه به آرایه اصلی کپی میشود.


آیا راهی وجود دارد که از آرایه کمکی استفاده نکرد،چون در هر حال این آرایه سبب به هدر رفتن حافظه می شود.


void merge (float v[], int start, int mid, int end) {
int i, j, k;
float tmp[end-start];
i = start;
j = mid;
k = 0;
while ((i < mid) && (j < end)){
if (v[i] <= v[j])
tmp[k++] = v[i++];
else
tmp[k++] = v[j++];
}
while (i < mid) tmp[k++] = v[i++];
while (j < end) tmp[k++] = v[j++];
for (i = 0; i < (end-start); i++) v[start+i] = tmp[i];
}


در اینجا از آرایه کمکی temp استفاده شده است.

[lionking_1360]

سلام
این کد که شما نوشتید برای Merg Sort برای تقسیم به 2 زیر آرایه هست من برای تقسیم به 3 زیر آرایه می خوام
اگر می دونید کمک کنید

[B-Vedadian]

سلام،

مشکلی که در اجرا نشدن برنامه اریه شده از طرف من وجود دارد، همین آرایه کمکی است. در زیر برنامه داده شده نتیجه بلافاصله در آرایه مبدا ذخیره می شود و این مساله باعث از بین رفتن داده های اولیه می گردد.

احتمالا کد زیر درست کار کند.


void merge(s1,e1,s2,e2,s3,e3,sr)
{
int i=0,j=0,k=0;
int* temp;
temp=new int[e1-s1+e2-s2+e3-s3+3];
for(int l=0;l++;l<e1-s1+e2-s2+e3-s3+3)
{
if(i<e1-s1+1)
if(a[s1+i]>a[s2+j] && a[s1+i]>a[s3+k])
{
temp[l]=a[s1+i];
i++;
}
if(j<e2-s2+1)
if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k])
{
temp[sr+l]=a[s2+j];
j++;
}
if(k<e3-s3+1)
if(a[s3+k]>a[s1+i] && a[s3+k]>a[s2+j])
{
temp[sr+l]=a[s3+k];
k++;
}
}
for(l=sr;l<sr+e1-s1+e2-s2+e3-s3+3;l++)
a[l]=temp[l-sr];
delete[] temp;
}

[zizi_zizi69]

تابع merge که اینجا code شده همون چیزی که دوستمون نوشته بود فقط شاید یکم خوانا تر باشه .
فقط یک مشکلی هست. فرض کنید ما اینقدر لیست اصلی را تقسیم کردیم که به سه زیر لیست
27,10,12 می رسیم.اشاره گر اولی (h) به 27 دومی(l) به 10 و سومی(j) به 12 اشاره دارد. mid1=1 و mid2=2 است.
بعد 10 بعنوان کوچکترین عنصر در شرط if چهارمی صدق می کند. مقدارl برار 3 میشود ودیگر وارد if دومی نمی شویم. و باید a[j] و a[h]مقایسه شوند.در صورتی که ما هر بار مقایسه با a[l] هم داریم. واین باعث ایجاد مشکل می شود. اگر trace کنید معلوم میشود.


void merge (float a[], int start, int mid1, int mid2, int end)
{ int i, j, k,l,h;
float tmp[end-start+1];
h = start;
i = start;
l = mid1+1;
j = mid2+1;
for(k=0;k++;k<=end){
if (h<=mid1)//h must be between start..mid1
if ((a[h]<=a[l]) && (a[h]<=a[j]))//is a[h] the smallest in the three sublist
tmp[i++] = a[h++];

if (l<=mid2)//l must be between mid1+1..mid2
if ((a[l]<=a[h]) && (a[l]<=a[j]))//is a[l] the smallest in the three sublist
tmp[i++] = a[l++];

if (j<=end)//j must be between mid2+1..end
if ((a[j]<=a[h]) && (a[j]<=a[l]))//is a[j] the smallest in the three sublist
tmp[i++] = a[j++];
}//end for
}//end merge

[lionking_1360]

سلام
آقای B-Vedadian این متغیر ها رو میشه معرفی کنید
s1,e1,s2,e2,s3,e3,sr
ممنون

[B-Vedadian]

سلام،

اندیس شروع بخش اول : s1

اندیس پایانی بخش اول : e1

...

اندیس شروع بخش نتیجه : sr

[B-Vedadian]

در ضمن دوست عزیز zizi

من مشکل رو نفهمیدم مخصوصا که اصلا سه زیر لیست 10و12و27 یعنی چه و چطوری mid ها 1و2 میشند.

[zizi_zizi69]

آقای B-Vedadianفرض کنید
ما می خواهیم لیست حاوی اعداد 27,10,12,20,25,13,15,22,8 را mergesort کنیم. ابتدا توسط mergesort لیست ما به سه زیر لیست 20,25,13 / 15,22,8 27,10,12 / تقسیم میشود. بعد دوباره بعد دوباره mergesort روی لیست سمت چپ اعمال میشه. سه زیر لیست 27/10/12 خواهیم داشت.
که این سه تا تابع merge را فراخوانی می کنند.
پس s1,e1,s2,e2,s3,e3 به ترتیب 1,1,2,2,3,3 میشند.
وارد if ا ولی میشیم 0<1 است
وارد if د ومی میشیم if(a[s1+i]>a[s2+j] && a[s1+i]>a[s3+k])
if(a[1]>a[2] && a[1]>a[3]) ( یعنی 27>10,27>12) =T ، پس i =1 و27 هم در temp قرار می گیره.
بعد وارد if چهارمی که شد :
if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k])
if(a[2]>a[1+1] && a[2]>a[3]) ( یعنی 10>10,10>12) = F
بعد وارد if ششمی که شد:
if(a[s3]>a[1+1] && a[3]>a[2]) (12>10,12>10) =T، K=1 و12 هم در temp قرار می گیره.
بعد دوباره if ها چک میشند و به if می رسیم
if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k]) = if(a[2]>a[1+1] && a[2]>a[3+1])=F

بنا براین عدد 10 در temp قرار نمی گیره!

[B-Vedadian]

درست است ، وقتی که k>e3-s3+1 است و هنوز دو زیر لیست دیگر باقیمانده اند مشکل پیش میآید. باید هر کدام از if ها بصورت زیر اصلاح شوند:


if( (a[s1+i]>a[s2+j] || j>=e2-s2+1) && (a[s1+i]>a[s3+k] || k>=e3-s3+1) )
{
temp[l]=a[s1+i];
i++;
}

[zizi_zizi69]

من این برنامه را بکمک دوستم نوشتم که از یک روش دیگه انجام شده.اول لیست رو سه قسمت می کنیم بعد دوتا دوتا merge کنیم. تابع merge همان چیزیه که برای دوتایی بکار می ره.درست جواب میده.


void sort (int start, int end) {
int mid;
if (begin < end)
sols(ثلث)= حد بالای (end-strat+1)/3
msort (start,strat+sols-1 );
msort (start+sols,start+2sols-1 );
msort (start+2sols,end);
merge (start,start+sols-1,start+2sols-1);
merge (start,start+2sols-1,end);
}

[zizi_zizi69]

من این برنامه را بکمک دوستم نوشتم که از یک روش دیگه انجام شده.اول لیست رو سه قسمت می کنیم بعد دوتا دوتا merge کنیم. تابع merge همان چیزیه که برای دوتایی بکار می ره.درست جواب میده.



void msort (int start, int end) {
int sols;
if (begin < end)
sols= ceil((end-strat+1)/3);
msort(start,strat+sols-1 );// recursive functuion
msort(start+sols,start+2sols-1 ); // recursive functuion
msort(start+2sols,end); // recursive functuion
merge(start,start+sols-1,start+2sols-1);
merge(start,start+2sols-1,end);
}


:موفق:

[رضا جاسبی]

دوستان عزیز
نکته بسیار مهم در اینگونه الگوریتمها در استفاده از توابع بازگشتی ( Recursive ) است. من توی هیچ یک از کدهای دوستان این حالت را ندیدم. ولی قبل از اینکه راه حلم را بنویسم می خواهم از دوستمون lionking_1360 بپرسم که چرا می خواهی این حالت را امتحان کنی؟ توجه داشته باش که در بخش Merge در حالت سه تایی تعداد مقایسه ها بالا می رود ، پیچیدگی زیاد می شود و کارآیی الگوریتم پایین می آید. چیزی که این الگوریتمها به شدت از آن پرهیز دارند.
من فقط در مورد الگوریتم، شبه کد می نویسم البته شبیه به کد C. لطفا پیاده سازی اصلی را یکی از دوستان انجام دهد و نتیجه را اعلام کند ممنون . فقط توجه داشته باشید که تابع ceil تابعی است که سقف یک عدد اعشاری را می دهد. Ceil(1.3) = Ceil(1.6)= 2 مطمئن نیستم که این تابع درست باشد یا خیر. شرمنده ! یک کم C یادم رفته. :sorry:
این روش مرتب سازی صعودی است. طبیعتا در نزولی تغییرات مربوطه را دارد.




// Declare Array A
int A[MAXNUMBER];
// or int A[] = { ... }
int Min(A1Indx , A2Indx , A3Indx )
{
if ( A1Indx = -1 )
{
if ( A3Indx = -1 ) return 2;
if ( A2Indx = -1 ) return 3; // you can use "else if" for more readability
if ( A[A2Indx] > A[A3Indx] ) return 3
return 2;
}

if ( A2Indx = -1 )
{
if ( A3Indx = -1 ) return 1;
if ( A1Indx = -1 ) return 3;
if ( A[A1Indx] > A[A3Indx] ) return 3
return 1;
}

if ( A3Indx = -1 )
{
if ( A2Indx = -1 ) return 1;
if ( A1Indx = -1 ) return 2;
if ( A[A1Indx] > A[A2Indx] ) return 2
return 1;
}

if ( A[A1Indx] > A[A2Indx] )
{
if (A[A2Indx] > A[A3Indx] ) return 3;
return 2;
}
else
{
if (A[A1Indx] > A[A3Indx] ) return 3;
return 1;
}
}

Merge (A1Start , A1End , A2Start , A2End , A3Start , A3End)
{
int temp[100]; //if you want you can use dynamic allocation if your programming language let you. int * Temp , Temp = malloc(...) ...
int A1Indx , A2Indx , A3Indx , Indx ;

for (Indx = 0 , A1Indx = A1Start , A2Indx = A2Start , A3Indx = A3Start ;
A1Indx != -1 || A2Indx != -1 || A3Indx != -1 ; )
{
switch (Min(A1Indx , A2Indx , A3Indx) )
{
case 1 :
Temp[Indx++] = A[A1Indx++];
if ( A1Indx > A1End ) A1Indx = -1;
break;
case 2 :
Temp[Indx++] = A[A2Indx++];
if ( A2Indx > A2End ) A2Indx = -1;
break;
case 3 :
Temp[Indx++] = A[A3Indx++];
if ( A3Indx > A3End ) A3Indx = -1;
break;
}
}
for ( Indx = Start ; AIndx < A3End ; Indx++)
{
A[Indx] = Temp[Indx - Start];
}
}

Merge_sort( int Start , int End )
{
int Len;

Len = End - Start + 1
if ( Len = 1 || Start = -1 ) return;

//split Array A to 3 part; A1 , A2 , A3 with related Start and End (A1Start , A1End , ... )
A1Start = Start;
A1End = ceil(Start + Len/3 - 1 )

A2Start = A1End + 1
A2End = ceil(Start + (2*Len)/3 - 1)

A3Start = A2End + 1
A3End = End;
if Len = 2
A3Start = -1;

MergeSort(A1Start , A1End); // recursive functuion
MergeSort(A2Start , A2End); // recursive functuion
MergeSort(A3Start , A3End); // recursive functuion

Merge(A1Start , A1End , A2Start , A2End , A3Start , A3End);
}

void main(void)
{
int Start = 0; // or 1;
int End = MAXNUMBER; // or any value I mean number of items in A to be sorted.
// Initial A
MergeSort(Start , End );
// Print Array A which is sorted;
}

[zizi_zizi69]

نکته بسیار مهم در اینگونه الگوریتمها در استفاده از توابع بازگشتی ( Recursive ) است. من توی هیچ یک از کدهای دوستان این حالت را ندیدم.

دوست عزیز تمام زیربرنامه های این topic بازگشتی هستند. چون ما آرایه اصلی را با کمک تابع mergesort به آرایه های کوچکتر تقسیم می کنیم . وانقدر تابع را بصورت بازگشتی صدا می کنیم تا زیر آرایه ها بقدر کافی کوچک باشند.
الگوریتم های mergesort از روش تقسیم و حل (Divide and Conquer) تبعیت می کنند. که این روش یک روش طراحی بالا به پایین ( top_down design ) است. یعنی حل یک مسله باحل نمونه های کوچک از آن. که این همای روش بکار رفته در حل روالهای بازگشتی است.

[zizi_zizi69]

توجه داشته باش که در بخش Merge در حالت سه تایی تعداد مقایسه ها بالا می رود ، پیچیدگی زیاد می شود و کارآیی الگوریتم پایین می آید.

البته زمان اجرای یک الگوریتم بستگی به خود الگورینم دارد. پیچیدگی زمانی mergesort در حالث دوتایی )nlogn در مبنای 2 ) می باشد. برای حالتی که آرایه به سه قسمت تقسیم می شود ، برای الگوریتمی که من نوشتم پیچیدگی زمانی nlogn ( در مبنای 3) میباشد.
چون nlogn ( در مبنای 2) > nlogn ( در مبنای 3) ، پس کارایی mergesort در حالت سه قسمتی بهتر است.

[karshenasi]

ببخشید که این تاپیک زیر خاکی را بالا آوردم
من میخام همین الگوریتم مرج سورت رو به جای سه زیر لیست به پنج زیر لیست تقسیم کنم
کسی هست که بتونه کمکم کنه ؟