JavaScript'te QuickSort Algoritması

Hızlı Sıralama nedir?

Hızlı Sıralama algoritması, Böl ve Fethet yaklaşımını izler. Öğeleri bazı koşullara göre daha küçük parçalara ayırır ve bölünmüş olan daha küçük parçalar üzerinde sıralama işlemlerini gerçekleştirir.

Hızlı Sıralama algoritması, herhangi bir programlama dilinde en çok kullanılan ve popüler algoritmalardan biridir. Ancak, bir JavaScript geliştiricisiyseniz, JavaScript'te zaten mevcut olan sort () ' i duymuş olabilirsiniz . Sonra, bu Hızlı Sıralama algoritmasının ne olduğunu düşünmüş olabilirsiniz. Bunu anlamak için, önce sıralamanın ne olduğuna ve JavaScript'te varsayılan sıralamanın ne olduğuna ihtiyacımız var.

Sıralama nedir?

Sıralama, öğeleri istediğimiz sıraya göre düzenlemekten başka bir şey değildir. Buna okul veya üniversite günlerinde rastlamış olabilirsin. Sayıları küçükten büyüğe (artan) veya büyükten küçüğe (azalan) düzenlemek gibi şimdiye kadar gördüğümüz şeydi ve buna sıralama denir.

JavaScript'te varsayılan sıralama

Daha önce belirtildiği gibi, JavaScript'in sort () özelliği vardır . [5,3,7,6,2,9] gibi birkaç dizi elemanlı bir örnek alalım ve bu dizi elemanlarını artan sırada sıralamak istiyoruz. Öğeler dizisinde sort () işlevini çağırmanız yeterlidir ve dizi öğelerini artan sırada sıralar.

Kod:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

JavaScript'te varsayılan sıralama () yerine Hızlı sıralamayı seçmenin nedeni nedir?

Sort () istediğimiz sonucu verse de, sorun dizi öğelerini sıralama yöntemiyle ilgilidir. Standart sıralama () JavaScript kullanan yerleştirme tür tarafından Chrome'un V8 Engine ve sıralama Birleştirme tarafından Mozilla Firefox ve Safari .

Ancak, çok sayıda öğeyi sıralamanız gerekiyorsa, bu uygun değildir. Dolayısıyla çözüm, büyük veri kümesi için Hızlı sıralamayı kullanmaktır.

Dolayısıyla, tam olarak anlamak için Hızlı sıralamanın nasıl çalıştığını bilmeniz ve şimdi bunu ayrıntılı olarak görmemize izin vermeniz gerekir.

Hızlı sıralama nedir?

Hızlı sıralama, Böl ve Fethet algoritmasını izler . Öğeleri bazı koşullara göre daha küçük parçalara bölmek ve bölünmüş olan daha küçük parçalar üzerinde sıralama işlemlerini gerçekleştirmektir. Bu nedenle, büyük veri kümeleri için iyi çalışır. İşte Hızlı sıralamanın basit kelimelerle nasıl çalıştığı adımları.

Önce pivot öğe olarak adlandırılacak bir öğe seçin .
Daha sonra, tüm dizi öğelerini seçili pivot öğesiyle karşılaştırın ve bunları, pivot öğesinden daha küçük öğeler solunda ve pivottan daha büyük olan öğeler sağda olacak şekilde düzenleyin.
Son olarak, pivot elemanının sol ve sağ tarafındaki elemanlarda aynı işlemleri gerçekleştirin.

İşte bu, Hızlı sıralamanın temel taslağıdır. Hızlı sıralama yapmak için tek tek izlenmesi gereken adımlar şunlardır.

QuickSort nasıl çalışır?

