Javascript Tournament 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 tournament sort algoritmasını anlatacağım. Hadi başlayalım !

Tournament Sort Algoritması

Tournament sort, sıralama algoritmalarından biridir. Bu algoritma, bir dizi elemanı, belirli bir turnuva yapısı kullanarak sıralar. Bu turnuva yapısı, elemanların ikili olarak karşılaştırılması ve turnuvanın kazananının belirlenmesi yoluyla gerçekleşir. Bu işlem, belirli bir öncelik sırasına göre elemanların sıralanmasına neden olur.

Tournament sort, sıralanacak dizinin büyüklüğüne göre iyi bir performans gösterir. Büyük diziler için verimli bir şekilde çalışır ve O(nlogn) zaman karmaşıklığına sahiptir. Ancak, küçük diziler için performansı nispeten daha düşüktür.

Çalışma Adımları

Tournament sort algoritmasının çalışma prensibi şu şekildedir:

1. Dizideki her eleman bir turnuvaya katılır.
2. Her tur, turnuvadaki elemanların sayısının yarısı kadar eleme turu yapılır. Bu eleme turunda, elemanlar ikili olarak karşılaştırılır ve turun kazananı bir sonraki tura geçer.
3. Son turda, turnuvanın kazananı dizinin ilk elemanı olur.
4. Dizinin ilk elemanı sıralanmış dizideki yerini alır ve turnuvadan çıkarılır.
5. Kalan elemanlar için aynı işlem tekrar edilir.

Javascript Kodu

JavaScript ile birlikte, Tournament sort algoritmasını uygulamak oldukça kolaydır. Aşağıda, Tournament sort algoritması için JavaScript kod örnekleri verilmiştir:

function tournamentSort(arr) {
  const n = arr.length;
  const treeSize = 2 * Math.pow(2, Math.floor(Math.log2(n))) - 1;
  const tree = new Array(treeSize);

  buildTree(tree, arr, 0, n - 1, 0);

  for (var i = 0; i < n; i++) {
    arr[i] = extractMin(tree, 0, n - 1, 0);
  }

  return arr;
}

function buildTree(tree, arr, start, end, treeIndex) {
  if (start == end) {
    tree[treeIndex] = arr[start];
    return;
  }

  var mid = Math.floor((start + end) / 2);

  buildTree(tree, arr, start, mid, 2 * treeIndex + 1);
  buildTree(tree, arr, mid + 1, end, 2 * treeIndex + 2);

  tree[treeIndex] = Math.min(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}

function extractMin(tree, start, end, treeIndex) {
  if (start == end) {
    const min = tree[treeIndex];
    tree[treeIndex] = Infinity;
    return min;
  }

  const mid = Math.floor((start + end) / 2);

  const leftMin = tree[2 * treeIndex + 1];
  const rightMin = tree[2 * treeIndex + 2];

  if (leftMin <= rightMin) {
    tree[2 * treeIndex + 2] = Infinity;
    return leftMin;
  } else {
    tree[2 * treeIndex + 1] = Infinity;
    return rightMin;
  }
}

Kod Açıklamaları

Yukarıdaki kod, Tournament sort algoritmasını JavaScript ile uygulamak için bir örnek olarak kullanılabilir. Bu kod, bir dizi elemanı sıralamak için kullanılabilir.

Bu kod örneği, tournamentSort fonksiyonunu kullanarak bir dizi elemanı sıralar. Fonksiyon, arr parametresi olarak bir dizi alır ve sıralanmış bir dizi döndürür.

Fonksiyon, buildTree ve extractMin fonksiyonlarını kullanarak bir turnuva yapısı oluşturur ve elemanları sıralar. buildTree fonksiyonu, bir turnuva yapısını oluşturmak için kullanılır. extractMin fonksiyonu ise, turnuvanın kazananını bulmak için kullanılır.

Bu kod örneğinde, turnuva yapısı bir dizi ile temsil edilir. Dizinin boyutu, turnuvanın en üstündeki düğüme karşılık gelir. Bu dizinin her elemanı, turnuvadaki bir düğümün değerini temsil eder.

Turnuva yapısını oluşturmak için, buildTree fonksiyonu, rekürsif bir şekilde turnuvanın sol ve sağ alt ağaçlarını oluşturur. Bu alt ağaçlardan biri kazananı belirler ve üst düğümün değeri olarak atanır. Bu işlem, turnuva yapısının oluşturulması için gereklidir.

Turnuvanın kazananını bulmak için, extractMin fonksiyonu, rekürsif bir şekilde turnuvanın sol ve sağ alt ağaçlarını kontrol eder ve kazananı belirler. Bu kazanan, sıralama için kullanılır ve turnuvadan çıkarılır.

Sonuç

Sonuç olarak, Tournament sort algoritması, sıralama algoritmalarından biridir ve büyük diziler için verimli bir şekilde çalışır. JavaScript gibi bir programlama dili ile kolayca uygulanabilir ve performans açısından iyi bir seçim olabilir.

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