Javascript Binary Insertion Sort Algoritması

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

Binary Insertion Sort Nedir?

Binary insertion sort, verileri sıralamak için insertion sort algoritmasına benzer bir yöntem kullanır. Ancak, verileri sıralamak için farklı bir teknik kullanır. Insertion sort algoritmasında, her bir elemanı doğru konumuna yerleştirmek için bir tarama yapılır. Bu tarama sırasında, elemanların doğru konumuna yerleştirilmesi için önceki elemanlarla karşılaştırılır.

Binary insertion sort algoritmasında ise, elemanların doğru konumuna yerleştirilmesi için ikili arama kullanılır. Bu, elemanların doğru konumunu bulmak için daha hızlı bir yöntemdir. Özellikle, büyük veri setleri için insertion sort algoritmasından daha hızlıdır.

Binary Insertion Sort Nasıl Çalışır?

Binary insertion sort algoritması, aşağıdaki adımları izler:

1. İlk elemanı, sıralı bir diziye yerleştir.
2. Sıralı diziye eklenmek istenen elemanın konumunu bulmak için ikili arama yapın.
3. Yeni elemanı, doğru konuma yerleştirin ve diğer elemanları kaydırın.
4. Adım 2 ve 3’ü, veri kümesindeki tüm elemanlar için tekrarlayın.

Aşağıda, bu adımların daha iyi anlaşılabilmesi için örnek bir veri kümesi kullanarak binary insertion sort algoritmasının nasıl çalıştığını gösteren bir JavaScript kod örneği verilmiştir:

function binaryInsertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let x = array[i];
    let j = binarySearch(array, x, 0, i - 1);
    for (let k = i - 1; k >= j; k--) {
      array[k + 1] = array[k];
    }
    array[j] = x;
  }
  return array;
}

function binarySearch(array, x, start, end) {
  if (start == end) {
    if (array[start] > x) {
      return start;
    } else {
      return start + 1;
    }
  }
  if (start > end) {
    return start;
  }
  let mid = Math.floor((start + end) / 2);
  if (array[mid] < x) {
    return binarySearch(array, x, mid + 1, end);
  } else if (array[mid] > x) {
    return binarySearch(array, x, start, mid - 1);
  } else {
    return mid + 1;
  }
}

Bu kodda, binaryInsertionSort fonksiyonu bir dizi alır ve binary insertion sort algoritmasını kullanarak diziyi sıralar. İkinci fonksiyon olan binarySearch, yeni elemanın doğru konumunu bulmak için ikili arama yapar.

binaryInsertionSort fonksiyonu, döngü başlangıcında ilk elemanı zaten sıralanmış bir diziye yerleştirir. Daha sonra, dizinin geri kalan elemanları için ikili arama yaparak doğru konumu bulur. Doğru konum bulunduktan sonra, diğer elemanları kaydırarak yeni elemanı doğru konuma yerleştirir.

binarySearch fonksiyonu, verilen dizideki elemanların doğru konumunu bulmak için ikili arama yapar. İkili arama, veri kümesini her seferinde yarıya indirerek çalışır. Böylece, büyük veri setleri için de hızlı bir şekilde çalışır.

Binary Insertion Sort Algoritması Performansı

Binary insertion sort algoritması, insertion sort algoritmasından daha hızlı çalışır. Insertion sort algoritması, her elemanı doğru konuma yerleştirmek için bir tarama yapar ve bu tarama işlemi, veri kümesinin boyutu arttıkça daha uzun sürebilir. Binary insertion sort algoritması ise, elemanların doğru konumunu bulmak için ikili arama kullanır ve bu sayede daha hızlı çalışır.

Binary insertion sort algoritması, en kötü durumda bile O(n^2) performansa sahiptir. Ancak, veri kümesi sıralı veya neredeyse sıralıysa, O(nlogn) performansı elde edilebilir. Bu nedenle, binary insertion sort algoritması, sıralanmış veya neredeyse sıralanmış veri kümeleri için ideal bir seçimdir.

Sonuç

Bu makalede, binary insertion sort algoritması ile ilgili detayları ve JavaScript kod örneklerini açıkladık. Binary insertion sort algoritması, insertion sort algoritmasına benzer bir yöntem kullanır. Ancak, elemanların doğru konumunu bulmak için ikili arama kullanarak daha hızlı çalışır. Bu nedenle, büyük veri setleri için insertion sort algoritmasından daha hızlıdır.

Evet Javascript ile binary insertion sort algoritması bu şekilde idi. Tüm Javascript yazılarımıza buraya, diğer sıralama algoritmaları yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.