Mavzu: Saralash algoritmlarining samaradorligi va qiyosiy tahlili. Misolda namoyish

Saralanmagan roʻyxatda kerakli yozuvni qidirish butun roʻyxatni yozuv topilgunga qadar koʻrib chiqishga olib keladi. Bu qidirish algoritmlarining oddiy koʻrinishi. Koʻrishimiz mumkin bu algoritm uncha samarador emas, lekin u ixtiyoriy roʻyxatda ishlaydi.

• Saralanmagan roʻyxatda kerakli yozuvni qidirish butun roʻyxatni yozuv topilgunga qadar koʻrib chiqishga olib keladi. Bu qidirish algoritmlarining oddiy koʻrinishi. Koʻrishimiz mumkin bu algoritm uncha samarador emas, lekin u ixtiyoriy roʻyxatda ishlaydi.
• Saralangan roʻyxatda ikkilik qidirishdan foydalanish mumkin. Ikkilik qidirish tartiblanganlikka koʻra bir solishtirishda birdan ortiq elementlarni tashlab yuborishga asoslangan. Natijada qidirish samarador boʻladi

Odatda qidirish nafaqat kerakli elementni roʻyxatda bor yoʻqligini aniqlash uchun, balki topilgan kalit qiymatiga bogʻliq ma’lumotlarni olish uchun xizmat qiladi. Masalan, kalit qiymat xodimning raqami yoki tartib raqami yoxud boshqa istalgan yagona identifikator boʻlishi mumkin. Kerakli kalit topilgandan soʻng, dastur unga bogʻlangan ma’lumotlarni oʻzgartirishi mumkin yoki butun yozuvni chiqarishi mumkin. Oxir oqibatda qidirish algoritmi oldida muhim vazifa kalitning oʻrnini topish masalasi turadi. Shuning uchun qidirish algoritmlari kerakli kalitni saqlovchi yozuv indeksini beradi. Agar kalit qiymat topilmasa, u holda qidirish algoritmi massiv yuqori chegarasidan chiquvchi indeks qiymatini beradi. Maqsadimiz uchun faraz qilamizki, roʻyxat elementlari 1 dan N gacha raqamlangan. Bu agar maqsad elementi topilmasa 0 ni berishga imkon beradi. Oddiylik uchun kalit qiymat takrorlanmaydi deb faraz qilamiz.

• Odatda qidirish nafaqat kerakli elementni roʻyxatda bor yoʻqligini aniqlash uchun, balki topilgan kalit qiymatiga bogʻliq ma’lumotlarni olish uchun xizmat qiladi. Masalan, kalit qiymat xodimning raqami yoki tartib raqami yoxud boshqa istalgan yagona identifikator boʻlishi mumkin. Kerakli kalit topilgandan soʻng, dastur unga bogʻlangan ma’lumotlarni oʻzgartirishi mumkin yoki butun yozuvni chiqarishi mumkin. Oxir oqibatda qidirish algoritmi oldida muhim vazifa kalitning oʻrnini topish masalasi turadi. Shuning uchun qidirish algoritmlari kerakli kalitni saqlovchi yozuv indeksini beradi. Agar kalit qiymat topilmasa, u holda qidirish algoritmi massiv yuqori chegarasidan chiquvchi indeks qiymatini beradi. Maqsadimiz uchun faraz qilamizki, roʻyxat elementlari 1 dan N gacha raqamlangan. Bu agar maqsad elementi topilmasa 0 ni berishga imkon beradi. Oddiylik uchun kalit qiymat takrorlanmaydi deb faraz qilamiz.