Niyə Alqoritm Vacibdir?

1-ci bölümdə biz data strukturların kodumuzun performansına necə təsir edə biləcəyini gördük. Bu bölümdə isə alqoritmanın kodumuzun performansına necə təsir edə biləcəyinə baxacağıq.

Alqoritm nədir?

Alqoritm, müəyyən bir tapşırığı yerinə yetirmək üçün izlənilən dəqiq addımlar ardıcıllığıdır.

Məsələn:

Makaron bişirmə alqoritması:

Su qaynadın.
Duz və makaron əlavə edin.
Bişirin və süzün.
Servis edin.

Başqa addımlarda əlavə etmək olar, amma bu qısa alqoritma ilə makaronu bişirə bilərik.

Biz kod yazarkən alqoritma qururuq, komputer o addımları izləyir və kodu icra edir. Ola bilər ki, iki alqoritma olsun, eyni işi görsün, biri digərindən daha az addim atsın birinci bölümdə gördüyümüz kimi.

Bu bölümdə də iki alqoritma görəcəyik, ikisi də eyni işi görəcək, amma birin digərindən qatlarla sürətli olacaq.Bunları görmək üçün yeni data strukturuna baxaq.

Sıralı Arraylər(Ordered Arrays)

Sıralı arraylərdə bildiyimiz klassik arraylər kimidir, amma sıralı olmalıdır.

Məsələn, sıralı bir arrayımız olsun.

let arr = [6, 15, 80, 321];

Əgər bu klassik array olsaydı və 42 rəqəmini əlavə etmək istəsəydik, 1 addım alacaqdı, çünki arrayin sonuna əlavə etməliydi.

Sıralı arraydə 42-ni 15 ilə 80-in arasına qoymalıyıq, amma komputer bunu bir addımda edə bilməz. Birinci düzgün yerini tapmalıdır (yəni 75-i qoymaq üçün) və sonra digər dəyərləri shift etməlidir yer açmaq üçün.

Addım-addım:

Komputer 6-ya baxır: 42, 6-dan böyükdür davam edir..
15-ə baxır: yenə böyükdür davem edir
80-ə baxır: 42 kiçikdir burda düzgün yeri tapır və shift etməyə başlayır
Sondakı dəyəri yəni 321 shift edir sağ tərəfə
Sonra 80 shift edir sağa
Və sonra 42-ni yerinə qoyur

let arr = [6, 15, 42, 80, 321];

Sıralı array-ə əlavə etmə daha çox addım alır regular arraydən.

İndi isə sıralı array-də Searching-ə baxaq

Sıralı Arraydə Axtarış

Biz öyrənmişdik ki, klassik array-də axtardığımız dəyəri tapana qədər soldan sağa doğru axtarış aparılır və xanalar bir-bir yoxlanılır. Buna isə “linear search” deyilir.

İndi isə “linear search” alqoritmi sıralı və sıralanmamış array-də necə fərqlik göstərir, ona baxaq.

Deyək ki, bizim klassik bir arrayimiz var — hansı ki, sıralanmayıb —

[12, 4, 16, 400, 30];

Əgər biz bu arraydə mövcud olmayan 14 dəyərini axtarsaq, hər bir elementi yoxlamalı olardıq, çünki 14 arrayin istənilən yerində ola bilər.

Əgər təsadüfən axtardığımız dəyəri tapsaq, axtarışı dayandıra bilərik, yoxsa arrayin sonuna kimi getməliyik ki, əmin olaq axtardığımız dəyər orada deyil.

Sıralı arraydə isə axtarışı tez dayandıra bilərik. Tutaq ki,

[4, 12, 16, 30, 400];

Sıralı massivdə 14-ü axtarırıq. 16-ya çatan kimi axtarışı dayandıra bilərik, çünki 14-ün onun sağında olması mümkün deyil.

Ordered array üçün Linear Search:

function linearSearch(array, searchValue) {
  // Array üzərində iterasiya edirik
  for (let i = 0; i < array.length; i++) {
    // Əgər element axtarılan dəyərə bərabərdirsə, indeksini qaytarırıq
    if (array[i] === searchValue) {
      return i;
    }
    // Array sıralı olduğu üçün, element axtarılan dəyərdən böyükdürsə,
    // bundan sonra gələn elementlər də daha böyük olacaq. Ona görə axtarışı dayandırırıq.
    if (array[i] > searchValue) {
      break;
    }
  }
  // Axtarılan dəyər array-də yoxdursa, -1 qaytarılır
  return -1;
}

Bura qədər yalnız array-də axtarışı Linear Search alqoritması ilə görmüşük. Ancaq array-lərdə axtarış etməyin tək yolu bu deyil. Sıralı (Ordered) array-in klassik (sıralanmamış) array-dən üstünlüyü ondan ibarətdir ki, Ordered array-də başqa axtarış alqoritmindən istifadə etməyə imkan verir. Bu alqoritm Binary Search adlanır.

Binary Search

Yəqin ki, bu oyunu hamımız oynamışıq: Mən 1 ilə 100 arasında bir rəqəm fikirləşirəm. Qarşımdakı isə həmin rəqəmi təxmin edir. O, bir rəqəm dedikdə, mən “yuxari və ya aşağı” deyə bildirəm.

Əgər belə bir oyun oynasaqdıq, siz yəqin ki, 50 deyərdiniz ki, rəqəmi tapmaq daha asan və sürətli olsun.

Tutaq ki, mən 1-dən 10-a qədər bir rəqəm fikirləşdim. Oyun çox güman ki, belə olardı:

