Mediana va uni hisoblash algoritmi Bajardi: Javxanov Dilshod

Bizga oltinchi element kerak. 6-len (left) = 3, shuning uchun bizga kerak o’ng qatordagi uchinchi eng kichik element. Endi biz quyidagi massivdagi uchinchi eng kichik elementni qidiramiz:

[9,3,4,6,8,7,10,5]

Biz o'zimizning asosiy omilimiz bo'lish uchun tasodifiy indeksni tanlaymiz.

Biz indeks 2 ni tanladik, uning qiymati l[2]=6

Pivot bo'yicha biz guruhlarga ajratamiz:

[3,4,5,6] [9,7,10]

Biz uchinchi eng kichik elementni xohlaymiz, shuning uchun u chap massivdagi uchinchi eng kichik element ekanligini bilamiz

Quickselect bilan medianani topish uchun biz tezkor tanlashni alohida funksiyaga ajratamiz. Quickselect_median funksiyamiz kerakli indekslar bilan quickselectni chaqiradi.

O(n log n) da medianani topish

Medianani topishning eng oddiy usuli bu ro'yxatni tartiblash va indeks bo'yicha medianani tanlashdir. Taqqoslash bo'yicha eng tez tartiblash O(n log n) ni oladi, shuning uchun bajarilish vaqti1, 2 bunga bog'liq.

Bu usul eng oddiy kodga ega, lekin bu, albatta, eng tez emas.

Endi biz quyidagi massivda uchinchi eng kichigini qidirmoqdamiz: