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

ابتدا کوچک‌ترین عنصر مجموعه اعداد را یافته و با اولین عدد جابه‌جا می‌کنیم. سپس دومین عنصر کوچک‌تر را یافته و با دومین عدد جابه‌جا می‌کنیم و این روند را برای $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]$$

این الگوریتم دارای پیچیدگی زمانی از مرتبه‌ی $\mathcal{O}(n^2)$ است که به همین دلیل اعمال آن روی مجموعه‌ی بزرگی از اعداد کارا به نظر نمی‌رسد و به طور عمومی ضعیف‌تر از مرتب سازی‌های مشابه مثل مرتب سازی درجی عمل می‌کند. این مرتب سازی به دلیل سادگی‌اش قابل توجه‌است. در بهترین حالت از $\mathcal{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;
}

• https://en.wikipedia.org/wiki/Selection_sort