O(n log n) da medianani topish

Amalda medianani topish algoritmlari kutilgan chiziqli ishlash vaqtiga ega bo'lgan tasodifiy algoritmlar bilan amalga oshiriladi. Biroq, ushbu Viki median-of-medians algoritmiga qaratiladi, bu chiziqli vaqtda ishlaydigan deterministik algoritmdir.

 

Median-of-medians algoritmi deterministik chiziqli vaqtni tanlash algoritmidir. Algoritm ro'yxatni sublistlarga bo'lish orqali ishlaydi va keyin sublistlarning har birida taxminiy mediani aniqlaydi. Keyin, bu medianalarni oladi va ularni ro'yxatga kiritadi va ushbu ro'yxatning medianasini topadi. U ushbu o'rtacha qiymatdan burilish sifatida foydalanadi va ro'yxatning boshqa elementlarini pivot bilan taqqoslaydi. Agar element pivot qiymatidan kam bo'lsa, element pivotning chap tomoniga, agar element pivotdan katta qiymatga ega bo'lsa, u o'ng tomonga joylashtiriladi.

Algoritm ro'yxatda takrorlanib, u izlayotgan qiymatga ega. Algoritm ro'yxat va indeks - median-of-median(A, i) ni oladi. A ning barcha elementlari alohida deb taxmin qiling (garchi algoritm takroriy elementlarga imkon berish uchun yanada umumlashtirilishi mumkin).

• Ro'yxatni har biri beshinchi uzunlikdagi sublistlarga bo'ling (agar oxirgi ro'yxat uchun beshdan kam element mavjud bo'lsa, bu yaxshi).
• Har bir sublistni tartiblang va medianni aniqlang. Juda kichik ro'yxatlarni saralash chiziqli vaqtni oladi, chunki bu sublistlar beshta elementga ega va bu oladi O(n) vaqt. Ushbu sahifada tasvirlangan algoritmda, agar ro'yxat juft sonli elementlarga ega bo'lsa, median indeksini topish uchun ro'yxat uzunligining 2 ga bo'linishini oling.
• Barcha medianlar to'plamining medianasini rekursiv ravishda aniqlash uchun median-of-median algoritmidan foydalaning.
• Markaz element sifatida bu median foydalaning, x. Markaz butun ro'yxatning taxminiy media va keyin har bir recursive qadam haqiqiy median kuni.
• A ni shunday tartiblangki, x dan kichik bo'lgan barcha elementlar x ning chap tomonida, A ning x dan katta bo'lgan barcha elementlari o'ng tomonda. Bunga bo'linish deyiladi. Ular x ikki tomonida joylashtirilgan bir marta elementlar hech alohida tartibda bo'ladi.masalan, x bo'lsa 5, x o'ng ro'yxati balki kabi qarash [8,7,12,6][8,7,12,6] (ya'ni emas tartiblangan tartibda). Beri bu chiziqli vaqtni oladi O(n) taqqoslashlar sodir bo'ladi—A dagi har bir element faqat x bilan taqqoslanadi.