Сортиране чрез пряка селекция
1. Намиране на минимален елемент на
масив.
2.
Намиране на минимален елемент на масив и неговия индекс.
3. Сортиране на масив по метода на
пряката селекция.
За обяснението на този метод е полезно първо да
разгледаме алгоритъма за намиране а максимален (минимален) елемент на масив.
1. Намиране на минимален
елемент на масив.
Търсенето на минимален елемент се извършва по принципа на последователното
сравняване на всеки от елементите с еталонна стойност. Нейната началната
стойност задължително трябва да е
стойността на един от елементите на масива (обикновено първия). Ако стойността
на текущия елемент е по-голяма от тази стойност, то тя става еталонна. В противен
случай стойността на еталона не се изменя.
Пример:
Даден е
масив от 7 елемента със следните стойности: 10,5,11,2,1,9,7. Търсим елемента с
най-малка стойност. Как процедираме (табл.2)?
1.
В еталона се записва първият
елемент на масива.
2.
Стойността на еталона се
сравнява с втория елемент на масива.
Ако той е по-малък, стойността му се записва в еталона. В противен случай
еталонът остава непроменен. В нашият случай 5<10. Следователно, еталонът
остава същия.
3.
Стойността на еталона се
сравнява с третия елемент на
масива. 11>5, еталонът остава същия.
4.
Стойността на еталона се
сравнява с четвъртия елемент
на масива. 5<2, в еталона се записва 2.
5.
Стойността на еталона се
сравнява с петия елемент на
масива. 1<2, в еталона се записва 1.
6.
Стойността на еталона се
сравнява с шестия елемент на
масива. 9>1, еталонът остава същия.
7.
Стойността на еталона се
сравнява със седмия елемент
на масива. 7>1, еталонът остава
същия.
8.
Масивът е обходен и в еталона е
останала стойността на най-малкият елемент – 1.
Променливата MIN ще съдържа еталона. Типът й трябва да е същия, както
типа на елементите на масива. Преди цикъла в MIN се
записва първият елемент на масива (a[0]).
Цикълът започва обхождането от втория елемент. Блоковата схема на алгоритъма е
показана на фиг.1, а програмата – на листинг 1.
Листинг 1
#
include <iostream.h>
void
main()
{
float
a[100], min;
int n,i;
cout<<"n=";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]=";
cin>>a[i];
}
min=a[0];
for(i=1;i<n;i++)
if(min>a[i]) min=a[i];
cout<<"min"<<min<<"\n";
}
2. Намиране на минимален
елемент на масив и неговия индекс.
Задачата представлява разширение на задачата от точка 1. НОВОТО в нея е, че
дефинираме променлива (Imin), която помни индекса на елемента, записан в
еталона (MIN). Новите блокове са показани със сини рамки.
Блоковата схема на алгоритъма е показана на фиг.2, а програмата – на листинг 2.
Листинг 2
#
include <iostream.h>
void
main()
{
float
a[100], min;
int n,i, Imin;
cout<<"n="; cin>>n;
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]=";
cin>>a[i];
}
min=a[0]; Imin=0;
for(i=1;i<n;i++)
{
if(min>a[i])
{
min=a[i]; Imin=i;
}
}
cout<<"min"<<min<<"\n";
cout<<"Imin"<<Imin<<"\n";
}
3. Сортиране на масив по метода
на пряката селекция.
Сортирането
във възходящ ред (от малка към голяма стойност) може да се опише със следния
алгоритъм:
1)
намира се най-малкият елемент
на масива;
2)
той си разменя мястото с
първият елемент на масива.
Така на
първо място е отсят най-малкият елемент от масива. Тази операция се повтаря с
останалите n-1 елемента, а след това с останалите n-2 елемента и т.н., докато остане
само един елемент – най-големият.
Пример:
Да се
подреди в низходящ ред масива A[4]={10,5,11,2,1,9,7}
Променливата
i следи началото на неподредения
подмасив.
1.
Целият масив е неподреден ® i =0.
a)
Намира се минималният елемент
на масива - A[4]=1.
b)
Първият елемент на неподредения
подмасив (A[0]) и минималният (A[4]) разменят местата си.
Първият елемент вече е на мястото си.
2.
Неподреденият подмасив започва
от втория елемент (i =1).
a)
Намира се минималния елемент на
неподредения подмасив - A[3]=9.
b)
Първият елемент на неподредения
подмасив (A[1]) и минималния (A[3]) разменят местата си.
И вторият елемент вече е на мястото си.
3.
Неподреденият подмасив започва
от третия елемент (i =2).
a)
Намира се минималния елемент на
неподредения подмасив - A[3]=7.
b)
Първият елемент на неподредения
подмасив (A[2]) и минималния (A[3]) разменят местата си.
И третият елемент вече е на мястото си.
4.
Неподреденият подмасив започва
от четвъртия елемент (i =3).
a)
Намира се минималния елемент на
неподредения подмасив - A[6]=5.
b)
Първият елемент на неподредения
подмасив (A[3]) и минималния (A[6]) разменят местата си.
И четвъртият елемент вече е на мястото си.
5.
Неподреденият подмасив започва
от петия елемент (i =4).
a)
Намира се минималния елемент на
неподредения подмасив - A[5]=2.
b)
Първият елемент на неподредения
подмасив (A[4]) и минималния (A[5]) разменят местата си.
И петият елемент вече е на мястото си.
6.
Неподреденият подмасив започва
от шестия елемент (i =5).
a)
Намира се минималния елемент на
неподредения подмасив - A[5]=1. Той е и първия елемент на неподредения подмасив и
размяна не се налага. Но за да се спази принципа се прави размяна на елемента
със самия себе си.
b)
Първият елемент на неподредения
подмасив (A[5]) и минималния (A[5]) разменят местата си.
И шестият елемент вече е на мястото си.
7.
Неподреденият подмасив започва
от седмия елемент (i =6), които е и
последния елемент на масива. След като всички останали елементи са си на мястото,
следва, че и този елемент си е на мястото и масивът е подреден в възходящо ред.
За
програмната реализация на този метод е необходимо да се организират два цикъла.
Във вътрешния цикъл се намира максималния елемент на неподредения подмасив и
неговия индекс. Външен цикъл, в който се следи началото на неподредения
подмасив и се извършва размяната на първия и минималния елемент на неподредения
подмасив. Вътрешния цикъл се изпълнява за стойности на индексната променлива j от i до n-1
(последния елемент на масива). Външния цикъл се изпълнява за стойности на
индексната променлива i от 1 до n-2 (предпоследния
елемент на масива).
Листинг 3
…………….
void sort(float a[100], int n)
{
int
i,j,imin;
float min;
for(i=0;i<n-1;i++)
{
min=a[i];
Imin=I;
for(j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
Imin=j;
}
}
a[Imin]=a[i];
a[i]=min;
}
}
Този
метод в известен смисъл е противоположен на прякото вмъкване. Не се влияе от предварителната наредба на масива. Малко по-бързо е в общия
случай от прякото вмъкване.