Bubble Saralash va Qo'shish tartibi
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. Qo'shish tartibi ham tartiblash algoritmi bo'lib, u kirish ro'yxatidagi elementni allaqachon tartiblangan ro'yxatning to'g'ri joyiga kiritish orqali ishlaydi. Bu jarayon roʻyxat saralanmaguncha qayta-qayta qoʻllaniladi.
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.
Qoʻshish tartibi nima?
Qoʻshish tartibi boshqa saralash algoritmi boʻlib, u kiritilgan roʻyxatdagi elementni roʻyxatning toʻgʻri joyiga (u allaqachon tartiblangan) kiritish orqali ishlaydi. Ushbu jarayon ro'yxat tartiblashtirilgunga qadar takrorlanadi. Kiritilgan saralashda saralash joyida amalga oshiriladi. Shuning uchun algoritmning i-iteratsiyasidan so'ng ro'yxatdagi birinchi i+1 yozuvlari saralanadi, qolganlari esa saralanadi. Har bir iteratsiyada ro'yxatning saralanmagan qismidagi birinchi element olinadi va ro'yxatning tartiblangan qismidagi to'g'ri joyga kiritiladi. Qoʻshish tartibida oʻrtacha ish vaqti murakkabligi O(n2) ga teng. Shu sababli, qo‘shish tartibi katta ro‘yxatlarni saralash uchun ham mos emas.
Bubble Sort va Insertion Sort oʻrtasidagi farq nima?
Koʻpikli saralash ham, qoʻshishni ham saralash algoritmlari oʻrtacha ish vaqti O(n2) murakkabligiga ega boʻlsa-da, pufakchali tartiblash qoʻshish tartibidan deyarli har doim oʻzib ketadi. 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. Bundan tashqari, qo'shilish turining qobiq turi deb ataladigan varianti mavjud bo'lib, vaqt murakkabligi O(n3/2) bo'lib, uni amalda qo'llash imkonini beradi. Bundan tashqari, qoʻshish tartibi pufakchali tartib bilan solishtirganda “deyarli saralangan” roʻyxatlarni saralash uchun juda samarali.
