آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی انتخابی»
شهریور ماه ۱۳۸۵
از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان)
منتشر شده بود.
روش مرتب‌سازی انتخابی (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
برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:
| 1 | void
selection_sort(int arr[], int n){
|
| 2 | int i, j, max, temp;
|
| 3 | for(i = n - 1 ; i > 0 ;
i--){
|
| 4 | max = 0;
|
| 5 | for(j = 1 ; j
<= i ; j++)
if(arr[max]
< arr[j])
|
| 6 | max =
j;
|
| 7 | temp = arr[i];
|
| 8 | arr[i] = arr[max];
|
| 9 | arr[max] = temp;
|
| 10 | }
|
| 11 | } |
یک پیاده‌سازی الگوریتم در زبان Python نیز به صورت زیر
است.
| 1 | def selection_sort(arr):
|
| 2 | for i
in range(len(arr) - 1, 0, -1):
|
| 3 |
maxIndex = 0
|
| 4 |
for j in range(1, i + 1):
|
| 5 |
if arr[maxIndex] < arr[j]:
|
| 6 |
maxIndex = j
|
| 7 | arr[i],
arr[maxIndex] = arr[maxIndex], arr[i] |
حلقه‌ی بیرونی حد نصاب پیمایش را مشخص کرده و حلقه‌ی
درونی به ازای هر تکرار حلقه‌ی بیرونی، بزرگترین عنصر لیست نامرتب را می‌یابد. سپس
محل این عنصر با عنصر انتهای بخش نامرتب جابجا می‌شود.
پیچیدگی زمانی مرتب‌سازی انتخابی
[بازگشت به فهرست]
تعداد عناصر لیست را n در نظر می‌گیریم. بر اساس توضیحات
فوق این الگوریتم n - 1 مرحله دارد. در هر مرحله، عنصر ابتدایی در max قرار گرفته و
بقیه‌ی عناصر با آن مقایسه می‌شوند. پس در مرحله‌ی اول تعداد n - 1 مقایسه، در
مرحله‌ی دوم تعداد n - 2 مقایسه و به همین ترتیب در مرحله‌ی iام تعداد n - i مقایسه
صورت می‌گیرد. پس اگر (T(n تعداد کل مقایسه‌ها را نشان دهد، میتوان نوشت:
\[ T(n) = (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 =
\frac{n (n - 1)}{ 2 } \]
که از مرتبه‌ی $\theta(n^2)$ است.
ویژگی‌های مرتب‌سازی انتخابی
[بازگشت به فهرست]
1- پیچیدگی زمانی اجرای این الگوریتم بر اساس محاسبات فوق
در بدترین حالت $\theta(n^2)$ است. با توجه به قطعه کد نوشته شده، ترتیب عناصر
تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب،
نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در
رابطه‌ی فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت
منوسط نیز $\theta(n^2)$ است.
2- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی
عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه‌ی کمکی بزرگ انجام
می‌گیرد.
3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو
عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود.
در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در
روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر
آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.