Borna66
07-08-2012, 11:24 PM
روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه عناصر با استفاده از روش تقسیم و غلبه (http://www.algorithmha.ir/post-%D8%B1%D9%88%D8%B4-%D8%AA%D9%82%D8%B3%DB%8C%D9%85-%D9%88-%D8%BA%D9%84%D8%A8%D9%87.aspx) است. این روش از مراحل بازگشتی زیر تشکیل یافته است:
1- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کن.
2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.
3- دو زیرآرایه مرتب‌شده را ادغام کن.
http://pnu-club.com/imported/2012/07/187.jpg (http://www.algorithmha.ir/post-%D9%85%D8%B1%D8%AA%D8%A8-%D8%B3%D8%A7%D8%B2%DB%8C-%D8%A7%D8%AF%D8%BA%D8%A7%D9%85%DB%8C.aspx)
پیاده‌سازی مرتب‌سازی ادغامی
بر اساس توضیحات فوق قطعه کد زیر به زبان برنامه‌نویسی ++C الگوریتم مرتب‌سازی ادغامی را پیاده‌سازی می‌کند:
void merge_sort( int arr[ ], int low, int high )
{
if( low >= high )
{
return;
}
int mid = ( low + high ) / 2;
merge_sort( arr, low, mid );
merge_sort( arr, mid + 1, high );
merge( arr, low, mid, high );
}
این قطعه کد بازه‌های low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده، و سپس توسط تابع merge ادغام می‌کند. به این ترتیب آرایه arr از بازه low تا high مرتب می‌شود.
تابع merge پیاده‌سازی‌های مختلفی دارد. یک روش ساده آن است که ادغام دو زیرآرایه در یک آرایه کمکی به طول مجموع طول‌های این دو زیرآرایه صورت بگیرد. در این حالت این مرتب‌سازی یک مرتب‌سازی درجا نخواهد بود. چرا که متناسب با طول آرایه نیاز به فضای اضافی جهت مرتب‌سازی وجود دارد.
قطعه کد زیر یک پیاده‌سازی درجا برای تابع merge است:
void merge( int arr[ ], int low, int mid, int high )
{
int i, j, k, t;
j = low;
for( i = mid + 1 ; i <= high ; i++ )
{
while( arr[ j ] <= arr[ i ] && j < i )
{
j++;
}
if( j == i )
{
break;
}
t = arr[ i ];
for( k = i ; k > j ; k -- )
{
arr[ k ] = arr[ k - 1 ];
}
arr[ j ] = t;
}
}
این تابع محل مناسب عناصر زیرآرایه سمت راست را در زیرآرایه سمت چپ پیدا کرده و در آن درج می‌کند. با توجه به این که عناصر دو زیرآرایه مرتب هستند، ادغام آنها پیچیدگی کمتری خواهد داشت.
به عنوان مثال اگر هدف ادغام کردن زیرآرایه‌های زیر باشد:
1 3 6 9 / 2 4 5 8
ترتیب چینش عناصر پس از اتمام هر تکرار حلقه بیرونی قطعه کد فوق، به این ترتیب خواهد بود:
1) 1 3 6 9 / 2 4 5 8 => 1 2 3 6 9 / 4 5 8
2) 1 2 3 6 9 / 4 5 8 => 1 2 3 4 6 9 / 5 8
3) 1 2 3 4 6 9 / 5 8 => 1 2 3 4 5 6 9 / 8
4) 1 2 3 4 5 6 9 / 8 => 1 2 3 4 5 6 8 9 /
پیچیدگی زمانی مرتب‌سازی ادغامی
تعداد عناصر آرایه را n و تعداد مقایسه‌های مورد نیاز جهت مرتب‌سازی این عناصر را ( T( n در نظر می‌گیریم.
بر اساس تعریف بازگشتی این الگوریتم، مرتب کردن n عنصر نیاز به مرتب شدن دو زیر آرایه تقریبا n / 2 عنصری دارد. پس از این مرحله، این دو زیرآرایه توسط تابع merge ادغام می‌شوند.
جهت ادغام دو زیرآرایه با قطعه کد فوق - که در مجموع n عنصر دارند - حداکثر n مقایسه اتفاق خواهد افتاد (چرا؟). پس می‌توان نوشت:
T( n ) = 2 T( n / 2 ) + n
حل این رابطه بازگشتی نشان از مرتبه اجرای ( Ө( n log n دارد.
حافظه مصرفی مرتب‌سازی ادغامی
حافظه مازاد مورد نیاز برای این الگوریتم به روش پیاده‌سازی مرحله ادغام بستگی دارد. قطعه کد فوق این قسمت را به روش درجا پیاده‌سازی می‌کند. اما روش‌های ساده‌تری وجود دارند که عمل ادغام را روی حافظه دیگری غیر از حافظه تخصیص یافته به خود آرایه انجام می‌دهند. چنین الگوریتم‌هایی از نظر هزینه زمانی پیچیدگی کمتری دارند. اما برای یک آرایه به طول n، نیاز به آرایه مجزایی به همان اندازه جهت ادغام دارند.
ویژگی‌های مرتب‌سازی ادغامی
1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات ( Ө( n log n است. چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.
2- پیچیدگی حافظه مصرفی بستگی به روش پیاده‌سازی مرحله ادغام دارد، که تا ( O( n افزایش می‌یابد. پیاده‌سازی درجای این الگوریتم حافظه مصرفی مرتبه ( Ө( 1 دارد. اما اجرای آن در بدترین حالت زمانبر است.
3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.
1- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کن.
2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.
3- دو زیرآرایه مرتب‌شده را ادغام کن.
http://pnu-club.com/imported/2012/07/187.jpg (http://www.algorithmha.ir/post-%D9%85%D8%B1%D8%AA%D8%A8-%D8%B3%D8%A7%D8%B2%DB%8C-%D8%A7%D8%AF%D8%BA%D8%A7%D9%85%DB%8C.aspx)
پیاده‌سازی مرتب‌سازی ادغامی
بر اساس توضیحات فوق قطعه کد زیر به زبان برنامه‌نویسی ++C الگوریتم مرتب‌سازی ادغامی را پیاده‌سازی می‌کند:
void merge_sort( int arr[ ], int low, int high )
{
if( low >= high )
{
return;
}
int mid = ( low + high ) / 2;
merge_sort( arr, low, mid );
merge_sort( arr, mid + 1, high );
merge( arr, low, mid, high );
}
این قطعه کد بازه‌های low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده، و سپس توسط تابع merge ادغام می‌کند. به این ترتیب آرایه arr از بازه low تا high مرتب می‌شود.
تابع merge پیاده‌سازی‌های مختلفی دارد. یک روش ساده آن است که ادغام دو زیرآرایه در یک آرایه کمکی به طول مجموع طول‌های این دو زیرآرایه صورت بگیرد. در این حالت این مرتب‌سازی یک مرتب‌سازی درجا نخواهد بود. چرا که متناسب با طول آرایه نیاز به فضای اضافی جهت مرتب‌سازی وجود دارد.
قطعه کد زیر یک پیاده‌سازی درجا برای تابع merge است:
void merge( int arr[ ], int low, int mid, int high )
{
int i, j, k, t;
j = low;
for( i = mid + 1 ; i <= high ; i++ )
{
while( arr[ j ] <= arr[ i ] && j < i )
{
j++;
}
if( j == i )
{
break;
}
t = arr[ i ];
for( k = i ; k > j ; k -- )
{
arr[ k ] = arr[ k - 1 ];
}
arr[ j ] = t;
}
}
این تابع محل مناسب عناصر زیرآرایه سمت راست را در زیرآرایه سمت چپ پیدا کرده و در آن درج می‌کند. با توجه به این که عناصر دو زیرآرایه مرتب هستند، ادغام آنها پیچیدگی کمتری خواهد داشت.
به عنوان مثال اگر هدف ادغام کردن زیرآرایه‌های زیر باشد:
1 3 6 9 / 2 4 5 8
ترتیب چینش عناصر پس از اتمام هر تکرار حلقه بیرونی قطعه کد فوق، به این ترتیب خواهد بود:
1) 1 3 6 9 / 2 4 5 8 => 1 2 3 6 9 / 4 5 8
2) 1 2 3 6 9 / 4 5 8 => 1 2 3 4 6 9 / 5 8
3) 1 2 3 4 6 9 / 5 8 => 1 2 3 4 5 6 9 / 8
4) 1 2 3 4 5 6 9 / 8 => 1 2 3 4 5 6 8 9 /
پیچیدگی زمانی مرتب‌سازی ادغامی
تعداد عناصر آرایه را n و تعداد مقایسه‌های مورد نیاز جهت مرتب‌سازی این عناصر را ( T( n در نظر می‌گیریم.
بر اساس تعریف بازگشتی این الگوریتم، مرتب کردن n عنصر نیاز به مرتب شدن دو زیر آرایه تقریبا n / 2 عنصری دارد. پس از این مرحله، این دو زیرآرایه توسط تابع merge ادغام می‌شوند.
جهت ادغام دو زیرآرایه با قطعه کد فوق - که در مجموع n عنصر دارند - حداکثر n مقایسه اتفاق خواهد افتاد (چرا؟). پس می‌توان نوشت:
T( n ) = 2 T( n / 2 ) + n
حل این رابطه بازگشتی نشان از مرتبه اجرای ( Ө( n log n دارد.
حافظه مصرفی مرتب‌سازی ادغامی
حافظه مازاد مورد نیاز برای این الگوریتم به روش پیاده‌سازی مرحله ادغام بستگی دارد. قطعه کد فوق این قسمت را به روش درجا پیاده‌سازی می‌کند. اما روش‌های ساده‌تری وجود دارند که عمل ادغام را روی حافظه دیگری غیر از حافظه تخصیص یافته به خود آرایه انجام می‌دهند. چنین الگوریتم‌هایی از نظر هزینه زمانی پیچیدگی کمتری دارند. اما برای یک آرایه به طول n، نیاز به آرایه مجزایی به همان اندازه جهت ادغام دارند.
ویژگی‌های مرتب‌سازی ادغامی
1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات ( Ө( n log n است. چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.
2- پیچیدگی حافظه مصرفی بستگی به روش پیاده‌سازی مرحله ادغام دارد، که تا ( O( n افزایش می‌یابد. پیاده‌سازی درجای این الگوریتم حافظه مصرفی مرتبه ( Ө( 1 دارد. اما اجرای آن در بدترین حالت زمانبر است.
3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.