Əgər belə bir oyun oynasaqdıq, siz yəqin ki, 50 deyərdiniz ki, rəqəmi tapmaq daha asan və sürətli olsun.

Tutaq ki, mən 1-dən 10-a qədər bir rəqəm fikirləşdim. Oyun çox güman ki, belə olardı:

Binary Search də bu məntiq ilə işləyir.

İndi isə sıralı array-ə Binary Search alqoritmasını tətbiq edək. Tutaq ki, bizim 9 elementli bir arrayimiz var.

[4, 8, 12, 16, 20, 23, 28, 32, 40];

bu array-də biz 23-i tapmaqa çalışaq

1)Addim: Array-in orta indeksini tapmalıyıq Binary Search-də orta elementi tapmaq üçün bu düsturdan istifadə edirik:

Burada:
- start – axtarış sahəsinin ilk indeksidir (başlanğıcda 0 olur, çünki array sıfırdan başlayır).
- end – axtarış sahəsinin son indeksidir (array.length - 1).
- mid – orta indeksdir, yəni Math.floor((start + end) / 2).
Bizim array-də orta index 4-dür dəyəri isə 20.

23 > 20 olduğu üçün, axtarışın sol hissəsindəki elementlərə ehtiyac yoxdur.

Array:
```
[23, 28, 32, 40];
```
2)Addım: Yenə hesablayırıq 6-cı indeksdəki dəyər: 28

23 < 28 olduğu üçün, axtarışın sağ hissəsindəki elementlərə ehtiyac yoxdur.

Array:
```
[23];
```
3)Addım: 5-ci indeksdəki dəyər: 23. 23 == 23 olduğu üçün, axtarış tamamlanır və 23-ün indeksi olan 5 qaytarılır. (əgər orda da deyilsə deməli array-də 23 yoxdur.)

qısa:

1. Addım:

- Orta indeks: 4 (dəyəri: 20)
- 23 > 20 olduğu üçün sol hissəyə ehtiyac yoxdur.
Yeni axtarış sahəsi: [23, 28, 32, 40]

2. Addım:

- Orta indeks: 2 (dəyəri: 28)
- 23 < 28 olduğu üçün sağ hissəyə ehtiyac yoxdur.
Yeni axtarış sahəsi: [23]

3. Addım:

- Yalnız bir element qalır: 23
- 23 tapıldı və axtarış tamamlandı.


**Binary search yalnız sıralanmış array-də mümkündür.**

JavaScript ilə yazılışı:

```js
function binarySearch(arr, target) {
let start = 0; // Axtarışın başlanğıc indeksi
let end = arr.length - 1; // Axtarışın son indeksi

while (start <= end) {
  // Orta indeksi tapırıq
  let mid = Math.floor((start + end) / 2);

  // Əgər orta element axtarılan elementdirsə
  if (arr[mid] === target) {
    return mid; // Elementin indeksini qaytarırıq
  }
  // Əgər axtarılan element orta elementdən böyükdürsə
  else if (arr[mid] < target) {
    start = mid + 1; // Axtarışı sağ hissəyə keçiririk
  }
  // Əgər axtarılan element orta elementdən kiçikdirsə
  else {
    end = mid - 1; // Axtarışı sol hissəyə keçiririk
  }
}

// Əgər element tapılmasa
return -1;
}

Binary Search vs Linear Search

Kiçik datalar olanda Linear Search ilə Binary Search arasındakı fərq o qədər nəzərə çarpmır. Amma böyük datalar olanda fərq çox açıq görünür. Məsələn, 100 elementli bir array-də:

Linear Search ən pis halda 100 addım tələb edir.
Binary Search isə maksimum 7 addım ilə cavabı tapır.

Linear Search-də, əgər axtardığımız dəyər sonuncu elementdədirsə bütün elementləri yoxlamalıyıq. 100 elementli bir array üçün bu, 100 addım deməkdir.

Binary Search-də isə elə ilk axtarışda bizə lazım olmayan 50-sini görməzdən gəlirik.

Məsələn, array-də 3 data varsa, Binary Search ilə bu 2 addımda tapılacaq. Əgər 3-ü ikiqat artırıb üstünə 1 gəlsək (hesablama rahat olsun deyə), 7 data üçün 3 addım lazım olacaq. Yenə ikiqat artırıb üstünə 1 gəlsək, 15 data üçün 4 addım lazım olacaq

Burada kı çox səmərəli bir patterndir, çünki hər dəfə data sayını ikiqat artıranda, Binary Search-in axtarış addımı sayı yalnız 1 vahid artır.

Amma Linear Search-də array-də 3 data varsa 3 addım, 7 varsa 7 addım, 15 varsa 15 addım ilə tapılacaq.

100 elementli array-də binary search 7 addım atır. 200 elementli array-də nə qədər addım atacaq? İlk olaraq 14 deyə bilərik, amma doğru cavab 8 addımdır. Burada əsas məqam odur ki, binary search-in addım sayını artırmaq üçün array-in ölçüsünü iki qat artırmalıyıq.

Sıralanmış array-lar hər zaman sürətli deyil. Sıralanmış array-lərdə əlavə etmə, adi array-lərə nisbətən daha yavaşdır.

Sıralanmış array istifadə edərək, əlavə etmə prosesi daha yavaş olsa da, axtarış çox daha sürətli olur. Hər zaman tətbiqinizi analiz edib hansı metodun daha uyğun olduğuna qərar verməlisiniz.

Proqramınızda çox sayda əlavə etmə əməliyyatı olacaq? yoxsa axtarış tətbiqdə əsas funksiya olacaq?