Malumotlar tuzilmasi va algoritmlar

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYA UNIVERSITETI

Malumotlar tuzilmasi va algoritmlar

MUSTAQIL

ISH

BAJARDI: Norboboyev Mirismoilsoniy
Tekshirdi:Bo’riyev Yusuf
MAVZU:Saralash algaritmlari.Saralashning yaxshilangan usullari.Tez saralash(quicksort)saralash usuli va uni qullanilishiga dastur tuzish.
Saralash – bu berilgan to‘plam elementlarini biror bir tartibda (o‘sish yoki kamayish) joylashtirish jarayonidir.
Saralash (inglizcha sorting - tasniflash, tartiblash) - tanlangan mezonga qarab biror narsani ketma-ket joylashtirish yoki guruhlarga bo'lish.
Saralashdan maqsad - tartiblangan to‘plamda kerakli elementni topishni osonlashtirishdan iborat.
Ma’lumotlarni xajmi va tuzilishiga nisbatan saralash usullari ikkiga ajraladi, ya’ni ichki va tashqi:

• 
  ichki saralash – bu operativ xotiradagi saralash;
  
• 
  tashqi saralash – tashqi xotirada saralash.
  

Saralash – bu berilgan to’plam elementlarini biror bir tartibda joylashtirish jarayonidir. Saralashni maqsadi tartiblangan to’plamda kerakli elementni topishni osonlashtirishdan iborat. Saralash dasturlarni translyasiya qilinayotganda, ma’lumotlar majmuasini tashqi xotirada tashkil qilinayotganda, kutubxonalar, kataloglar, ma’lumotlar bazasi yaratilayotganda tadbiq qilinadi. Ma’lumki, saralashning turli hil algoritmlari mavjud. Sababi, bitta masalani saralash uchun juda ko’plab turli hil algoritmlardan foydalanish mumkin. Berilgan masalani hal qilishda ba’zilari mukammal bo’lishi mumkin. Shuning uchun saralash masalasida algoritmlarni qiyosiy tahlilini o’tkazish zarurati paydo bo’ladi.

Quiksort – tez saralash usuli
Birlashtirish saralash kabi , bo'lish va zabt etish algoritmidir . U elementni pivot sifatida tanlaydi va berilgan massivni tanlangan pivot atrofida ajratadi. QuickSort-ning turli xil yo'llar bilan pivo tanlaydigan ko'plab turli versiyalari mavjud. 

• 
  Har doim birinchi elementni pivot sifatida tanlang.
  
• 
  Har doim oxirgi elementni pivot sifatida tanlang (quyida amalga oshiriladi)
  
• 
  Pivot sifatida tasodifiy elementni tanlang.
  
• 
  Pivot sifatida medianni tanlang.