Bubble Saralash va Tanlangan Saralash
Bubble sort - qoʻshni elementlar juftlarini solishtirganda qayta-qayta saralanadigan roʻyxat boʻylab oʻtish orqali ishlaydigan saralash algoritmi. Agar juft elementlar noto'g'ri tartibda bo'lsa, ular to'g'ri tartibda joylashtirish uchun almashtiriladi. Bu o'tish boshqa almashtirishlar talab qilinmaguncha takrorlanadi. Tanlovni saralash ham tartiblash algoritmi bo‘lib, u ro‘yxatdagi minimal elementni topib, uni birinchi element bilan almashtirishdan boshlanadi. Bu jarayon almashtirilgan elementlarni tartibda joylashtirish orqali roʻyxatning qolgan qismida takrorlanadi.
Bubble Sort nima?
Bubble sort - qoʻshni elementlar juftlarini solishtirganda qayta-qayta saralanadigan roʻyxat boʻylab oʻtish orqali ishlaydigan saralash algoritmi. Agar juft elementlar noto'g'ri tartibda bo'lsa, ular to'g'ri tartibda joylashtirish uchun almashtiriladi. Ushbu o'tish boshqa almashtirishlar talab qilinmaguncha takrorlanadi (bu ro'yxat tartiblanganligini anglatadi). Roʻyxatdagi kichikroq elementlar pufak yuzaga chiqishi bilan tepaga kelganligi sababli, unga qabariq sort nomi berilgan. Pufakchali tartiblash juda oddiy tartiblash algoritmidir, lekin n elementli roʻyxatni saralashda oʻrtacha ish vaqti murakkabligi O(n2) ga teng. Shu sababli, pufakchali tartiblash ko'p sonli elementlarga ega ro'yxatlarni saralash uchun mos emas. Ammo soddaligi tufayli pufakchali tartiblash algoritmlarga kirish jarayonida o‘rgatiladi.
Tanlash tartibi nima?
Tanlash tartibi ham roʻyxatdagi minimal elementni topish va uni birinchi element bilan almashtirish bilan boshlanadigan yana bir tartiblash algoritmidir. Keyin minimal element ro'yxatning qolgan qismidan topiladi (ikkinchi elementdan ro'yxatning oxirgi elementigacha) va ikkinchi element bilan almashtiriladi. Ushbu jarayon almashtirilgan elementlarni tartibda joylashtirish orqali ro'yxatning qolgan qismi uchun takrorlanadi. Shunday qilib, tanlash tartibida, algoritmning istalgan bosqichida, ro'yxat ikki qismga bo'linadi, ularning bir qismida tartiblangan elementlar, ikkinchi qismida esa tartiblanmagan elementlar mavjud. Algoritm davom etar ekan, tartiblangan ro'yxat chapdan o'ngga o'sadi. Tanlash tartibi ham O(n2) ga teng oʻrtacha ish vaqti murakkabligiga ega. Shuning uchun u katta roʻyxatlarni saralash uchun ham mos emas.
Bubble Saralash va Tanlash Saralash oʻrtasidagi farq nima?
Garchi qabariqni saralash va tanlashni saralash algoritmlarining oʻrtacha ish vaqti murakkabligi O(n2) boʻlsa ham, qabariqli saralash deyarli hamma vaqt tanlovdan ustundir. Bu ikkita algoritm uchun zarur bo'lgan almashtirishlar soniga bog'liq (qabariqli navlar uchun ko'proq almashtirish kerak). Ammo qabariqni tartiblashning soddaligi tufayli uning kod hajmi juda kichik. Barqarorlik bu ikki algoritmning yana bir farqidir. Barqaror saralash algoritmi, agar ro'yxatda teng qiymatga ega elementlar bo'lsa, yozuvlar tartibini saqlaydigan tartiblash algoritmi. Shu ma'noda, tanlash tartibi barqaror algoritm emas, pufakchali tartiblash esa barqaror algoritmdir.
