Mustaqil ish mavzu: Bubble sort algoritmi. Bajardi: Allayarov Tohirjon

Pufakcha tartiblash algoritmining vaqt murakkabligi

• 
  Bubble sort ikkita halqadan foydalanadi: ichki halqa va tashqi halqa.
  
• 
  Ichki pastadir O(n) taqqoslashlarini deterministik tarzda amalga oshiradi.
  

Eng yomon holat

• 
  Eng yomon stsenariyda tashqi tsikl O(n) marta ishlaydi.
  
• 
  Natijada, qabariqni saralashning eng yomon vaqt murakkabligi O(nxn) = O(nxn) (n2).
  

Eng yaxshi holat

• 
  Eng yaxshi stsenariyda massiv allaqachon tartiblangan, ammo har qanday holatda qabariqli tartiblash O(n) taqqoslashni amalga oshiradi.
  
• 
  Natijada, eng yaxshi stsenariyda pufakchani tartiblashning vaqt murakkabligi O(n) dir.
  

Oʻrtacha holat

• 
  Pufakchali saralash oʻrtacha holatda har bir oʻtish uchun (n/2) pas va O(n) taqqoslashni talab qilishi mumkin.
  
• 
  Natijada, qabariqni saralashning o'rtacha ish vaqti murakkabligi O(n/2 xn) = O(n/2 xn) = O(n/2 xn) = O(n/2 xn) = O (n2).
  

Pufakcha tartiblash algoritmining fazoviy murakkabligi

• 
  Pufakcha tartiblash uchun bayroq, i va oʻlcham oʻzgaruvchilari uchun faqat belgilangan miqdorda qoʻshimcha joy kerak boʻladi.
  
• 
  Natijada, qabariq navining fazoviy murakkabligi O. (1).
  
• 
  Bu berilgan massivni saralash uchun asl massivning elementlarini o'zgartiradigan joyida tartiblash algoritmi.
  

Ushbu qo'llanmada siz qabariq turining ba'zi afzalliklari va kamchiliklarini ko'rasiz.
Bubble Sort algoritmining afzalliklari

• 
  Massiv yoki ro'yxat egallagan xotiradan tashqari, pufakchani tartiblash juda kam xotira talab qiladi.
  
• 
  Pufakcha tartiblash faqat bir necha qator kodlardan iborat. 
  
• 
  Eng yaxshi ish vaqti murakkabligi O(n) bilan pufakchali tartiblash roʻyxatning tartiblangan yoki saralanmaganligini aniqlashda yordam beradi. Boshqa saralash usullari ko'pincha butun saralash ketma-ketligi bo'ylab aylanishadi, yakunlash uchun O(n2) yoki O(n log n) vaqt kerak bo'ladi.
  
• 
  Xuddi shu narsa bir necha marta almashtirilishi kerak bo'lgan bir nechta elementlarga ega ma'lumotlar to'plamlari uchun ham amal qiladi.