Ikki mezon bo’yicha saralash

Ko’pincha elementlarni bitta emas, ikkita mezon bo’yicha saralash kerak bo’ladi. Masalan, musobaqa reytingi: ishtirokchilar avval yechgan masalalar soni bo’yicha (ko’pdan kamga), agar bu ko’rsatkich teng bo’lsa — sarflangan vaqt bo’yicha (kamdan ko’pga) tartiblanadi.

Bunday holatda oddiy sort() yetarli emas — maxsus solishtiruvchi funksiya (comparator) kerak bo’ladi:

C++ da Comparator yozilishi

bool cmp(int a, int b) {
    if (s[a] != s[b]) 
        return s[a] > s[b];   // ko'proq masala yechgan — oldinda
    if (p[a] != p[b]) 
        return p[a] < p[b];   // kam vaqt sarflagan — oldinda
    return a < b;             // ikkalasi teng — tartib raqami bo'yicha
}

sort(idx + 1, idx + n + 1, cmp);

Qoida oddiy: avval birinchi mezon solishtiriladi; teng chiqsa — ikkinchisiga o’tiladi; u ham teng chiqsa — uchinchisiga... Shu zanjir bilan istalgancha mezon bo’yicha saralash qurish mumkin.

Tezligini baholash

cmp funksiyasining o’zi O(1) — faqat bir nechta son solishtiradi. sort() esa n ta elementni O(n log n) vaqtda saralaydi. Demak, umumiy murakkablik: O(n * log n)

n = 10^5 uchun bu ≈ 1.7×10^6 ta amal — millisekundlar ichida bajariladi, necha mezon qo’shilishidan qat’iy nazar tezlik deyarli o’zgarmaydi.

#samcoding #algorithm #sorting