Ma’lumotlar tuzilmasi va algoritmlar” fanidan 4- laboratoriya is hini bajarishga namuna

Algoritm samaradorligi:
Taqqoslashlar soni:
Almashtirishlar soni:

2. Quiksort – tez saralash algoritmi
Bu algoritm “bo'lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo'lib, o'rtacha N*log2N ta solishtirish natijasida saralaydi. Algoritm berilgan massivni saralash uchun uni 2 taga bo'lib oladi. Bo'lib olish uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi. Lekin o'rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma'qul. Tanlangan kalit elementga nisbatan chapdagi va o'ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o'ng tomonga o'tkaziladi (6.3-rasm). Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya'ni bu oraliqlarning o'rtasidagi elementlar kalit sifatida olinadi va h.k.

Q uicksort algoritmi.

Tez saralash - umuman olganda, bu massivlarni tartiblash uchun eng tezkor algoritmlardan biridir, ammo amalda ko'pincha turli xil o'zgartirishlar bilan qo'llaniladi. Bu "bo'linish va zabt etish" tamoyiliga misol.
Algoritmning g'oyasi shundaki, saralash amalga oshiriladigan qo'llab-quvvatlovchi element tanlangan. Teng va kattaroq elementlar o'ngga, kichikroq - chap tomonga joylashtirilgan. Keyin, dastlabki ikki nuqta rekursiv ravishda natijada paydo bo'lgan subarraysiyalarga qo'llaniladi.
Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.
Algoritm uch bosqichdan iborat:

1. 
   Qatordan elementni tanlang. Keling, buni ma'lumotnoma deb ataymiz.
   
2. 
   Bo'linish : elementlarni massivda, ularning oldidan kichikroq elementlar, keyin esa katta yoki teng elementlar joylashtiradigan tarzda tartibga solish.
   
3. 
   Ma'lumotning chap va o'ng tomonidagi ikkita pastki qatorga dastlabki ikki qadamni takroriy ravishda qo'llang. Rekursiya faqat bitta element yoki etishmayotgan elementlar qatoriga taalluqli emas.