2. Saralash masalasini formal qo‘yilishi Ichki saralash usullari: Qat’iy usullar va yaxshilangan usullar

Samaradorlik mezonlari

• 
  saralashga ketgan vaqt (T(n)=C(n)+M(n), bunda C(n) - taqqoslashlar soni; M(n) - esa o‘rinlashtirishlar soni);
  
• 
  dasturni ishlab chiqishga ketgan vaqt;
  
• 
  talab qilinadigan xotira xajmi.
  

• 
  Saralashga ketgan vaqt uchun quyidagi o‘rinli bo‘ladi:
  
• 
  O(nlogn)  T(n)  O(n2);
  
• 
  T(n)=O(n) – ideal holatda.
  

• 
  Ichki saralash usullari
  

• 
  Qat’iy usullar
  

• 
  Yaxshilangan usullar
  

• 
  Qo‘yish orqali saralash
  

• 
  Algoritm g’oyasi
  

• 
  Ob’ektlar hayolan “tayyor” a(1),...,a(i-1) va boshlang‘ich ketma-ketliklarga bo‘linadi. Har bir qadamda (i=2 dan boshlab) boshlang‘ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo‘shiladi.
  

• 
  Misol: Faraz qilaylik, kalit qiymatlari 40,51,8,38,90,14,2,63 bo‘lgan ob’ektlar berilgan bo‘lsin.
  

• 
  - boshlang’ich holat
  

• 
  Qo‘yish orqali saralash algoritmi tahlili
  

• 
  Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
  

• 
  Taqqoslashlar soni:
  

• 
  O‘rinlashtirishlar soni:
  

• 
  Saralashga ketgan vaqt:
  

Qo’yish orqali saralash usuli psevdocodi :

• 
  Qo’yish orqali saralash usuli psevdocodi :
  
• 
  For 1=2 to n
  
• 
  X=a(i)
  
• 
  for j=i-1 downto 1
  
• 
  if x
  
• 
  then a(j+1)=a(j)
  
• 
  Else go to L
  
• 
  endif
  
• 
  Next j
  
•