O(n log n) da medianani topish

6. K sonlarning S to'plami uchun x ning ma'nosi “rank" bo'lsin, x S dagi eng kichik sondir.

7a. Agar i = k bo'lsa, x ni qaytaring.

7b. Agar i

7c. Agar i >k bo'lsa, (A[k+1,…, i ], i-k) bo'yicha median-of−medians algoritmidan foydalanib qaytadan yozing.

 

Imtihon ballari A ro'yxatidagi uchinchi eng past ballni topish uchun median-of-medians algoritmining bosqichlarini ko'rsating.

Izoh: ushbu algoritmning ba'zi tatbiqlari, xuddi quyidagi algoritm kabi, nol indekslangan, ya'ni eng past ball ro'yxatdagi eng past ball bo'ladi. Ushbu misolda nol indekslashdan foydalaning-shuning uchun uchinchi eng past ball bo'ladi tartiblangan ro'yxatda chap element.

A=[25,21,98,100,76,22,43,60,89,87]

Birinchidan, biz ro'yxatni beshta element ro'yxatiga ajratamiz:

=[25,21,98,100,76] va =[22,43,60,89,87]

Keyin, har bir ro'yxatdan medianni oling va ularni M medianlar ro'yxatiga qo'ying,

M=[76,60].

 

Ushbu ro'yxatdan medianani tanlang-chunki ro'yxat uzunligi 2 ga teng va biz median indeksini ro'yxat uzunligi bo'yicha ikkiga bo'linishini aniqlaymiz: biz 2/2=1, median indeksi 1 ga teng va M[1] = 76. Buni burilish elementi sifatida foydalaning va chapga 76 dan kichik va o'ngga 76 dan katta bo'lgan barcha elementlarni AA ga qo'ying:

A’=[25,22,43,60,21,76,100,89,87,98].

76 bo'lgan 5 ning indeksini toping. 5 bilan 3 qanday taqqoslanadi? 5 > 3,5 > 3 bo'lgani uchun [25,22,43,60,21][25,22,43,60,21] bo'lgan a',a' ro'yxatning chap yarmida qaytadan yozishimiz kerak.

Ushbu ro'yxat faqat beshta elementdan iborat, shuning uchun biz uni tartiblashimiz va 3-indeksda nima borligini topishimiz mumkin: [21,22,25,43,60][21,22,25,43,60] va 43 uchinchi indeksda.

Demak, 43-A ning to'rtinchi eng kichik soni.

Endi biz quyidagi massivda uchinchi eng kichigini qidirmoqdamiz:

[3,4,5,6] Biz o'zimizning asosiy omilimiz bo'lish uchun tasodifiy indeksni tanla

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