Borna66
07-08-2012, 11:39 PM
روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر لیست را به صورت صعودی یا نزولی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده، و به انتهای لیست منتقل می‌کند.
لیست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:
2 8 4 1 7
در مرحله اول، کل لیست از ابتدا تا انتها بررسی شده، و بزرگترین عنصر با عنصر انتهای لیست نامرتب جابجا می‌شود:
1) 2 8 4 1 7 -> 2 7 4 1 8
در مرحله دوم، پیمایش از ابتدای لیست تا عنصر چهارم صورت گرفته، و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود:
2) 2 7 4 1 8 -> 2 1 4 7 8
علت این که چرا عنصر پنجم بررسی نمی‌شود کاملا مشخص است. این عنصر در مرحله قبل به عنوان بزرگترین عنصر به انتهای لیست منتقل شده است، و به طور حتم نیاز به جابجایی ندارد.
در مرحله سوم، عناصر اول تا سوم بررسی شده و بزرگترین عنصر به انتهای آن منتقل می‌شود:
3) 2 1 4 7 8 -> 2 1 4 7 8
و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:
4) 2 1 4 7 8 -> 1 2 4 7 8
و به این ترتیب لیست مرتب می‌شود.
پیاده‌سازی مرتب‌سازی انتخابی
الگوریتم مرتب‌سازی انتخابی به زبان برنامه‌نویسی ++C برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:
void selection_sort( int arr[ ], int n )
{
int i, j, max, temp;
for( i = n - 1 ; i > 0 ; i-- )
{
max = 0;
for( j = 1 ; j <= i ; j++ )
{
if( arr[ max ] < arr[ j ] )
{
max = j;
}
}
temp = arr[ i ];
arr[ i ] = arr[ max ];
arr[ max ] = temp;
}
}
حلقه بیرونی حد نصاب پیمایش را مشخص کرده، و حلقه درونی به ازای هر تکرار حلقه بیرونی، بزرگترین عنصر لیست نامرتب را می‌یابد. سپس محل این عنصر با عنصر انتهای بخش نامرتب جابجا می‌شود.
پیچیدگی زمانی مرتب‌سازی انتخابی
تعداد عناصر لیست را n در نظر می‌گیریم. بر اساس توضیحات فوق این الگوریتم n - 1 مرحله دارد. در هر مرحله، عنصر ابتدایی در max قرار گرفته، و بقیه عناصر با آن مقایسه می‌شوند. پس در مرحله اول تعداد n - 1 مقایسه، در مرحله دوم تعداد n - 2 مقایسه، و به همین ترتیب در مرحله iام تعداد n - i مقایسه صورت می‌گیرد. پس اگر ( T( n تعداد کل مقایسه‌ها را نشان دهد، می‌توان نوشت:
T( n ) = ( n - 1 ) + ( n - 2 ) + ( n - 3 ) + ... + 2 + 1 = n ( n - 1 ) / 2
که از مرتبه ( Θ( n2 است.
ویژگی‌های مرتب‌سازی انتخابی
1- پیچیدگی زمانی اجرای این الگوریتم بر اساس محاسبات فوق در بدترین حالت ( Θ( n2 است. با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز ( Θ( n2 است.
2- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.
3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.
لیست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:
2 8 4 1 7
در مرحله اول، کل لیست از ابتدا تا انتها بررسی شده، و بزرگترین عنصر با عنصر انتهای لیست نامرتب جابجا می‌شود:
1) 2 8 4 1 7 -> 2 7 4 1 8
در مرحله دوم، پیمایش از ابتدای لیست تا عنصر چهارم صورت گرفته، و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود:
2) 2 7 4 1 8 -> 2 1 4 7 8
علت این که چرا عنصر پنجم بررسی نمی‌شود کاملا مشخص است. این عنصر در مرحله قبل به عنوان بزرگترین عنصر به انتهای لیست منتقل شده است، و به طور حتم نیاز به جابجایی ندارد.
در مرحله سوم، عناصر اول تا سوم بررسی شده و بزرگترین عنصر به انتهای آن منتقل می‌شود:
3) 2 1 4 7 8 -> 2 1 4 7 8
و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:
4) 2 1 4 7 8 -> 1 2 4 7 8
و به این ترتیب لیست مرتب می‌شود.
پیاده‌سازی مرتب‌سازی انتخابی
الگوریتم مرتب‌سازی انتخابی به زبان برنامه‌نویسی ++C برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:
void selection_sort( int arr[ ], int n )
{
int i, j, max, temp;
for( i = n - 1 ; i > 0 ; i-- )
{
max = 0;
for( j = 1 ; j <= i ; j++ )
{
if( arr[ max ] < arr[ j ] )
{
max = j;
}
}
temp = arr[ i ];
arr[ i ] = arr[ max ];
arr[ max ] = temp;
}
}
حلقه بیرونی حد نصاب پیمایش را مشخص کرده، و حلقه درونی به ازای هر تکرار حلقه بیرونی، بزرگترین عنصر لیست نامرتب را می‌یابد. سپس محل این عنصر با عنصر انتهای بخش نامرتب جابجا می‌شود.
پیچیدگی زمانی مرتب‌سازی انتخابی
تعداد عناصر لیست را n در نظر می‌گیریم. بر اساس توضیحات فوق این الگوریتم n - 1 مرحله دارد. در هر مرحله، عنصر ابتدایی در max قرار گرفته، و بقیه عناصر با آن مقایسه می‌شوند. پس در مرحله اول تعداد n - 1 مقایسه، در مرحله دوم تعداد n - 2 مقایسه، و به همین ترتیب در مرحله iام تعداد n - i مقایسه صورت می‌گیرد. پس اگر ( T( n تعداد کل مقایسه‌ها را نشان دهد، می‌توان نوشت:
T( n ) = ( n - 1 ) + ( n - 2 ) + ( n - 3 ) + ... + 2 + 1 = n ( n - 1 ) / 2
که از مرتبه ( Θ( n2 است.
ویژگی‌های مرتب‌سازی انتخابی
1- پیچیدگی زمانی اجرای این الگوریتم بر اساس محاسبات فوق در بدترین حالت ( Θ( n2 است. با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز ( Θ( n2 است.
2- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.
3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.