Таңдау әдісімен сұрыптау алгоритмін сипаттаңыз

Сұрыптау (Сортировка; sorting) - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеупроцессін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағы басқа. Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.

Таңдау арқылы сұрыптау (Сортировка выбором; Selection Sort) - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы n элементтен тұратын А сандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет.

Таңдау арқылы сұрыптау алгоритмінің күрделілігі .

Бұл алгоритмді түсіну оңай, қолдану қарапайым. Дегенмен, бұл алгоритмнің жағымсыз бірқатар қасиеттері бар. Алгоритмдегі цикл берілген массивтің ұзындығына пропорционалды өсе береді. Сонымен қоса, егер сіз бұл алгоритмге сұрыпталған массив берсеңіз де сол циклдар орындала береді, өйткені бұл алгоритмде массивтің барлық элементі туралы ақпарат жоқ.

Алгоритмі:

1. Өлшемі n болатын А массивін толтыру және экранға шығару;

2. i:=1;

3. Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;

4. A[i] және A[j] элементтерінің орындарын ауыстыру;

5. i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;

6. Сұрыпталған А массивін экранға шығару.

Программасы:

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,a[50],i,j,min,k;
cin»n;
for(i=0;i<n;i++)
cin»a[i];
for(j=0;j<n-1;j++)
{
min=a[j];
for(i=j;i<n;i++)
if(a[i]<min)
{
min=a[i];

k=i;
}
swap(a[j],a[k]);
}
for(i=0;i<n;i++)
cout«a[i]«" ";
cout«endl;
return 0;
}