فهرست مندرجات

مرتب سازی انتخابی

تعریف

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

الگوریتم

ابتدا کوچک‌ترین عنصر مجموعه اعداد را یافته با اولین عدد جابه‌جا می‌کنیم. سپس دومین عنصر کوچک‌تر را یافته با دومین عدد جابه‌جا می‌کنیم و این روند را برای n-1 عدد اول تکرار می‌کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می‌کنیم. زیر لیست اول که قبلاً مرتب کرده‌ایم و سایر اعضای لیست که هنوز مرتب نشده‌است. در جدول زیر مثالی از پیاده‌سازی این روال بر روی 5 عدد آمده‌است.

[55 24 36 11 7]

[7 24 36 11 55]

[7 11 36 24 55]

[7 11 24 36 55]

[7 11 24 36 55]

پیچیدگی‌ الگوریتم

این الگوریتم دارای پیچیدگی زمانی از مرتبه‌ی $O(n^2)$ است که به همین دلیل اعمال آن روی مجموعه‌ی بزرگی از اعداد کارا به نظر نمی‌رسدو به طور عمومی ضعیف تر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند. این مرتب‌سازی به دلیل سادگی‌اش قابل توجه‌است. در بهترین حالت از $O(n^2)$ است .

پیاده‌سازی اولیه

Selection_Sort.cpp
#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxn=1000+100;
int n,a[maxn];
 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n-1;i++){
        int imin=i;
        for(int j=i+1;j<=n;j++)
            if(a[j]<a[imin])
                imin=j;
        swap(a[i],a[imin]);
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
 
    return 0;
}