To’g’ridan-to’g’ri tanlash algoritmining tahlili
C kalitlarni taqqoslashlar soni:
Minimal almashtirishlar soni:
Elementlar tartiblangan bo’lsa va teskari tartibda bo’lsa:
O’rtacha almashtirishlar soni:
Bu yerda - Eyler o’zgarmasi.
Xulosa: To’g’ridan-to’g’ri tanlash usuli to’g’ridan-to’g’ri qo’yish usulidan ustunroq. Lekin agar kalitlar dastlab saralangan bo’lsa, yoki qisman saralangan bo’lsa to’g’ridan-to’g’ri qo’yish usuli sal tezroq bo’ladi.
c. To’g’ridan-to’g’ri almashtirish usuli («Pufakcha» usuli)
To’g’ridan-to’g’ri almashtirish yoki pufakcha usuli – elementlar saralangunga qadar yonma-yon elementlarni saralashlar va almashtirishlar jarayoni. Bu usulda xuddi to’g’ridan-to’g’ri saralash usuli kabi eng kichik element massiv boshiga ko’chiriladi. Agar massivni vertikal ko’rinishda deb tasavvur qilsak, minimal elementlarning tepaga ko’chishi xuddi suvdagi pufakchalarning tepaga ko’tarilishiga o’xshaydi. Shuning uchun ham bu usulni “pufakchali usul” deyish mumkin.
“Pufakcha” usulida saralashning C++ dastrulash tilidagi algoritmiga misol
#define _CRT_SECURE_NO_WARNINGS // scanf()to’g’ri ishlashi uchun
#include
// To’g’ridan-to’g’ri almashtirish uchun funksiya ("pufakcha" usuli)
void bubbleSort(int *num, int size)
{
// barcha elementlar uchun
for (int i = 0; i < size - 1; i++)
{
for (int j = (size - 1); j > i; j--) // i-elementdan keyingi barcha elementlar uchun
{
if (num[j - 1] > num[j]) // joriy element oldingisidan kichik bo’lsa
{
int temp = num[j - 1]; // ularning joyini almashtiramiz
num[j - 1] = num[j];
num[j] = temp;
}
}
}
}
int main()
{
int a[10]; // 10ta elementdan iborat massiv e’lon qilamiz
// massiv elementlarining qiymatlarini kiritamiz
for (int i = 0; i < 10; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
bubbleSort(a, 10); // saralash funksiyasini chaqiramiz
// saralangan massiv elementlarini chiqaramiz
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
}
Natija:
Algoritm tahlili
Taqqoslashlar soni:
O’rin almashtirishlar soni (mos ravishda):
Xulosa: «Almashtirishli saralash» samaradorligi bo’yicha to’g’ridan-to’g’ri tanlash va to’g’ridan-to’g’ri qo’yish usullari o’rtasida desa ham bo’ladi.
| 