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

Quickselect Sort Algoritması

Quickselect, bir dizideki sıralanmamış öğelerin sıralanmasını sağlayan bir sıralama algoritmasıdır. Quickselect, aynı zamanda Quick sort algoritmasından esinlenilmiştir ve birçok durumda daha hızlı bir şekilde çalışır. Bu algoritma, ortalamada O(n) zaman karmaşıklığına sahiptir ve O(n^2) gibi en kötü durumda ise nadiren gerçekleşir.

Javascript Quickselect Sort Algoritması Kodu

Aşağıda, Quickselect algoritması ile ilgili bir örnek javascript kodu ve açıklamalar yer almaktadır:

function quickselect(arr, k) {
  if (arr.length === 0 || k < 1 || k > arr.length) {
    return null;
  }

  const pivot = arr[Math.floor(Math.random() * arr.length)];
  const left = [];
  const right = [];
  const equal = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] === pivot) {
      equal.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  if (k <= left.length) {
    return quickselect(left, k);
  } else if (k <= left.length + equal.length) {
    return pivot;
  } else {
    return quickselect(right, k - left.length - equal.length);
  }
}

Kod Açıklamaları

Bu kod parçası, quickselect() fonksiyonunu tanımlar. Bu fonksiyon, bir dizideki k numaralı sıralanmamış öğeyi seçmek için kullanılır. Dizi, arr parametresiyle geçirilir.

İlk olarak, özel durumlar kontrol edilir. Dizi boş ise veya k sıfırdan küçük veya dizinin uzunluğundan büyükse, null değeri döndürülür.

Daha sonra, pivot adlı bir değişken tanımlanır ve dizinin rastgele bir öğesi ile atanır. Bu, sıralama işlemi için bir referans noktası olarak kullanılacaktır.

Daha sonra, left, right ve equal adlı üç boş dizi tanımlanır. Bu diziler, pivot değerine göre solda, sağda veya eşit olan öğeleri saklamak için kullanılacaktır.

for döngüsü, dizideki her öğeyi kontrol eder ve pivot değerine göre ilgili diziye ekler.

Son olarak, k ile left dizisinin uzunluğu karşılaştırılır. Eğer k left dizisinin uzunluğundan küçük veya eşitse, quickselect() fonksiyonu left dizisi ve k parametresi ile tekrar çağrılır. Eğer k left dizisinin uzunluğu ve equal dizisinin uzunluğu toplamından küçük veya eşitse, pivot değeri döndürülür. Eğer k bu iki sayının toplamından büyükse, quickselect() fonksiyonu right dizisi ve k parametresinin left ve equal dizilerinin uzunluklarından çıkarılmış değeri ile tekrar çağrılır.

Zaman Karmaşıklığı

Bu algoritma, daha önce belirtildiği gibi, ortalama O(n) zaman karmaşıklığına sahiptir ve n’ye bağlı olarak daha iyi performans gösterir. Bu algoritma, genellikle en iyi sonucu veren diğer seçim algoritmalarından daha hızlıdır ve n’ye bağlı olarak en kötü durumlarda bile O(n²)’den daha kötü bir performans göstermez.

Örnek Kullanım

Örnek bir kullanım aşağıdaki gibidir:

const arr = [7, 2, 8, 1, 4, 9];
const k = 3;

const result = quickselect(arr, k);
console.log(result); // 4

Bu örnekte, arr dizisi [7, 2, 8, 1, 4, 9] değerlerine sahiptir. k değişkeni 3’tür, yani 3. sıralanmamış öğeyi seçmek istiyoruz. quickselect() fonksiyonu, 3. sıralanmamış öğe olan 4 değerini döndürür.

Sonuç

Quickselect, birçok durumda etkili bir seçim algoritmasıdır. Bu algoritmanın performansı, dizinin boyutuna ve öğelerin dağılımına bağlıdır. Ancak, ortalama durumda hızlı bir şekilde çalışması nedeniyle, birçok uygulamada kullanışlıdır.

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