Ma'lumotlar tuzilmasidagi steklar

Bucket Sort algoritmi

Abstrakt

O'ylab ko'ring, bizga raqamlar qatori berilgan va biz uni saralashni xohlaymiz. Ushbu vazifani bajarish uchun bir qator tartiblash algoritmlari mavjud. Eng yaxshi saralash algoritmi tez tartiblash yoki birlashtirish bo'lishi kerak, chunki ular O(nlog n) ning eng kam vaqt murakkabligini oladi .

Bucket Sort saralashni O(n) vaqt murakkab-ligida tartiblashni amalga oshirishi mumkin bo'lgan yana bir tartiblash algoritmidir , lekin faqat muayyan holatlarda. Keling, qachon va qanday qilib ishlashini ko’raylik.

Mavzu doirasi

• Ushbu maqola mavzuning asosiy kirishidan boshlanadi va keyin algoritmni batafsil tushuntirishni tugatadi.
• Ushbu maqolada Java, Python va C++ tillarida chelaklarni tartiblash algoritmi psevdo kod va haqiqiy kod bilan qanday ishlashi batafsil yoritilgan.
• Ushbu maqolada yoritilgan yana bir muhim jihat - massiv elementlari 0 dan 1 gacha bo'lgan suzuvchi emas, balki butun sonlar bo'lgan holat.
• Oxir-oqibat, ushbu algoritmning vaqt murakkabligi nima uchun va qachon chelakni saralash boshqa saralash usullariga qaraganda yaxshiroq ekanligini tushuntirish uchun batafsil muhokama qilinadi.
• Bucket sort faqat muayyan holatlarda qo'llanilishi mumkin. Bular ilovalarning kichik mavzusida muhokama qilinadi.

Olib ketishlar

• Chelaklarni saralash juda tez bo'lishi mumkin, chunki elementlar chelaklarga tayinlanadi, odatda indeks qiymat bo'lgan massivdan foydalanadi.

Kirish

• Saralash haqida gap ketganda, biz pufakchali tartiblash, tezkor saralash, birlashtirish va hokazolarni o'ylaymiz, chunki ular eng ko'p ishlatiladigan saralash algoritmlaridan biridir. Ularning barchasi bir nuqtada yakuniy maqsadga erishish uchun har ikki raqam o'rtasida haqiqiy taqqoslashni amalga oshiradi, ya'ni tartiblangan massiv. Taqqoslash uchun, chelaklarni saralash biroz boshqacha ishlaydi.
• U bir xil taqsimlangan ma'lumotlar ustida ishlaydi (quyida tushuntirilgan) va tartiblangan massivni shakllantirish uchun ularni saralash va yig'ish uchun raqamlarni chelaklarga joylashtiradi.
• An'anaviy tartiblash algoritmlari O(nlogn) ning eng yaxshi vaqt murakkabligiga erishishi mumkin bo'lsa-da , Paqir tartiblash O(n) da ham xuddi shunday qilishi mumkin .