روش مرتب سازی انتخابی (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
و به این ترتیب لیست مرتب می شود.
منبع مطلب: الگوریتمستان - مرتب‌سازی انتخابی
کد مرتب سازی انتخابی:
#include<iostream.h>
#include<iomanip.h>
int loc=0;
int min(int sort[],int k);
int main()
{
char ch;
do
{
int select[8],k,c,temp;
cout<<"www.softafzar.net\nEnter 8 elements of array to sort:"<<endl;
for (int i=0;i<8;i++)
{
cin>>select[i];
}
cout<<endl;
for(k=0;k<8;k++)
{
c=min(select,k);
temp=0;
temp=select[k];
select[k]=select[loc];
select[loc]=temp;
}
cout<<"array after sort"<<endl;
for ( i=0;i<8;i++)
{
cout<<select[i]<<'\t';
}
cout<<endl;
cout<<"do you want to sort more array? y/n"<<endl;
cin>>ch;
}
while(ch=='y');
return 0;
}
int min(int sort[],int k)
{
int mini;
mini=sort[k];
loc=k;
for(int j=k+1;j<=7;j++)
{
if(mini>sort[j])
{
mini=sort[j];
loc=j;
}
}
return mini;
}