Reja: Massiv elementlarini saralash va qidiruv algoritmlari

Massiv elementlarini saralash algoritmlari, qidiruv algoritmlari
Reja:

1. 
   Massiv elementlarini saralash va qidiruv algoritmlari
   
2. 
   Chiziqli saralash (tanlov bo‘yicha saralash)
   

Qidiruv algoritmlari

Dasturlashda eng ko‘p qo‘llaniladigan amallardan biri bu – ma’lumotlarni qidirishdir. Qidiruv masalasini hal etishga mo‘ljallangan algoritmga qidiruv algoritmi deyiladi. Qidiruv algoritmlari ma’lum bir ma’lumotlar tuzilmasida saqlanayotgan ma’lumotni olish uchun ishlatiladi. Bunga, muayyan ro‘yxatdan yoki u saqlanadigan har qanday ma’lumotlar strukturasidan ma’lum bir elementni topish masalasini misol qilish mumkin. Qidiruv jarayonining turiga qarab, ushbu algoritmlar odatda ikkita toifaga bo'linadi:

1. 
   Ketma-ket qidiruv: Bunda roʻyxat yoki massiv ketma-ket oʻtadi va har bir element tekshiriladi. Masalan: Linear Search (Chiziqli qidiruv).
   
2. 
   Intervalli qidiruv: Bu holda algoritmlar saralangan ma’lumotlar tuzilmalarida qidirish uchun maxsus ishlab chiqilgan. Ushbu turdagi qidiruv algoritmlari chiziqli qidiruvga qaraganda ancha samaraliroqdir, chunki ular qayta-qayta qidiruv strukturasining markazini nishonga oladi va qidiruv maydonini ikkiga bo‘ladi. Masalan: Binary Search (Ikkilik qidiruv).
   

Linear Search (Chiziqli qidiruv)
Chiziqli qidiruv yondashuvida asosiy element kalitini massivdagi har bir element bilan ketma-ket taqqoslanadi. Kalit massivdagi elementga to‘g‘ri kelmaguncha yoki massiv tugamaguncha jarayon davom etadi. Agar mos kelsa, chiziqli qidiruv massivdagi kalitga mos keladigan element indeksini qaytaradi. Aks holda, qidiruv -1 ni qaytaradi.
N ta elementdan iborat arr[] massivi berilgan bo‘lsa, ma’lum x elementni arr[] dan qidirish kerak. Bu quyidagicha amalga oshiriladi:

1. 
   arr[] ning eng chapdagi elementidan boshlansin va x ni arr[] ning har bir elementi bilan birma-bir taqqoslansin.
   
2. 
   Agar x element bilan mos kelsa, indeksni qaytarilsin.
   
3. 
   Agar x elementlarning birortasiga mos kelmasa, -1 ni qaytarilsin.
   

Masalan:

Berilgan:
arr[] = {20, 34, 51, 27, 19, 21, 31},
x = 27
Natija: 3
Izoh: qidirilayotgan x element 3-o‘rinda joylashgan.

Berilgan:

arr[] = {20, 34, 51, 27, 19, 21, 31},
x = 35
Natija: -1
Izoh: qidirilayotgan x element arr[] mavjud emas.

Misol. Bizga quyidagi ro‘yxat berilgan. Ro‘yxatdan 27 elementini topishni chiziqli qidiruv algoritmi yordamida ko‘rib chiqamiz.

20

34

51

27

19

21

31

Qidiruv quyidagicha amalga oshiriladi. Birinchi elementni olamiz va tekshiramiz.

20

32

58

27

19

21

5

20 < 27, biz qidirayotgan element bu emas. Demak, keyingi elementga o‘tamiz.

20

32

58

27

19

21

5

32 > 27, biz qidirayotgan element bu emas. Demak, keyingi elementga o‘tamiz.

20

32

58

27

19

21

5

58 > 27, biz qidirayotgan element bu emas. Demak, keyingi elementga o‘tamiz.

20

32

58

27

19

21

5

27 = 27, biz qidirayotgan element shu. “Uchinchi indeksli yacheykada joylashgan element biz qidirayotgan elementga teng” natijasi qaytariladi. Algoritm yakunlandi.

Quyida yuqoridagi yondashuvni C++ da amalga oshirish dasturi ko‘rsatilgan:

#include

using namespace std;
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 1;
int N = sizeof(arr) / sizeof(arr[0]);
int result = -1;
int i;
for (i = 0; i < N; i++)
if (arr[i] == x)
result = i;
(result == -1)
? cout << "Ushbu element massivda mavjud emas"
: cout << "Ushbu element " << result<<" indeksli yacheykada joylashgan";
return 0;
}

Chiziqli qidiruv funksiyasi kalitni massivdagi har bir element bilan taqqoslaydi. Massivdagi elementlar har qanday tartibda bo‘lishi mumkin. Chiziqli qidiruvning bajarilish vaqti massiv elementlari soni ortishi bilan chiziqli ravishda oshib borgani uchun katta massiv uchun chiziqli qidiruv samarasiz.

Binary Search (Ikkilik qidiruv)

