11-ma’ruza. Bir va ikki o‘lchovli massiv elementlarini tartiblash, qidirish algoritmlari va ularning murakkabligini tahlil qilish asosida dastur yaratish Massivni saralash

11-ma’ruza. Bir va ikki o‘lchovli massiv elementlarini tartiblash, qidirish algoritmlari va ularning murakkabligini tahlil qilish asosida dastur yaratish
Massivni saralash - bu massivdagi barcha elementlarni ma'lum tartibda joylashtirish jarayoni. Bu ko'pincha foydalidir. Masalan, pochta qutingizdagi elektron pochta xabarlari qabul qilingan vaqtga qarab ko'rsatiladi; yangi elektron pochta xabarlari sizga yarim soat, bir soat, ikki yoki bir kun oldin kelgan elektron pochta xabarlariga qaraganda ko'proq zarur; kontaktlar ro'yxatiga kirganingizda, ismlar odatda alifbo tartibida bo'ladi, chunki shu tarzda biror narsani topish osonroq. Ushbu holatlarning barchasi ma'lumotlarni namoyish qilishdan oldin ularni saralashni o'z ichiga oladi.
Saralash qanday ishlaydi?
Ma'lumotlarni saralash nafaqat odamlar uchun, balki kompyuterlar uchun ham massiv ichidan qidirishni samaraliroq qilishi mumkin. Masalan, ismlar ro'yxatida ma'lum bir ism mavjud bo'lishini bilishimiz kerak bo'lgan holatni ko'rib chiqaylik. Buni bilish uchun siz massivning har bir elementini berilgan qiymat bilan tekshirishingiz kerak. Ko'p elementli qatorni qidirish juda samarasiz (murakkab) bo'lishi mumkin.
Biroq, nomlarimiz qatori alfavit bo'yicha tartiblangan deb taxmin qiling. Shunda qidiruvni birinchi harfi bilan tekshirsak, ancha osonlashadi. Bunday holda, agar biz ushbu harfga yetib borsak va ismini topa olmasak, unda biz bu qatorning qolgan qismida yo'qligini aniq bilamiz, chunki biz allaqachon o'z harfimizni alifbo tartibida saralab olganmiz.
Tartiblangan massivlar ichida yanada yaxshi qidirish algoritmlari mavjud. Oddiy algoritmdan foydalanib, faqat 20 ta taqqoslash yordamida aniqlangan elementni 1 000 000 ta elementlardan iborat tartibda qidirishimiz mumkin! Yomon tomoni shundaki, massivni juda ko'p sonli elementlarga ko'ra saralash nisbatan murakkab jarayon va bitta qidiruv so'rovi uchun amalga oshirilmaydi.
Ba'zi hollarda, qatorni saralash qidirishni keraksiz holga keltiradi. Masalan, biz talabalar orasida eng yaxshi test balini qidirmoqdamiz. Agar massiv saralanmagan bo'lsa, unda biz eng yuqori ballni topish uchun massivning har bir elementini tekshirishimiz kerak bo'ladi. Agar massiv saralangan bo'lsa, unda eng yuqori ball birinchi pozitsiyada yoki oxirgisi bo'ladi (massivni saralash turiga qarab: pastdan yuqoriga yoki yuqoridan pastga), shuning uchun endi qidirishning umuman hojati qolmaydi.

Saralash usullari