Muhammad al-Xorazmiy nomidagi Toshkent axborot texnalogiyalari universiteti

Muhammad al-Xorazmiy nomidagi
Toshkent axborot texnalogiyalari universiteti
Qarshi filiali “Kompyuter injiniringi” Fakulteti
KI-11-21S guruh talabasi Qudratov Shavkat
Ma’lumotlar tuzilmasi va algoritmlar 
2-MUSTAQIL ISH 

Reja; 
1 . Ma’lumotlarni qidirish usullari, algoritmlari va ularning 
samaradorligi. 
2 . Chiziqli qidiruv. Binar qidiruv. Qidirish usullari samaradorligi 
va optimallashtirish. 
3 . Saralash tushunchasi va uning vazifasi. 
Kompyuter va kompleks tizimlarida ma’lumotlarni qayta 
ishlashda qidiruv asosiy va keng foydalanadigan amallardan biri 
hisoblanadi.
QIDIRUV bu ma’lumotlarning orasidan ma’lum bir belgilarga 
mos ma’lumotlarni topish yoki yo’qligini aniqlash jarayonidir. 
Qidiruvning maqsadi - quyidagi jarayonlarning birini 
bajarilishidan iborat: 
topilgan yozuvni oʼqish; 
qidirilayotgan yozuv topilmasa, uni jadvalga qoʼshish; 
topilgan yozuvni oʼchirish. 
Qidiruvni amalga oshirayotganda 3ta xususiyat(atribut)ni 
ajratish mumkin: 
1) Ma’lumotlar majmuasi - bu fayl yoki jadval ko’rinishidagi 
berilgan ma’lumotlar jamlanmasi (to’plami). 
2) Kalit - ixtiyoriy maʼlumot (yoki tuzilma elementi) boshqa 
maʼlumotdan farqlashning biror bir belgisi.
3) Qidiruv mezoni – bu qidirilayotgan kalit belgisi ma’lumotlar 
yozuvlarida moslik sharti. (teng, yaqin, o’xshash va b.) 

Kalit ikki xil boʼlishi mumkin: 
* Birlamchi (takrorlanmaydi, noyob);
* Ikkilamchi (takrorlanadi). 
Kalitlar saqlanishiga nisbatan ichki va tashqi deyiladi. Agar 
kalitlar maʼlumotlar jadvalidan ajratib olinib alohida fayl sifatida 
saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Аks 
holda, yaʼni yozuvning bir maydoni sifatida jadvalda saqlansa 
ichki kalit deyiladi.
CHIZIQLI QIDIRUV
Chiziqli qidiruv tarkibiy qidiruvga misol bo'ladi.
Aytaylik bizga massiv berilgan:
A={1,2,3,4,5,6,7,8,9,10} Bizga ushbu massivda biron bir element 
bor yoki yo'qligini tekshira oladigan algoritm tuzish sharti 
qo'yilgan.Ushbu masalani yechishda eng birinchi hayolga 
keladigan usul - bu massivni ketma-ket har bir elementini 
solishtirib chiqish va bu usul: Chiziqli qidiruv - Linear Search deb 
ataladi.
Algoritm g'oyasi: Ma'lumotlar butun jadval bo'yicha operativ 
xotirada kichik adresdan boshlab, to katta adressgacha ketma-
ket qarab chiqiladi.

BINAR QIDIRUV
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga 
bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi 
elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi 
orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi 
orasidagi massivni oladi, va har safar shu jarayon takrorlanib 
boradi toki x element solishtirilayotgan massivning elementga 
teng bo'lgunicha yoki massivning elementlari qolmaguncha. 
CHIZIQLI VA BINAR QIDIRUV USULLARINING FARQLARI
Funksiyaga berilayotgan massiv Binar qidiruv uchun albatta 
o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa 
berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q.

Chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, 
binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha 
kam solishtirish amali bajariladi.
Chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar 
qidiruvniki ko'pi bilan O(log n).
Elementni qidirishda solishtirish jarayoni ham ikki xil bo’ladi. 
Chiziqli qidirish algoritmi faqat tenglikka asoslanadi. Ikkilik 
qidirish esa tenglik, katta yoki kichiklikka qarab, o’z ishini 
davom ettiradi. 
Chiziqili qidirish algoritmi elementni array boshidan tartib bilan 
qidiradi. Ikkilik qidirish algoritmida esa bu jarayon array 
o’rtasidan boshlanib turlicha davom etishi mumkin.
Dasturlashda bu jarayon tasodifiy elementga murojaat (random 
access) deb ataladi.