Javoblar 86. Хасис алгоритм қачон қўлланилади?

Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:
1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element a0 birinchi element bilan o’rin almashinadi.
3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to
bitta eng “katta” element qolguncha davom ettiriladi.
for(int i=0;i
for(int j=i+1;j
if (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}
Algoritm samaradorligi:
-Taqqoslashlar soni
-Massiv tartiblanganda o’rinlashtirishlar soni
-Massiv teskari tartiblanganda o’rinlashtirishlar soni
Ushbu usul bo’yicha saralash bajarilsa, eng yomon holda taqqoslashlar va
o’rinlashtirishlar soni tartibi n^2 bo’ladi
“Pufaksimon” usulni yaxshilash

Ushbu usulning g„oyasi quyidagicha: marta massivda quyidan yuqoriga
qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati
yuqoridagi jufti kalitidan kichik bo„lsa, u holda ularning o„rni almashtiriladi
1) Agar massivda o’tishlar nafaqat yuqoridan pastga, balki bir vaqtning o’zida
pastdan yuqoriga ham bo’lsa, u holda “yengil” elementlar “yuqoriga suzib” chiqadi
va “og’ir” elementlar esa “cho’kadi”.
2) Massivda “bekor” o’tishni yo’q qilish uchun, tashqi siklda massiv
saralanganligini tekshiruvchi belgi qo’yish lozim.
for (int i=0;i
for (int j=n-1;j>i;j--)
if (a[j] < a[j - 1]){
int x= a[j - 1];
a[j - 1] = a[j];
a[j] = x; }
O’rinlashtirish va taqqoslashlar soni: (n* log( n )).

Masalaning qo’yilishi – tabalarning ism, familiyalarini optimallashtirilgan pufaksimon usuli bilan tartibga keltirish dasturini tuzamiz va saralash nechta o’rin almashtirish bilan amalga oshirilganini aniqlaymiz.

Algoritm
1. Jadvalga talabalar ism-sharifini kiritamiz.
2. Jadvaldagi 1-elementni olamiz, i=0.
3. Jadvaldagi n-1 oxirgi elementdan to i-elementgacha barcha elementni FIO
maydonini o’zidan oldin turgan element FIO maydoni bilan solishtiramiz.
Agar zarur bo’lsa, o’rin almashtiramiz va o’rin almashtirishlar hisoblagichi l
ning qiymatini bittaga oshiramiz, ya’ni l++.
4. Agar i
5. Natijaviy saralangan massivni ekranga chiqaramiz.
Dastur kodi
#include
#include
using namespace std;
int main(int args, char *argv[])
{
int n; cout<<"talabalar sonini kiriting=";cin>>n;
struct table{
int t;
char FIO[20];
} talaba[n];
cout<
for(int i=0;i
talaba[i].t=i+1;
cin>>talaba[i].FIO;
}
int l=0;
for(int i=0;i
for(int j=n-1;j>i;j--){
if (strcmp(talaba[j-1].FIO,talaba[j].FIO)==1){
l++;
table k=talaba[j];
talaba[j]=talaba[j-1];
talaba[j-1]=k;
}
}
}
for(int i=0;i
cout<<"| "<
cout<<"bu algoritm jadvalni "<
saraladi\n";
system("PAUSE");
}
Dastur natijasi:
talabalar sonini kiriting=5
5 ta talabalar FIO sini kiriting
Farhod
Asror
Sobir
Bobur
Vali
| 2 | Asror |
| 4 | Bobur |
| 1 | Farhod |
| 3 | Sobir |
| 5 | Vali |
bu algoritm jadvalni 10 ta solishtirishda saraladi.