تماس با ما

هرگونه پیشنهاد و انتقاد خود را با ما در میان بگذارید

مرتب سازی ادغامی یکی از سریع ترین روش های مرتب سازیه که پیچیدگی اون از مرتبه O(nLg(n)) هست در عین حال الگوریتم ساده ای هم داره که یادگیری و پیاده سازی اون رو خیلی ساده میکنه برای اینکه شیوه کار این الگوریتم رو توضیح بدم اول یک مثال میزنم، به این لیست اعداد یه نگاه بندازید:

1 7 4 11 9 2 13 14 3 10

خب حالا برای مرتب کردن این اعداد به این ترتیب عمل میکنیم:

  • اول: این آرایه از اعداد رو به دو قسمت تقسیم میکنیم که میشه این طوری:

    1 7 4 11 9

    2 13 14 3 10
  • دوم: حالا این دو تا آرایه جداگانه رو به یه روشی مرتب میکنیم مثلا میشه به صورت بازگشتی با همین الگوریتم مرتب کرد پس نتیجه میشه این شکلی:

    1 4 7 9 11

    2 3 10 13 14
  • سوم: حالا این دوتا آرایه رو در هم ادغام میکنیم جوری که ترتیب بهم نخوره یعنی وقتی داریم این دو تا آرایه به یک آرایه 10 عضوی اضافه میکنیم مقایسه میکنیم و عدد کوچک تر رو اول اضافه میکنیم، چونکه دو تا آرایه مرتبه این کار خیلی سخت نیست و فقط ابتدای دوتا آرایه رو که هنوز اضافه نکردیم باید مقایسه کنیم، اگر شکل رو نگاه کنید به صورت انیمیشن ادغام دوتا آرایه مرتب رو نشون داده:

    ادغام دو آرایه مرتب
    الگوریتم ادغام رو به زبان ++C نوشتم:
    int SortedArray[9];
    int Array1[4]={2,3,10,13,14};
    int Array2[4]={1,4,7,9,11};
    int i=0, j=0;
    for(int k=0; k<10 ;k++)
    {
    	if(Array1[i] < Array2[j])
    	{
    		SortedArray[k]=Array1[i];
    		i++;
    	}
    	else
    	{
    		SortedArray[k]=Array2[j];
    		j++;
    	}
    	if(i>=5) for(k++;j<5;j++,k++) SortedArray[k]=Array2[j];
    	if(j>=5) for(k++;i<5;i++,k++) SortedArray[k]=Array1[i];
    }

    پیداست که این روش ادغام در 10 مرحله انجام میشه و به طور کلی پیچیدگی الگوریتم به این روش O(n) هست حالا اگه اون دو تا آرایه رو هم به همین روش بخواهیم مرتب کنیم، یعنی اینکه اول دو قسمتشون کنیم و بعد برای هر قسمت دوباره به صورت بازگشتی همین الگوریتم رو پیاده کنیم در نهایت بعد از 4 بار آرایه های قسمت شده تک عضوی میشن و دیگه لازم نیست که مرتب بشن (چون آرایه تک عضوی مرتبه) و فقط باید ادغام رو شروع کنیم
    شکل زیر مراحل تقسیم و ادغام رو نشون داده:
     
    از شکل کاملا پیداست که چرا به این روش میگن مرتب سازی ادغامی، در واقع اگر بخواهید این روش مرتب سازی رو به صورت غیر بازگشتی بنویسید دیگه لازم نیست که آرایه رو تقسیم کنید فقط کافیه از همون اول ادغام رو شروع کنید مثلا میتونید اول 2تا 2تا ادغام کنید بعد 4تا 4تا ادغام کنید و همینطور ادامه بدید تا اینکه کل آرایه مرتب بشه.

اینم الگوریتم کامل به شیوه بازگشتی که به زبان ++C نوشتم، الگوریتم ادغامش مثل الگوریتم بالاس که یه کم تغییر دادم :

int Array[9];

void MergeSort(int a, int b)
{
	if(b > a)
	{
		int middle=(b-a)/2;
		MergeSort(a,middle);
		MergeSort(middle+1,b);
		Merge(a,middle,b);
	}
}

void Merge(int a,int middle,int b)
{
	int i=a, j=middle+1;
	int tempArray[9];
	for(int k=0; k<b ;k++)
	{
		if(Array[i] < Array[j])
		{
			tempArray[k]=Array[i];
			i++;
		}
		else
		{
			tempArray[k]=Array[j];
			j++;
		}
		if(i >= middle+1) for(k++; j<b; j++, k++) tempArray[k]=Array[j];
		if(j >= b) for(k++; i<middle; i++, k++) tempArray[k]=Array[i];
	}
	for(i=0; i<k; i++) Array[i]=tempArray[i];
}

 با توجه به اینکه هر بار آرایه دو قسمت میشه و پیچیدگی بخش ادغام از درجه O(n) هست پس نتیجه میگیریم که پیچیدگی کل این الگوریتم از درجه O(nLog2(n)) است.

نکته: پیچیدگی الگوریتم مرتب سازی ادغامی همیشه از درجه O(nLog2(n)) است و کم و زیاد نمیشه حتی اگر آرایه از قبل مرتب شده باشه، در حالی که در بعضی از الگوریتم ها مثل مرتب سازی سریع پیچیدگی الگوریتم به این بستگی داره که آرایه چقدر و چطور نا مرتب باشه، بنابر این اگه نمیدونید که آرایه چه وضعیتی داره بهتره که از این روش استفاه کنید اما اگر وضعیت آرایه از قبل مشخصه (مثلا میدونیم که آرایه تا حدودی مرتبه) اون وقت شاید الگوریتم های سریع تری هم بشه پیدا کرد.


برای اطلاعات بیشتر:

https://fa.wikipedia.org/

http://www.algorithmha.ir/

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort

http://maktabkhooneh.org/video/abam266-3