Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

4-qism. Bog’langan ro’yxatlar va saralash 
Ushbu mavzuda eng mashhur saralash algoritmlari: pufaksimon saralash, 
tezkor  saralash  va  birlashtirish  orqali  saralash  algoritmlari  o’rganiladi. 
Mavzuning  oxirida  ushbu  uchta  algoritmning  ishlashi  bo’yicha  unumdorligini 
testlash masalasi qarab chiqilgan.  
 
4.1. Saralash usullari 
Saralash  –  bu  ma’lum  bir  to’plam  ob’ektlarini  aniq  bir  tartibda  qayta 
joylashtirish  jarayoni  bo’lib,  saralashdan  asosiy  maqsad  elementni  qidirishni 
osonlashtirishdan iborat. Saralash uchun ko’plab algoritmlar qo’llaniladi, shuning 
uchun  ham  aniq  bir  masalani  yechishda  optimal  algoritmni  tanlab  olish  uchun 
qo’llaniladigan  saralash  algoritmlarini  qiyosiy  tahlil  qilib  chiqishimiz  kerak 
bo’ladi.  
Saralash  usullari  odatda  ikkita  guruhga  ajratiladi:  massivda  saralash  va 
faylda  saralash.  Odatda  bu  saralash  usullari  ichki  saralash  va  tashqi  saralash 
algoritmlari deb ham ataladi. Ya’ni massiv bu komp’yuterning ichki xotirasida, 
fayl esa tashqi xotirada joylashadi. Massivda va bog’langan ro’yxatlarda saralash 
algoritmlariga qo’yiladigan eng muhim talablardan biri – bu xotira sarfini tejash 
hisoblanadi.  Shuning  uchun  ham  saralash  uchun  qo’shimcha  massivdan 
foydalanish axmoqano ish hisoblanadi.  
Saralash  algoritmlarini  klassifikatsiya  qilishning  asosiy  kriteriyasi  uning 
tezkorligi bilan belgilanadi. Saralashda ikki turdagi amal bajariladi. Bu amallar 
kalitlarni taqqoslash va elementlar o’rnini almashtirish (bog’langan ro’yxatlarda 
ko’rsatkichlarni qayta joylashtirish) amallari. Agar massivda n ta element bo’lsa, 
u holda  elementlarning  o’rnini almashtirish  massiv  elementlari  soni  n  va  uning 
logarifmi  log(n)  ga  ko’paytmasiga  teng  bo’lsa  saralash  uchun  qo’llanilgan 
algoritm  eng  yaxshi  deb  hisoblanadi.  Masalan,  standart  pufaksimon  saralash 
algoritmida  n  ning  kvadratiga  teng  bo’lgan  sondagi  o’rin  almashtirishlar  talab 
etiladi. 

---

56 
 
Saralash usullarini asosan