Javascript Introsort Algoritması

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

Introsort Algoritması

Introsort, sıralama algoritmaları arasında en hızlı ve en etkili olanlardan biridir. Bu algoritma, bir dizi elemanı hızlı bir şekilde sıralamak için kullanılır. İntrosort algoritması, birçok farklı sıralama algoritması kullanarak en etkili sıralama yöntemini belirler.

İntrosort algoritması, QuickSort, HeapSort ve InsertionSort sıralama algoritmalarını birleştirir. İlk olarak, QuickSort algoritması ile bir dizi bölünür ve alt diziler, HeapSort algoritması ile sıralanır. Ancak, alt diziler belirli bir boyuta ulaştığında, InsertionSort algoritması kullanılarak sıralama işlemi tamamlanır.

İntrosort, QuickSort ve HeapSort gibi diğer sıralama algoritmalarına göre daha yavaş olsa da, en kötü durumda bile O(n log n) performansı sağlar.

Çalışma Adımları

İntrosort algoritması, bir dizi elemanı sıralamak için kullanılır. Algoritma, aşağıdaki adımları izler:

• Dizi elemanları bir QuickSort algoritması kullanılarak bölünür.
• Bölünmüş alt diziler, HeapSort algoritması kullanılarak sıralanır.
• Alt diziler, belirli bir boyuta ulaştığında, InsertionSort algoritması kullanılarak sıralanır.
• İşlem tamamlanır.

Javascript Kodu

Aşağıda, Introsort algoritmasını Javascript kullanarak nasıl uygulayabileceğinizi gösteren bir örnek kod verilmiştir.

function introsort(arr) {
  const maxdepth = Math.floor(Math.log(arr.length) * 2);
  introsortHelper(arr, 0, arr.length - 1, maxdepth);
  return arr;
}

function introsortHelper(arr, start, end, maxdepth) {
  if (end - start < 16) {
    insertionSort(arr, start, end);
    return;
  }
  if (maxdepth == 0) {
    heapsort(arr, start, end);
    return;
  }
  const pivot = medianOf3(arr[start], arr[Math.floor((start + end) / 2)], arr[end]);
  let i = start;
  let j = end;
  while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }
    while (arr[j] > pivot) {
      j--;
    }
    if (i <= j)
    {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
  if (start < j) {
    introsortHelper(arr, start, j, maxdepth - 1);
  }
  if (i < end) {
    introsortHelper(arr, i, end, maxdepth - 1);
  }
}

function medianOf3(a, b, c) {
  if (a > b) {
    if (b > c) {
      return b;
    } else if (a > c) {
      return c;
    } else {
      return a;
    }
  } else {
    if (a > c) {
      return a;
    } else if (b > c) {
      return c;
    } else {
      return b;
    }
  }
}

function insertionSort(arr, start, end) {
  for (let i = start + 1; i <= end; i++) {
    let j = i;
    while (j > start && arr[j] < arr[j - 1]) {
      swap(arr, j, j - 1);
      j--;
    }
  }
}

function heapsort(arr, start, end) {
  buildHeap(arr, start, end);
  for (let i = end; i > start; i--) {
    swap(arr, start, i);
    heapify(arr, start, i - 1, start);
  }
}

function buildHeap(arr, start, end) {
  const heapsize = end - start + 1;
  for (let i = Math.floor(heapsize / 2); i >= 0; i--) {
    heapify(arr, start, end, i);
  }
}

function heapify(arr, start, end, idx) {
  var root = idx;
  var left = 2 * idx + 1;
  var right = 2 * idx + 2;
  if (left <= end && arr[left] > arr[root]) {
    root = left;
  }
  if (right <= end && arr[right] > arr[root]) {
    root = right;
  }
  if (root != idx) {
    swap(arr, idx, root);
    heapify(arr, start, end, root);
  }
}

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

Kod Açıklamaları

Yukarıdaki kod, bir dizi elemanını Introsort algoritması kullanarak sıralar. introsort() işlevi, Introsort algoritması için gerekli olan maksimum derinlik değerini hesaplar ve ardından introsortHelper() işlevini çağırarak sıralama işlemini gerçekleştirir.

introsortHelper() işlevi, dizi elemanlarını QuickSort, HeapSort ve InsertionSort algoritmalarını kullanarak sıralar. İşlev, dizi elemanları belirli bir boyuta ulaştığında veya maksimum derinlik değerine ulaştığında sıralama işlemini durdurur.

medianOf3() işlevi, QuickSort algoritmasında kullanılan pivot elemanını belirlemek için kullanılır.

insertionSort() işlevi, belirli bir boyuta ulaşan alt dizileri sıralamak için kullanılır.

heapsort() işlevi, HeapSort algoritması kullanılarak alt dizileri sıralamak için kullanılır.

buildHeap() işlevi, HeapSort algoritması için bir heap oluşturmak için kullanılır.

heapify() işlevi, HeapSort algoritması için bir heap’ı yeniden düzenlemek için kullanılır.

swap() işlevi, iki dizi elemanını yer değiştirmek için kullanılır.

Örnek Kullanım

Örnek bir kullanım:

constarr = [5, 2, 9, 1, 5, 6, 3, 8, 0];
introsort(arr);
console.log(arr); // [0, 1, 2, 3, 5, 5, 6, 8, 9]

Yukarıdaki örnekte, introsort() işlevi, arr dizisini sıralar ve sonucu konsola yazdırır.

Sonuç

Introsort algoritması, birçok diğer sıralama algoritmasından daha hızlı ve daha verimlidir. Bu nedenle, özellikle büyük boyutlu dizileri sıralarken kullanılması önerilir.

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