Ikkilik qidiruv - bu ro‘yxatdan element qidirishning boshqa keng tarqalgan usuli. Bu algoritm uchun massiv elementlari tartiblangan (saralangan) bo‘lishi lozim. Massiv o‘sish tartibida deb faraz qilsak. Ikkilik qidiruv birinchi navbatda kalitni massivning o‘rtasida joylashgan element bilan taqqoslaydi. Quyidagi holatlarni ko‘rib chiqing:

• 
  Agar kalit o‘rtadagi elementdan kichik bo‘lsa, siz faqat ro‘yxatning birinchi yarmida qidirishni davom ettirishingiz kerak.
  
• 
  Agar kalit o‘rta elementga teng bo‘lsa, element topilgani uchun qidiruv yakunlanadi.
  
• 
  Agar kalit o‘rta elementdan kattaroq bo‘lsa, siz faqat massivning ikkinchi yarmida qidirishni davom ettirishingiz kerak.
  

Shubhasiz, ikkilik qidiruv funksiyasi har bir taqqoslashdan keyin massivning kamida yarmini yo‘q qiladi.
N ta elementdan iborat tartiblangan arr[] massivi berilgan bo‘lsa, ma’lum x elementni arr[] dan qidirish kerak. Bu quyidagicha amalga oshiriladi:

1. 
   x ni o‘rtadagi element bilan taqqoslang.
   
2. 
   Agar x o‘rtadagi elementga mos kelsa, biz o‘rta indeksni qaytaramiz.
   
3. 
   Aks holda, agar x o‘rtadagi elementdan katta bo‘lsa, x faqat o‘rta elementdan keyingi o‘ng yarim ro‘yxatdan qidiriladi. Shunday qilib, biz ushbu qadamni o‘ng yarmi uchun takrorlaymiz.
   
4. 
   Aks holda (x kichikroq) chap yarmi uchun takrorlanadi.
   

Masalan:

Berilgan:
arr[] = {19, 20, 21, 27, 31, 34, 51},
x = 21
Natija: 2
Izoh: qidirilayotgan x element 2-o‘rinda joylashgan.

Berilgan:

arr[] = {19, 20, 21, 27, 31, 34, 51},
x = 35
Natija: -1
Izoh: qidirilayotgan x element arr[] mavjud emas.

Misol. Bizga quyidagi tartiblangan ro‘yxat berilgan. Ro‘yxatdan 21 elementini topishni ikkilik qidiruv algoritmi yordamida ko‘rib chiqamiz.

19

20

21

27

31

34

51

Qidiruv quyidagicha amalga oshiriladi. Massivning o‘rtasidagi elementni olamiz va tekshiramiz.

19

20

21

27

31

34

51

21 < 27, biz qidirayotgan element bu emas va u 27 dan kichik. Demak, massivning 27 dan kichik elementlari joylashgan chap tomonini tekshiramiz va o‘ng tomonini esa tekshirmaymiz.

19

20

21

27

31

34

51

Chap tomonidagi elementlardan ham o‘rtadagini tanlab olamiz

19

20

21

27

31

34

51

21 > 20, biz qidirayotgan element bu emas va u 20 dan katta. Demak, massivning 20 dan katta elementlari joylashgan o‘ng tomonini tekshiramiz va chap tomonini esa tekshirmaymiz.

19

20

21

27

31

34

51

Bu holda ham, qolgan elementlarning o‘rtanchasini tanlab olish kerak edi, ammo bizda bittagina element qoldi. Shuning uchun uni tekshiramiz.

19

20

21

27

31

34

51

21 = 21, biz qidirayotgan element shu. “Uchinchi indeksli yacheykada joylashgan element biz qidirayotgan elementga teng” natijasi qaytariladi. Algoritm yakunlandi.

Quyida yuqoridagi yondashuvni C++ da amalga oshirish dasturi ko‘rsatilgan:

#include

using namespace std;
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = -1;
int l = 0;
int r = n - 1;

while (l <= r) {

int m = l + (r - l) / 2;
if (arr[m] == x)
result = m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
(result == -1)
? cout << "Ushbu element massivda mavjud emas"
: cout << "Ushbu element " << result<<" indeksli yacheykada joylashgan";
return 0;
}

Chiziqli qidiruv kichik massiv yoki tartiblanmagan massivdagi elementni topish uchun foydali, lekin katta massivlar uchun u samarasiz ekanini yuqorida ta’kidladik. Ikkilik qidiruv esa oldindan saralangan katta massivlar uchun samaraliroq.

Saralash
Saralash - tartiblash (Sorting Algorithms) deb, berilgan obyektlar ketma-ketligini ma’lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash elementlarni keyinchalik foydalanishga qulay holatga keltiradi. Agar bir sonlar massivini o‘sib borish tartibida saralasak, u holda birinchi element har doim eng katta, oxirgi element esa eng kichik bo‘ladi. Misol uchun maktab jurnalida o‘quvchilar familiyasi alifbo tartibiga ko‘ra saralangan bo‘ladi. Masalan, bizga sonlar qatori berilgan: 20, 34, 51, 27, 19, 21, 31. Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni