QuickSort Algoritması JavaSenaryo

Sıralama Nedir?

Sıralama, öğeleri istediğimiz sıraya göre düzenlemekten başka bir şey değildir. Okul veya üniversite günlerinizde bununla karşılaşmış olabilirsiniz. Sayıları küçükten büyüğe (artan) veya büyükten küçüğe (azalan) sıralamak gibi, şimdiye kadar gördüğümüz buna sıralama denir.

Varsayılan sıralama JavaSenaryo

Daha önce belirtildiği gibi, JavaKomut dosyası var çeşit(). [5,3,7,6,2,9] gibi birkaç elemanlı dizi içeren bir örnek alalım ve bu dizinin elemanlarını artan düzende sıralamak isteyelim. Sadece ara çeşit() items dizisinde bulunur ve dizi elemanlarını artan düzende sıralar.

Kodu:

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

Varsayılan sıralama () yerine Hızlı sıralamayı seçmenin nedeni nedir? JavaSenaryo

sort() istediğimiz sonucu vermesine rağmen sorun, dizi elemanlarını sıralama şeklindedir. Varsayılan sort() JavaKomut dosyası kullanımları ekleme türü by Chrome'un V8 Motoru ve Sıralamayı birleştir by mozilla Firefox ve Safari.

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

Yani tam olarak anlamak için Hızlı sıralamanın nasıl çalıştığını bilmeniz ve bunu şimdi ayrıntılı olarak görmemiz gerekiyor.

Hızlı sıralama nedir?

Hızlı sıralama aşağıdaki gibidir Bölmek ve fethetmek algoritma. Elemanların belirli koşullara göre daha küçük parçalara bölünmesi ve bölünen bu parçalar üzerinde sıralama işlemlerinin yapılmasıdır. 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ığına ilişkin adımlar.

1. İlk önce şu şekilde çağrılacak bir öğe seçin: pivot eleman.
2. Daha sonra, tüm dizi elemanlarını seçilen pivot elemanla karşılaştırın ve bunları, pivot elemandan küçük olan elemanlar solda ve pivot elemandan büyük olan elemanlar sağda olacak şekilde düzenleyin.
3. Son olarak pivot elemanının sol ve sağ yan elemanlarında da aynı işlemleri yapın.

İşte Hızlı sıralamanın temel taslağı budur. Hızlı sıralama işlemini gerçekleştirmek için tek tek izlenmesi gereken adımlar şunlardır.

QuickSort nasıl çalışır?

1. İlk önce şunu bul "eksen" dizideki öğe.
2. Sol işaretçiyi dizinin ilk elemanından başlatın.
3. Sağ işaretçiyi dizinin son öğesinden başlatın.
4. Sol işaretçiyi işaret eden öğeyi karşılaştırın ve pivot öğesinden küçükse, sol işaretçiyi sağa hareket ettirin (sol dizine 1 ekleyin). Sol taraftaki eleman pivot elemanından büyük veya ona eşit olana kadar buna devam edin.
5. 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 (sağ dizinden 1 çıkarın). Sağ taraftaki eleman pivot elemanından küçük veya ona eşit olana kadar buna devam edin.
6. Sol işaretçinin sağ işaretçiden küçük veya ona eşit olup olmadığını kontrol edin, ardından bu işaretçilerin konumlarındaki öğeleri değiştirin.
7. Sol işaretçiyi artırın ve sağ işaretçiyi azaltın.
8. Sol işaretçinin indeksi hala sağ işaretçinin indeksinden küçükse işlemi tekrarlayın; aksi takdirde sol işaretçinin dizinini döndürür.

Şimdi bu adımları bir örnekle görelim. Sıralamamız gereken eleman dizisini [5,3,7,6,2,9] ele alalım.

Pivot öğesini belirleyin

Ancak Hızlı sıralamaya geçmeden önce pivot öğesinin seçilmesi önemli bir rol oynar. Pivot eleman olarak ilk elemanı seçerseniz, sıralanan dizide en kötü performansı verir. Bu nedenle, pivot eleman olarak her zaman ortadaki elemanın (dizinin uzunluğunun 2'ye bölümü) seçilmesi tavsiye edilir ve biz de aynısını yaparız.

Burada bir örnekle gösterilen Hızlı sıralamayı gerçekleştirme adımları verilmiştir [5,3,7,6,2,9].

1 ADIM: Pivotu orta eleman olarak belirleyin. Bu yüzden, 7 pivot elemanıdır.

2 ADIM: Sol ve sağ işaretçileri sırasıyla dizinin ilk ve son öğeleri olarak başlatın. Yani sol işaretçi şunu gösteriyor 5 0 dizininde ve sağ işaretçi şunu gösteriyor 9 indeks 5'te.

3 ADIM: Sol işaretçideki öğeyi pivot öğesiyle karşılaştırın. Çünkü, 5 < 6 işaretçiyi sola, sağa, indeks 1'e kaydırır.

4 ADIM: Şimdi hala 3 <6 olduğundan sol işaretçiyi sağa doğru bir dizine daha kaydırın. Yani şimdi 7 > 6 sol işaretçiyi artırmayı bırakın ve şimdi sol işaretçi dizin 2'de.

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

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

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

8 ADIM: 6 = 6 olduğundan, işaretçileri bir adım daha hareket ettirin ve sol işaretçi sağ işaretçiyi geçerken durun ve sol işaretçinin indeksini döndürün.

Dolayısıyla burada yukarıdaki yaklaşıma dayanarak, yukarıdaki adımlarda belirtildiği gibi elemanların yerini değiştirmek ve diziyi bölümlemek için kod yazmamız gerekiyor.

İki sayıyı değiştirmek için kod JavaSenaryo

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

Yukarıdaki adımlarda belirtildiği gibi bölümü gerçekleştirecek kod

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

Özyinelemeli işlemi gerçekleştirin

Yukarıdaki adımları gerçekleştirdiğinizde, sol işaretçinin dizini döndürülecektir ve bunu diziyi bölmek ve o kısımda Hızlı sıralama yapmak için kullanmamız gerekir. Bu nedenle Böl ve Fethet algoritması olarak anılır.

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

Not: Hızlı sıralama aynı dizi üzerinde gerçekleştirilir ve süreçte yeni dizi oluşturulmaz.

Yani bunu aramamız gerekiyor bölüm () yukarıda açıkladık ve buna dayanarak bölüştük dizi parçalara ayrılır. İşte onu kullanacağınız kod:

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var 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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

NOT: Hızlı sıralama, Zaman Karmaşıklığı ile çalışır O(nlogn).