• Tanlash orqali saralash algoritmi
  • Pufaksimon saralash algoritmi Ushbu usulning g’oyasi quyidagicha: n - 1
    		•

    Tizimli va amaliy dasturlashtirish




    Download 467,79 Kb.
    Pdf ko'rish
    bet3/5
    Sana06.01.2024
    Hajmi467,79 Kb.
    #131233
    1   2   3   4   5
    Bog'liq
    Aliyev Samandar mta-3

    Algoritm samaradorligi 
    Faraz qilaylik, taqqoslashlar soni C, o’rinlashtirishlar soni M bo’lsin. Agar 
    massiv elementlari kamayish tartibida bo’lsa, u holda taqqoslashlar soni eng katta 
    bo’lib, u ga teng bo’ladi, ya‟ni . O’rinlashtirishlar soni esa ga teng bo’ladi, ya‟ni . Agar 
    berilgan massiv o’sish tartibida saralangan bo’lsa, u holda taqqoslashlar va 
    o’rinlashtirishlar soni eng kichik bo’ladi, ya‟ni , .
    Tanlash orqali saralash algoritmi 
    Mazkur usul quyidagi tamoyillarga asoslangan:
    1. Eng kichik kalitga ega element tanlanadi.
    2. Ushbu element 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
    S= N(N-1)/2=(N
    2
    -N)/2 
    ▪ Massiv tartiblanganda o’rinlashtirishlar soni
    M
    min
    =3(N-1) 
    ▪ Massiv teskari tartiblanganda o’rinlashtirishlar soni
    M
    min
    =M
    min
    N/2=3N(N-1)/2 
    Ushbu usul bo’yicha saralash bajarilsa, eng yomon holda taqqoslashlar va 
    o’rinlashtirishlar soni tartibi n
    2 
    bo’ladi.
    Pufaksimon saralash algoritmi 
    Ushbu usulning g’oyasi quyidagicha: n - 1 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- rasm).
    Misol : massiv - 4, 3, 7, 2, 1, 6.

    5 
    1-rasm. Pufaksimon saralash usulida massivelementlarining o’rnini almashtirish
    Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga 
    o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.
    Taqqoslashlar soni:
    M=(n/2)(n/2)=n
    2
    /4 
    Almashtirishlar soni:
    C
    max
    =3n
    2
    /4 
    2-rasm. Massivni pufaksimon saralashga misol 
    2-rasmda berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda 
    pastdan yuqoriga (yuqoridan pastga) o’tishlar soni 5-1=4 marta bo’ladi. Misoldan 
    ko’rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni “bekor” qayta 
    ishlaydi, 4-qadamni bajarmasa ham bo’ladi.
    Berilgan usullarning afzalligi:
    1) Eng sodda algoritm;
    2) Amalga oshirish sodda;
    3) Qo’shimcha o’zgaruvchilar shart emas.
    Kamchiliklari:
    1) Katta massivlarni uzoq qayta ishlaydi;
    2) Har qanday holatda ham o’tishlar soni kamaymaydi.

    Download 467,79 Kb.
    1   2   3   4   5




    Download 467,79 Kb.
    Pdf ko'rish