Tatu samarqand filiali

3.1.  Tuzilma elementlarini saralash  

Ma’lumotlarni  kompyuterda  qayta  ishlashda  elementning  informatsion 

maydoni  va  uning  mashina  xotirasida  joylashishini  bilish  zarur.  Shu  

maqsadda ma’lumotlarni  saralash  amalga  oshiriladi.  Demak,  saralash  –  bu  

ma’lumotlarni kalitlari  bo’yicha  doimiy  ko’rinishda  mashina  xotirasida  

joylashtirishdan  iborat. Bu  yerda  doimiylik  ma’lumotlarni  massivda  kalitlari  

bo’yicha  o’sishi  tartibida berilishi tushuniladi. Ma’lumotlarga  qayta  ishlov  

berilayotganda  ma’lumotning  informatsion maydonini hamda uning mashinada 

joylashishini (adresini) bilish zarur.  

Saralashning ikkita turi mavjud: ichki va tashqi:  

 

– tashqi xotirada saralash.  

Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni 

almashtirishlar katta sarf (vaqt va xotira  ma’nosida)  talab  qiladi.  Ushbu  sarfni 

kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda 

faqatgina ma’lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi. Bu usul 

adreslar jadvalini saralash usuli deyiladi.  

---

Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin 

bir xil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, shu tartibda 

qoldirilishi  maqsadga  muvofiq  bo’ladi  (Bir  xil  kalitlilar  o’zlariga  nisbatan). 

Bunday usulga turg’un saralash deyiladi.  Saralash samaradorligini bir necha 

mezonlar bo’yicha baholash mumkin:  

 

 

 

Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki 

almashtirishlar sonini hisoblash mumkin. Faraz  qilaylik,  N  =  0,01n2  +  10n  –  

taqqoslashlar  soni.  Agar  n  <  1000  bo’lsa, u  holda  ikkinchi  qo’shiluvchi  katta,  

aks  holda  ya’ni,  n  >  1000  bo’lsa,  birinchi qo’shiluvchi katta bo’ladi.  Demak, 

kichkina n larda taqqoslashlar soni n ga teng bo’ladi,  katta n larda  esa n2 ga teng 

bo’ladi.   

Saralashda taqqoslashlar soni quyidagi oraliqlarda bo’ladi:  

– ideal holatda.  

Saralashning quyidagicha usullari bor:  

iy (to’g’ridan-to’g’ri) usullar;  

 

Qat’iy usullarning afzalliklarini ko’rib chiqaylik:  

1.  Bilamizki,  dasturlarning  o’zlari  ham  xotirada  joy  egallaydi.  To’g’ridan-  

to’g’ri saralash usullarining dasturlari qisqa bo’lib, ular tushunishga oson.   

2. To’g’ridan-to’g’ri saralash usullari orqali saralash tamoyillarining asosiy  

xususiyatlarini tushuntirish qulay.  

3.  Murakkablashtirilgan  usullarda  uncha  ko’p  amallarni  bajarish  talab 

qilinmasada, ushbu amallarning o’zlari ham ancha murakkabdir. Garchi yetarlicha  

katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar  

tezroq ishlaydi.  

Shu  joyni  o’zida  qat’iy  usullarni  ishlash  tamoyillariga  ko’ra  3  ta  toifaga  

bo’lish mumkin:  

---

1. To’g’ridan-to’g’ri qo’shish usuli (by insertion);   

2. To’g’ridan-to’g’ri tanlash usuli (by selection);   

3. To’g’ridan-to’g’ri almashtirish usuli (by exchange).  

6.2.  To’g’ridan-to’g’ri qo’shish usuli bilan saralash algoritmi  

  

Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartalar) hayolan 

“tayyor”  a(1),...,a(i-1)  va  boshlang’ich  ketma-ketliklarga  bo’linadi.  Har  bir 

qadamda  (i=2  dan  boshlanib,  har  bir  qadamda  bir  birlikka  oshirib  boriladi) 

boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning 

kerakli joyiga qo’yiladi.  

To’g’ridan-to’g’ri qo’shish orqali saralash algoritmi quyidagicha bo’ladi:  

                 for (int i=1;i

                  x=a[i];  

                  x ni a[0]...a[i] oraliqning mos joyiga qo‘shish  

                 }  

Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. 2-

elementdan  boshlab  har  bir  elementni  qarab  chiqamiz,  ya’ni  har  bir  element 

o’zidan oldin turgan element bilan solishtiriladi. Agar qaralayotgan element kichik 

bo’lsa,  oldinda  turgan  element  bilan  o’rin  almashadi  va  yana  o’zidan  oldinda 

turgan  element  bilan  solishtiriladi,  jarayon  shu  kabi  davom  etadi.  Bu  jarayon 

quyidagi shartlarning birortasi bajarilganda to’xtatiladi:  

1. x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda.  

2. x elementi oldida element qolmaganda.  

for (int i=1;i

  int j=i;  

      while(a[j]

            int t=a[j-1];  

            a[j-1]=a[j];  

            a[j]=t;  

            j=j-1;  

---

      }  

  }  

  

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 (

^2)

O’rinlashtirishlar  soni  esa 

xam3(1)    ga    teng    bo’ladi,    ya’ni    O(

^2)

Agar    berilgan    massiv  

o’sish tartibida  saralangan  bo’lsa,  u  holda  taqqoslashlar  va   o’rinlashtirishlar  

soni  eng kichik bo’ladi, ya’ni Cmin = 

=3