Javascript Bottom-up Merge 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 bottom-up merge sort algoritmasını anlatacağım. Hadi başlayalım !

Bottom-up merge sort, bir sıralama algoritmasıdır ve n log n zaman karmaşıklığına sahiptir. Bu algoritmanın ana fikri, bir diziyi küçük parçalara ayırmak ve bu parçaları birleştirmektir. Bu makalede, bottom-up merge sort algoritmasını açıklayacak ve JavaScript kod örnekleriyle birlikte göstereceğim.

Algoritma Açıklaması

1. Diziyi, elemanları birerli, ikişerli, dörderli, sekizerli şeklinde gruplara ayırarak başlayın.
2. Her grup içindeki elemanları birbirleriyle karşılaştırarak küçükten büyüğe doğru sıralayın.
3. Ardından, birinci ikişerli grupla ikinci ikişerli grupları birleştirin ve her bir birleşik grubu sıralayın.
4. İşlemi 3. adımda olduğu gibi tüm gruplar için tekrarlayarak, sonunda tek bir sıralı dizi elde edin.

JavaScript Kod Örneği

function mergeSort(arr) {
  const len = arr.length;
  for (let size = 1; size < len; size *= 2) {
    for (let leftStart = 0; leftStart < len; leftStart += 2 * size) {
      const mid = leftStart + size - 1;
      const rightEnd = Math.min(leftStart + 2 * size - 1, len - 1);
      merge(arr, leftStart, mid, rightEnd);
    }
  }
  return arr;
}

function merge(arr, leftStart, mid, rightEnd) {
  const leftEnd = mid;
  const rightStart = mid + 1;
  const temp = [];

  let left = leftStart;
  let right = rightStart;
  let k = 0;

  while (left <= leftEnd && right <= rightEnd) {
    if (arr[left] < arr[right]) {
      temp[k] = arr[left];
      k++;
      left++;
    } else {
      temp[k] = arr[right];
      k++;
      right++;
    }
  }

  while (left <= leftEnd) {
    temp[k] = arr[left];
    k++;
    left++;
  }

  while (right <= rightEnd) {
    temp[k] = arr[right];
    k++;
    right++;
  }

  for (let i = 0; i < k; i++) {
    arr[leftStart + i] = temp[i];
  }
}

Yukarıdaki JavaScript kod örneği, bottom-up merge sort algoritmasını uygulayan bir işlev içerir. mergeSort işlevi, verilen bir diziye göre bottom-up merge sort işlemini gerçekleştirir. merge işlevi, iki alt dizi arasında birleştirme işlemini gerçekleştirir.

Bottom-up merge sort algoritması, diğer sıralama algoritmaları gibi, performans açısından en iyi olmayabilir. Ancak, n*logn zaman karmaşıklığına sahip olduğu için, büyük veri kümelerinde hızlı bir şekilde çalışabilir. Ayrıca, bu algoritmanın n*logn zaman karmaşıklığı, diğer bazı sıralama algoritmalarına kıyasla daha iyi bir performans sunar.

Bottom-up merge sort algoritmasının bir diğer avantajı, verilerin bellekte başka bir yerde kopyalanmasına gerek olmamasıdır. Bu sayede, bellek yönetimi açısından da etkili bir yöntemdir.

Algoritma İşlem Adımları

Aşağıdaki örnekte, bottom-up merge sort algoritması nasıl çalışır görebilirsiniz.

Örnek dizi: [9, 5, 7, 3, 8, 6, 2, 1]

• Dizi, ikişerli gruplara ayrılır: [5, 9], [3, 7], [6, 8], [1, 2]
• Her grup sıralanır: [5, 9], [3, 7], [6, 8], [1, 2] › [5, 9], [3, 7], [6, 8], [1, 2]
• İki ikişerli grup birleştirilir ve sıralanır: [3, 5, 7, 9], [1, 2, 6, 8]
• Dizi, dörderli gruplara ayrılır: [3, 5, 7, 9], [1, 2, 6, 8]
• Her grup sıralanır: [3, 5, 7, 9], [1, 2, 6, 8] › [3, 5, 7, 9], [1, 2, 6, 8]
• İki dörderli grup birleştirilir ve sıralanır: [1, 2, 3, 5, 6, 7, 8, 9]

Yukarıdaki örnekte, verilen dizi küçük gruplara ayrılır ve her bir grup sıralanır. Ardından, gruplar birleştirilir ve sıralanır. Bu işlem, grupların boyutu artana kadar tekrarlanır. Sonunda, tüm gruplar birleştirilerek sıralı bir dizi elde edilir.

Sonuç

Bottom-up merge sort, verilerin bellekte başka bir yerde kopyalanmasına gerek olmayan ve n log n zaman karmaşıklığına sahip bir sıralama algoritmasıdır. Bu makalede, bottom-up merge sort algoritmasının nasıl çalıştığını ve JavaScript kod örnekleriyle nasıl uygulandığını açıkladım. Bu algoritmayı kullanarak, büyük veri kümelerini hızlı bir şekilde sıralayabilirsiniz.

Evet Javascript ile bottom-up merge 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.