Javascript Pigeonhole Sort Algoritması

Herkese merhaba, Javascript yazılarımıza kaldığımız yerden devam ediyoruz. Bu yazımızda sıralama algoritmalarından olan pigeonhole sort algoritmasını anlatacağım. Hadi başlayalım !

Pigeonhole (Güvercin Yuvası) Algoritması Nedir?

Pigeonhole Algoritması, sıralanmamış bir dizideki elemanlar arasında en az bir çift sayıyı bulmak için kullanılan bir algoritmadır. Bu algoritma, adını, güvercin yuvası prensibinden almaktadır. Güvercin yuvası prensibi, birkaç güvercinin birkaç yuvaya yerleştirilmesiyle ilgilidir ve bu prensip, birçok matematiksel problemin çözümünde kullanılır.

Pigeonhole Algoritması, her elemanı bir yuva olarak düşünür ve ardından elemanların sayısı kadar yuvaya güvercinleri yerleştirir. Eğer eleman sayısı yuva sayısından fazlaysa, en az bir yuvada birden fazla güvercin olacaktır. Bu durumda, bir çift sayı bulunmuş demektir.

Javascript Pigeonhole Sort Algoritması Kodu

Pigeonhole Algoritması’nı Javascript ile uygulayabiliriz. İşte, birkaç örnek kod:

Örnek 1

function findPair(arr) {
  const n = arr.length;
  let min = Number.MAX_SAFE_INTEGER;
  
  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (arr[i] == arr[j]) {
        min = Math.min(min, Math.abs(j - i));
      }
    }
  }

  return (min == Number.MAX_SAFE_INTEGER) ? -1 : min;
}

const arr = [8, 4, 2, 6, 10, 2, 8, 1, 2, 4, 9, 5, 7];
console.log(findPair(arr)); // Output: 1

Bu örnekte, bir dizi içindeki en az bir çift sayıyı bulmak için Pigeonhole Algoritması kullanılmıştır. Algoritmanın mantığı, diziyi dolaşarak her elemanı bir yuva olarak düşünmek ve ardından güvercinleri yuvalara yerleştirmektir. Eğer bir yuvada birden fazla güvercin varsa, bir çift sayı bulunmuş demektir. Bu örnekte, çift sayı 2 iki kez bulunduğu için, en az bir çift sayı olduğu sonucuna varılır.

Örnek 2

function findPair(arr) {
  const n = arr.length;
  let min = Number.MAX_SAFE_INTEGER;
  let map = new Map();

  for (let i = 0; i < n; i++) {
    if (map.has(arr[i])) {
      let prevIndex = map.get(arr[i]);
      min = Math.min(min, i - prevIndex);
    }
    map.set(arr[i], i);
  }

  return (min == Number.MAX_SAFE_INTEGER) ? -1 : min;
}

const arr = [8, 4, 2, 6, 10, 2, 8, 1, 2, 4, 9, 5, 7];
console.log(findPair(arr)); // Output: 1

Bu örnekte, Pigeonhole Algoritması, bir Map (harita) veri yapısı kullanılarak uygulanmıştır. Dizideki her eleman, Map’e eklenecek ve Map, elemanların hangi pozisyonlarda olduğunu takip edecektir. Daha sonra, diziyi dolaşarak, aynı elemanın tekrarlandığı bir durumda, önceki pozisyonla şimdiki pozisyon arasındaki fark hesaplanacaktır. Bu fark, en küçük fark olan min değeriyle karşılaştırılacak ve en küçük fark min değerinde saklanacaktır. Bu örnekte de, çift sayı 2 iki kez bulunduğu için, en az bir çift sayı olduğu sonucuna varılır.

Sonuç

Pigeonhole Algoritması, sıralanmamış bir dizideki elemanlar arasında en az bir çift sayıyı bulmak için kullanılan bir algoritmadır. Javascript ile bu algoritmayı uygulamak oldukça kolaydır. İster bir iki iç içe for döngüsüyle, ister bir Map veri yapısı kullanarak, algoritmayı uygulayabilirsiniz. Umarım bu makale, Pigeonhole Algoritması’nı anlamanıza yardımcı olmuştur.

Evet Javascript Pigeonhole Sort Algoritması bu şekilde yazılmakta. Tüm Javascript yazılarımıza buraya, sıralama algoritmaları ile ilgili yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.