Önce dizideki "pivot" öğesini bulun .
Sol işaretçiyi dizinin ilk öğesinden başlatın.
Sağ işaretçiyi dizinin son öğesinden başlatın.
Sol işaretçiyi gösteren öğeyi karşılaştırın ve pivot öğesinden küçükse, sol işaretçiyi sağa hareket ettirin (soldaki dizine 1 ekleyin). Sol taraftaki öğe pivot öğesinden büyük veya ona eşit olana kadar buna devam edin.
Sağ işaretçiyi gösteren öğeyi karşılaştırın ve pivot öğesinden büyükse, sağ işaretçiyi sola hareket ettirin (1'i sağdaki dizine çıkarın). Sağ taraftaki öğe pivot öğesinden küçük veya ona eşit olana kadar buna devam edin.
Sol işaretçinin sağ işaretçiden küçük veya ona eşit olup olmadığını kontrol edin, ardından öğeleri bu işaretçilerin konumlarında görün.
Sol işaretçiyi artırın ve sağ işaretçiyi azaltın.
Sol işaretçinin dizini hala sağ işaretçinin dizininden küçükse, işlemi tekrarlayın; aksi takdirde sol işaretçinin dizinini döndürür.

Öyleyse bu adımları bir örnekle görelim. Sıralamamız gereken elemanların [5,3,7,6,2,9] olduğunu düşünelim.

Pivot elemanını belirle

Ancak Hızlı sıralama ile ilerlemeden önce, pivot elemanının seçilmesi önemli bir rol oynar. İlk öğeyi pivot öğesi olarak seçerseniz, sıralanan dizide en kötü performansı verir. Bu nedenle, her zaman orta elemanı (dizinin uzunluğu bölü 2) pivot eleman olarak seçmeniz önerilir ve biz de aynısını yapıyoruz.

Bir örnekle [5,3,7,6,2,9] gösterilen Hızlı sıralamayı gerçekleştirmek için adımlar aşağıda verilmiştir.

ADIM 1: Orta eleman olarak pivotu belirleyin. Yani, 7 pivot unsurdur.

ADIM 2: Sırasıyla dizinin ilk ve son elemanları olarak sol ve sağ işaretçileri başlatın. Yani, sol işaretçi işaret ediyor 5 0 dizininde ve sağ işaretçi işaret ediyor 9 endeksinde 5 de.

ADIM 3: Sol işaretçideki öğeyi pivot öğesi ile karşılaştırın. O zamandan beri, 5 <6, soldaki imleci sağa, 1. dizine kaydırır.

ADIM 4: Şimdi, hala 3 <6, bu yüzden sol işaretçiyi sağa doğru bir indeks daha kaydırın. Öyleyse şimdi 7> 6 sol işaretçiyi artırmayı durdurun ve şimdi sol işaretçi dizin 2'de.

ADIM 5: Şimdi, sağ işaretçideki değeri pivot öğesiyle karşılaştırın. 9> 6'dan beri sağ işaretçiyi sola hareket ettirin. Şimdi 2 <6 olarak sağ işaretçiyi hareket ettirmeyi bırak.

ADIM 6: Sol ve sağ işaretçilerde bulunan her iki değeri birbiriyle değiştirin.

ADIM 7: Her iki işaretçiyi bir adım daha hareket ettirin.

ADIM 8: 6 = 6 olduğundan, işaretçileri bir adıma daha taşıyın ve sol işaretçi sağ işaretçiyi geçerken ve sol işaretçinin dizinine dönerken durun.

Bu nedenle, burada yukarıdaki yaklaşıma dayanarak, yukarıdaki adımlarda bahsedildiği gibi öğeleri takas etmek ve diziyi bölümlemek için kod yazmamız gerekiyor.

JavaScript'te iki sayıyı değiştirmek için kod:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Bölümü yukarıdaki adımlarda belirtildiği gibi gerçekleştirmek için kod:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Özyinelemeli işlemi gerçekleştirin

Yukarıdaki adımları gerçekleştirdikten sonra, sol işaretçinin dizini döndürülür ve diziyi bölmek ve bu kısımda Hızlı sıralamayı gerçekleştirmek için bunu kullanmamız gerekir. Bu nedenle, Divide and Conquer algoritması olarak adlandırılır.

Bu nedenle, sol dizi ve sağ dizideki tüm öğeler sıralanana kadar Hızlı sıralama gerçekleştirilir.

Not: Hızlı sıralama aynı dizide gerçekleştirilir ve işlemde yeni dizi oluşturulmaz.

Dolayısıyla, yukarıda açıklanan bu partition () ' ı çağırmalıyız ve buna dayanarak diziyi parçalara böleriz. İşte onu kullandığınız kod,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Hızlı sıralama kodunu tamamlayın:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]