Javascript Natural 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 Natural Merge Sort algoritmasını anlatacağım. Hadi başlayalım !

Natural Merge Sort

Natural Merge Sort, Merge Sort algoritmasının bir varyasyonudur ve özellikle neredeyse sıralanmış veya kısmen sıralanmış diziler için daha hızlı çalışır. Normal Merge Sort’ta, her zaman iki alt-dizi oluşturulur ve bu alt-diziler sıralanır, ardından birleştirilir. Ancak, neredeyse sıralı bir dizi durumunda, birleştirme aşamasında çoğu işlem gereksizdir, çünkü her iki alt-dizi de zaten sıralıdır. Natural Merge Sort, bu durumda, zaten sıralanmış bölümleri algılayarak işlem yapar ve sıralama sürecini hızlandırır.

Natural Merge Sort algoritması, öncelikle diziyi iki alt-diziye böler, ardından her alt-diziyi ayrı ayrı sıralar. Daha sonra, sıralı alt-dizileri birleştirerek sıralı bir dizi oluşturur. Bu adımlar, tüm dizinin sıralanana kadar tekrarlanır.

Javascript Kodu

Natural Merge Sort algoritmasını JavaScript’te uygulamak için öncelikle bir fonksiyon oluşturmamız gerekiyor. Bu fonksiyon, sıralanacak diziyi parametre olarak alacak ve sıralanmış diziyi döndürecek.

function naturalMergeSort(arr) {
  // TODO: Sıralama algoritması buraya yazılacak.
  return arr;
}

Natural Merge Sort algoritmasını uygulamak için, sıralanacak diziyi sırayla ikiye bölmeliyiz. Ardından, her iki alt-diziyi ayrı ayrı sıralayıp, birleştirerek sıralı bir dizi elde edeceğiz. Bu adımların tüm diziyi sıralamak için tekrarlanması gerekecektir. Bu işlemi yapmak için, birleştirme işleminin gerçekleştiği bir fonksiyon yazacağız. İşte tüm kodlar:

function naturalMergeSort(arr) {
  function merge(arr, start, mid, end) {
    const left = arr.slice(start, mid + 1);
    const right = arr.slice(mid + 1, end + 1);
    let i = 0;
    let j = 0;
    let k = start;

    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        arr[k] = left[i];
        i++;
      } else {
        arr[k] = right[j];
        j++;
      }
      k++;
    }

    while (i < left.length) {
      arr[k] = left[i];
      i++;
      k++;
    }

    while (j < right.length) {
      arr[k] = right[j];
      j++;
      k++;
    }
  }

  function mergeSort(arr, start, end) {
    if (start >= end) {
      return;
    }
    let mid = Math.floor((start + end) / 2);
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);

    // Neredeyse sıralı bölümleri tespit et
    if (arr[mid] <= arr[mid + 1]) {
      return;
    }

    // Alt-dizileri sırala ve birleştir
    merge(arr, start, mid, end);
  }

  mergeSort(arr, 0, arr.length - 1);
  return arr;
}

Kod Açıklamaları

Bu kod örneği, Natural Merge Sort algoritmasının çalışma mantığını göstermektedir. İlk önce, sıralanacak diziyi parametre olarak alan naturalMergeSort fonksiyonunu oluşturuyoruz. Ardından, iki alt-diziye bölme işlemini gerçekleştirmek için mergeSort fonksiyonunu oluşturuyoruz. mergeSort fonksiyonu, verilen diziyi sırayla ikiye bölerek, her iki alt-diziyi ayrı ayrı sıralıyor. Daha sonra, alt-dizileri birleştirerek sıralı bir dizi elde ediyor. Ancak, burada bir fark var. Alt-dizileri birleştirmeden önce, neredeyse sıralı bölümleri tespit ediyoruz. Eğer alt-diziler neredeyse sıralıysa, birleştirme işlemi yapmıyoruz ve sıralama sürecini hızlandırıyoruz.

Natural Merge Sort algoritması, neredeyse sıralanmış veya kısmen sıralanmış dizilerde Merge Sort’a göre daha hızlı çalışır. Ancak, tamamen rastgele dizilerde Merge Sort ile aynı performansı gösterir. Bu nedenle, sıralanacak dizinin yapısına göre algoritmayı seçmek önemlidir.

Sonuç

Bu makalede, Natural Merge Sort algoritması hakkında bilgi verdim ve JavaScript kod örnekleriyle nasıl uygulanacağını gösterdim. Bu algoritma, özellikle neredeyse sıralı veya kısmen sıralı diziler için faydalıdır. Ancak, tamamen rastgele dizilerde Merge Sort ile aynı performansı gösterir. Bu nedenle, sıralama işlemi yapmadan önce dizinin yapısını dikkate almak önemlidir.

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