Javascript Timsort Algoritması

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

Timsort Algoritması

Timsort, Python, Java, C++ ve daha birçok programlama dilinde kullanılan bir sıralama algoritmasıdır. Bu algoritma, ilk olarak 2002 yılında Tim Peters tarafından Python programlama dili için yazılmıştır ve ismini de ondan almıştır. Timsort, en iyi ve en kötü durumlarda O(n log n) zaman karmaşıklığına sahiptir ve pratikte diğer sıralama algoritmalarından daha hızlı çalışabilir.

Timsort, birleştirme sıralama (merge sort) ve ekleme sıralama (insertion sort) algoritmalarını birleştirerek çalışır. Bu sayede, bir dizi üzerindeki sıralama işleminde farklı boyutlardaki alt dizilerin farklı sıralama algoritmaları kullanarak sıralanması sağlanır.

Javascript Timsort Algoritması Kodu

Aşağıda, JavaScript kullanarak bir dizinin Timsort algoritması kullanılarak nasıl sıralanabileceği gösterilmektedir:

function timsort(arr) {
  const RUN = 32;
  const n = arr.length;

  // İnsertion sort uygulanacak alt dizilerin belirlenmesi
  for (let i = 0; i < n; i += RUN) {
    insertionSort(arr, i, Math.min(i + RUN, n));
  }

  // Birleştirme işlemleri
  for (let size = RUN; size < n; size = 2 * size) {
    for (let left = 0; left < n; left += 2 * size) {
      const mid = left + size;
      const right = Math.min(left + 2 * size, n);

      merge(arr, left, mid, right);
    }
  }
  return arr;
}

function insertionSort(arr, left, right) {
  for (let i = left + 1; i < right; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
}

function merge(arr, left, mid, right) {
  const len1 = mid - left;
  const len2 = right - mid;

  const leftArr = new Array(len1);
  const rightArr = new Array(len2);

  for (let i = 0; i < len1; i++) {
    leftArr[i] = arr[left + i];
  }
  for (let i = 0; i < len2; i++) {
    rightArr[i] = arr[mid + i];
  }

  let i = 0;
  let j = 0;
  let k = left;

  while (i < len1 && j < len2) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }

  while (i < len1) {
    arr[k] = leftArr[i];
    k++;
    i++;
  }

  while (j < len2) {
    arr[k] = rightArr[j];
    k++;
    j++;
  }
}

Kod Açıklamaları

Yukarıdaki kodda, timsort fonksiyonu, bir dizi alır ve önce dizi üzerinde küçük alt dizileri insertion sort kullanarak sıralar. Ardından, birleştirme işlemleri gerçekleştirerek, alt dizileri birleştirir ve son olarak sıralanmış diziyi döndürür.

insertionSort fonksiyonu, bir alt dizi içindeki elemanları küçükten büyüğe doğru sıralar. merge fonksiyonu ise, iki alt diziyi birleştirir.

Timsort algoritması, özellikle büyük boyutlu dizilerin sıralanması için tercih edilir. Ayrıca, bazı programlama dillerinde varsayılan sıralama algoritması olarak da kullanılır.

Örnek Kullanım

Aşağıda, bir örnek kullanımı gösterilmiştir:

const arr = [4, 2, 1, 3, 5];
console.log(timsort(arr)); // [1, 2, 3, 4, 5]

Yukarıdaki örnekte, arr adlı dizi önce Timsort algoritması kullanılarak sıralanır ve sonucu console.log() fonksiyonu kullanılarak ekrana yazdırılır.

Sonuç

Timsort algoritması, özellikle karmaşık yapıya sahip verilerin sıralanmasında etkilidir. Ancak, küçük boyutlu dizilerde diğer sıralama algoritmaları daha hızlı çalışabilir. Bu nedenle, sıralama işlemi yapılacak veri setinin boyutu ve özellikleri göz önünde bulundurularak hangi sıralama algoritmasının kullanılacağına karar verilmelidir.

Evet Javascript ile timsort 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.