Mediana va uni hisoblash algoritmi Bajardi: Javxanov Dilshod

ymiz. Biz indeks 1 ni tanladik, uning qiymati l[1]=4

[3,4] [5,6]

Biz uchinchi eng kichik elementni xohlaymiz, shuning uchun uning nima ekanligini bilamiz o'ng qatordagi eng kichik element. Endi biz quyidagi massivdagi eng kichik elementni qidiramiz: [5,6]

Ushbu nuqtada bizda indeks asosida eng katta yoki eng kichik elementni tanlaydigan asosiy holat mavjud. Biz eng kichik elementni xohlaymiz, ya'ni 5.

qaytish 5

O'rtacha vaqt ichida medianani topish O(n)

Bizning keyingi qadamimiz, agar omadimiz kelsa, chiziqli vaqt bo'yicha o'rtacha medianani topishdir. Bu “quickselect” deb nomlangan algoritm Toni Xoar tomonidan ishlab chiqilgan bo‘lib, u ham xuddi shunday nomli tezkor saralash algoritmini ixtiro qilgan. Bu rekursiv algoritm va u har qanday elementni (faqat medianani emas) topa oladi.

Keling, ro'yxatning indeksini tanlaymiz. Tanlash usuli muhim emas, amalda u juda mos va tasodifiy. Ushbu indeksdagi elementi (pivot) deb ataladi.

Keling, ro'yxatni ikki guruhga ajratamiz:

Elementlar pivotdan kichik yoki unga teng, lesser_els

Elementlar pivotdan kattaroq, great_els

Biz bilamizki, ushbu guruhlardan biri medianani o'z ichiga oladi. Faraz qilaylik, biz k elementni qidiramiz:

Agar lesser_els ichida k yoki undan ortiq elementlar mavjud boʻlsa, k. elementni qidirib, kamroq lesser_els roʻyxatini rekursiv aylantiring.

Agar lesser_els ichida k elementdan bo'lsa, rekursiv ravishda greater_els ro'yxatidan o'ting. K ni qidirish o'rniga biz k-len (lesser_els) ni qidiramiz.

Keling, quyidagi ro'yxatni olaylik. Biz medianani topmoqchimiz.

l = [9,1,0,2,3,4,6,8,7,10,5]

len(l) == 11, shuning uchun biz oltinchi eng kichik elementni qidiramiz

Avval biz mos yozuvlar elementini (pivot) tanlashimiz kerak. Biz tasodifiy indeks 3 ni tanlaymiz.

Ushbu indeksdagi elementning qiymati 2 ga teng.

Ro'yxatni pivot bo'yicha guruhlarga ajratamiz:

[1,0,2], [9,3,4,6,8,7,10,5]