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


Pufakcha tartiblash algoritmining vaqt murakkabligi


Download 104.22 Kb.
bet3/4
Sana16.06.2023
Hajmi104.22 Kb.
#1518787
1   2   3   4
Bog'liq
Bubble sort

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.


Download 104.22 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling