QuickSort Algoritması JavaÖrnekli Senaryo

Hızlı Sıralama nedir?

Hızlı sıralama Karşılaştırmalı sıralama algoritmasıdır ve aşağıdaki adımları izler: Bölmek ve fethetmek Bu yaklaşım, bir elemanı pivot olarak seçer, diziyi pivot değerinden küçük değerler içeren bir kısma ve daha büyük değerler içeren bir kısma ayırır ve ardından tüm dizi sıralanana kadar her kısma aynı işlemi uygular.

Hızlı Sıralama (Quick Sort), her programlama dilinde en yaygın kullanılan sıralama algoritmalarından biridir. Eğer siz de yazarsanız... JavaSenaryoBüyük ihtimalle yerleşik özelliği zaten kullanmışsınızdır. çeşit() Bu yöntemi bildiğinize göre, ayrı bir Hızlı Sıralama uygulamasının neden öğrenilmeye değer olduğunu merak edebilirsiniz. Bunu cevaplamak için öncelikle sıralamanın ne anlama geldiğini ve varsayılan sıralamanın ne olduğunu bilmeniz gerekir. JavaSenaryo gerçekten de öyle yapıyor.

Hızlı Sıralama'yı tanımlayan üç özellik vardır:

• Yerinde: Orijinali yeniden düzenliyor dizi ve aynı boyutta ikinci bir dizi ayırmaz.
• Özyinelemeli: Her bölümleme, aynı fonksiyonla sıralanan iki küçük aralık üretir.
• Dengesiz: Aynı anahtara sahip iki öğe, başlangıçtaki göreli sıralamalarından farklı bir sıralamada sonuçlanabilir.

Sıralama Nedir?

Sıralama, öğeleri belirli bir düzende düzenlemek anlamına gelir. Bunu okulda neredeyse kesinlikle görmüşsünüzdür: sayıları en küçüğünden en büyüğüne doğru sıralamak... yükselen Sıralamak ve onları en büyükten en küçüğe doğru sıralamak Azalan Sıralama yalnızca sayılarla sınırlı değildir. Metinler alfabetik olarak, tarihler kronolojik olarak ve nesneler fiyat veya puan gibi seçtiğiniz herhangi bir alana göre sıralanabilir.

Sıralama önemlidir çünkü sıralı veriler daha hızlı işlemleri mümkün kılar. İkili arama O(log n) sürede çalışır, ancak bu yalnızca sıralı girdilerde geçerlidir. Veriler sıralı hale geldiğinde, yinelenen kayıtları kaldırma, aralık sorguları, sıralama ve birleştirme işlemleri çok daha ucuz hale gelir; bu nedenle her programlama dili en az bir sıralama rutini içerir.

Varsayılan Sıralama JavaSenaryo

Daha önce belirtildiği gibi, JavaKomut dosyası şunları sağlar: çeşit()Örneğin [5,3,7,6,2,9] gibi küçük bir diziyi artan sırada sıralamak istediğiniz şekilde alın. çeşit() Dizideki işlem tam olarak bunu yapıyor gibi görünüyor.

Yukarıdaki ekran görüntüsü, tarayıcı konsolunun sıralanmış diziyi yazdırdığını gösteriyor. İşte aynı kod:

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

Çıktı:

[ 2, 3, 5, 6, 7, 9 ]

Bu sonuç doğru, ancak tesadüfen doğru. Array.prototype.sort() her öğeyi bir dizeye dönüştürür ve dizeleri karşılaştırır. Bir karşılaştırma fonksiyonu sağlamadığınız sürece, bu dizideki her değer tek bir rakamdan oluştuğu için, dize sırası sayısal sırayla eşleşir. Verileri değiştirirseniz, yanılsama bozulur.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Çıktı:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

sort() fonksiyonu hangi algoritmayı kullanıyor?

Teknik şartnamede bir algoritma belirtilmediğinden, her motor kendi algoritmasını seçer. Modern motorların tamamı birleştirme tabanlı bir algoritma kullanır:

• V8 (Chrome, Edge, Node.js) kullanıldı. Sıralama V8 7.0 sürümünden itibaren Chrome 70 ile birlikte gönderiliyor.
• Örümcek maymunu (Firefox) kullanır birleştirme sırası.
• JavaScriptCore (Safari) ayrıca kullanır birleştirme sırası.

ES2019'dan beri bu dil şunu garanti ediyor: sort() is kararlıBu da motor içinde basit bir Hızlı Sıralama algoritmasını devre dışı bırakır. Birleştirme tabanlı sıralama O(n) yardımcı belleğe ihtiyaç duyar ve sizin fonksiyonunuzu çağırmalıdır. JavaHer bir karşılaştırma için komut dosyası karşılaştırıcısı. Elle yazılmış sayısal Hızlı Sıralama, sayıları doğrudan karşılaştırır ve yerinde sıralar, bu nedenle büyük sayısal dizilerde başarılı olabilir. Node.js 22'de 1,000,000 rastgele tamsayıyı sıralamak yaklaşık olarak şu kadar sürdü: 100 ms Aşağıdaki Hızlı Sıralama ile ve kabaca 210 ms 'da sort((a, b) => a - b).

Dolayısıyla, yerinde sıralama, bellek üzerinde sıkı kontrol veya sıralamanın nasıl çalıştığına dair sağlam bir anlayışa ihtiyaç duyduğunuzda Quick Sort yazmaya değer bir araçtır. Mekaniği detaylı olarak inceleyelim.

Hızlı Sıralama Nasıl Çalışır?

Hızlı Sıralama, temel bir işlemi tekrarlar; bu işleme "Hızlı Sıralama" denir. bölümlemeDaha küçük ve daha küçük aralıklarda. İşte adımlar sırasıyla:

1. Bul pivot dizideki öğe.
2. Sol fare işaretçisini aralığın ilk elemanından başlatın.
3. Sağ işaretçiyi aralığın son elemanından başlatın.
4. Sol işaretçideki elemanı pivot noktasıyla karşılaştırın. Eğer pivot noktasından küçükse, sol işaretçiyi bir adım sağa kaydırın. Sol eleman pivot noktasından büyük veya ona eşit olana kadar bu işleme devam edin.
5. Sağ işaretçideki elemanı pivot noktasıyla karşılaştırın. Eğer pivot noktasından büyükse, sağ işaretçiyi bir adım sola kaydırın. Sağdaki eleman pivot noktasından küçük veya ona eşit olana kadar bu işleme devam edin.
6. Sol işaretçi hala sağ işaretçiden küçük veya ona eşitse, iki elemanı yer değiştirin.
7. Sol işaretçiyi artırın ve sağ işaretçiyi azaltın.
8. Sol indeks hala sağ indeksten küçük veya ona eşitse, 4. adımdan itibaren tekrarlayın. Aksi takdirde, sol işaretçinin indeksini döndürün.

Yukarıdaki diyagram tracBu işaretçi hareketlerini örnek bir dizi üzerinde inceleyelim. Pivot değerinden küçük her eleman soluna, büyük her eleman ise sağına yerleşir; bu da tam olarak döndürülen indeksin işaretlediği şeydir. Aşağıdaki bölümde aynı dizi adım adım incelenmektedir.

Pivot Elemanının Belirlenmesi

Pivot seçimi, hızlı bir Quick Sort algoritmasını yavaş bir Quick Sort algoritmasından ayıran tek karardır. Eğer her zaman pivotu seçerseniz... ilk Sıralı bir dizide eleman eklenmesi, mümkün olan en kötü bölmeyi üretir: bir taraf boş, diğer tarafta ise kalan tüm elemanlar bulunur. Bu da algoritmayı O(n²) karmaşıklığına getirir. orta (Dizi uzunluğunun ikiye bölünmesiyle elde edilen) eleman, sıralı ve ters sıralı girdiler için bu tuzağı önler; bu nedenle aşağıdaki kod bunu kullanır.

Yaygın strateji değişiklikleri:

• İlk veya son unsur: Kodlaması en basit olanıdır, ancak sıralı verilerde O(n²) karmaşıklığına sahiptir.
• Orta eleman: Sıralı ve ters sıralı dizileri O(n log n) karmaşıklığında işleyen iyi bir varsayılan değer.
• Rastgele öğe: En kötü durum senaryosunun önceden oluşturulmasını imkansız hale getirir.
• Üçün ortalaması: İlk, orta ve son değerlerin medyanını alır; üretim kütüphanelerinde standart tercihtir.

Şimdi dizi üzerinde Hızlı Sıralama algoritmasını inceleyelim. [5,3,7,6,2,9].

1 ADIM: Pivot, ortadaki elemandır. Sol = 0 ve sağ = 5 olmak üzere, Math.floor((5 + 0) / 2) Bu, indeks 2'yi verir, dolayısıyla pivot değeri şudur: 7.

2 ADIM: İşaretçileri dizinin uçlarından başlatın. Sol işaretçi 0 indeksindedir (değer ). 5) ve sağ işaretçi 5. indekstedir (değer) 9).

3 ADIM: Soldaki değeri pivot ile karşılaştırın. 5 < 7, bu yüzden sağa doğru 1. indekse geçin. 3 < 7, bu yüzden sağa doğru 2. indekse geçin. Oradaki değer 7'dir ve bu değer pivottan küçük değildir, bu nedenle sol işaretçi 2. indekste durur.

4 ADIM: Sağdaki değeri pivot ile karşılaştırın. 9 > 7, bu yüzden sola doğru 4. indekse gidin. Oradaki değer 2'dir ve bu değer pivottan büyük değildir, bu nedenle sağdaki işaretçi 4. indekste durur.

5 ADIM: Sol indeks (2), sağ indeksten (4) küçük veya ona eşit olduğundan, iki değeri değiştirin. Dizi şu hale gelir: [5,3,2,6,7,9].

6 ADIM: Her iki işaretçiyi de bir adım içeri doğru hareket ettirin. Sol işaretçi artık 3. indekste, sağ işaretçi de 3. indekste.

7 ADIM: Tarama işlemini tekrarlayın. 3. indeksteki değer 6'dır ve 6 < 7 olduğundan sol işaretçi 4. indekse ilerler. 3. indeksteki değer pivot değerinden büyük olmadığı için sağ işaretçi 3. indekste kalır.

8 ADIM: Sol indeks (4) artık sağ indeksten (3) büyük olduğundan döngü sona erer ve fonksiyon geri döner. 44. indeksten önceki her şey pivot değerinden küçük veya ona eşittir ve 4. indeksten sonraki her şey pivot değerinden büyük veya ona eşittir.

Bu kılavuza göre, iki işlem için koda ihtiyacınız var: takas (swap).ping iki öğe ve bir aralığın bölümlere ayrılması.

Code İkiyi Değiştirmek Numbers in JavaSenaryo

Yukarıdaki editör ekran görüntüsünde de görüldüğü gibi, takas yardımcısı iki dizindeki değerleri değiştirmek için geçici bir değişken kullanır. Diziyi doğrudan değiştirir ve hiçbir şey döndürmez.

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

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Çıktı:

[ 9, 3, 7, 6, 2, 5 ]

Code Bölme işlemini gerçekleştirmek

Yukarıdaki ekran görüntüsündeki kod, 1'den 8'e kadar olan adımları bir fonksiyona dönüştürüyor. İki iç içe geçmiş kısım... döngüler İşaretçileri ilerlet, if Blok takas işlemini gerçekleştirir ve fonksiyon, bölme indeksini döndürür.

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;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Çıktı:

[ 5, 3, 2, 6, 7, 9 ]
4

Çıktı, kılavuzdaki adım adım açıklamalarla birebir örtüşüyor: bir bölümleme işleminden sonra dizi [5,3,2,6,7,9] oluyor ve döndürülen bölme indeksi 4.

Özyinelemeli işlemi gerçekleştirin Operayon

Bölme işlemi bölme indeksini döndürdükten sonra, bu indeksi kullanarak aralığı bölün ve her bir yarıya Hızlı Sıralama algoritmasını uygulayın. Bu nedenle Böl ve Yönet algoritması olarak adlandırılır. Özyineleme, her alt aralık tek bir eleman içerene kadar devam eder; bu noktada tüm dizi sıralanmış olur.

Not: Hızlı Sıralama, işlem boyunca aynı diziyi kullanır. İşlem sırasında yeni diziler oluşturulmaz, bu da onu yerinde sıralama algoritması yapar.

Yani siz arıyorsunuz bölüm () Yukarıda açıklanan fonksiyonu kullanın ve dönüş değerini bölmek için kullanın. dizi Parçalara ayırmak için işte kod:

Ekran görüntüsünde vurgulanan iki koruma koşuluna dikkat edin. left < index - 1 Sol tarafta en az iki unsurun kaldığını doğrular ve index < right Sağ taraf için de aynı durum geçerlidir. Bu koruma mekanizmaları olmasaydı, fonksiyon tek elemanlı aralıklarda sonsuza kadar kendini tekrar tekrar çağırırdı.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Çıktı:

[ 2, 3, 5, 6, 7, 9 ]

Hızlı Sıralamayı Tamamla Code

Takas, bölümleme ve özyineleme parçalarını bir araya getirmek, tam uygulamayı verir:

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); // swapping 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);

Çıktı:

[ 2, 3, 5, 6, 7, 9 ]

Yukarıdaki ekran görüntüsü, düzenleyicideki programın tamamını ve konsoldaki sıralanmış diziyi göstermektedir. Bu uygulama, önceden sıralanmış bir diziye, ters sıralanmış bir diziye, yinelenen ve aynı değerler içeren dizilere, negatif sayılara, tek bir elemana ve boş bir diziye karşı doğrulanmış ve her durumda doğru sonucu vermiştir.

Hızlı Sıralama Algoritmasının Zaman ve Alan Karmaşıklığı

Her bölümleme işlemi aralıktaki her elemana bir kez dokunur, bu nedenle tek bir işlemin maliyeti O(n)'dir. Dolayısıyla toplam maliyet, aralıklar önemsiz hale gelmeden önce dizinin kaç kez bölünebileceğine bağlıdır.

Alan karmaşıklığı O(log n)'dir. Bu yerinde sürüm için. İkinci bir dizi tahsis edilmediğinden, tek ekstra bellek özyineleme yığınıdır ve dengeli bölme, bu yığını yaklaşık log₂(n) çerçeve derinliğinde tutar. En kötü durumda yığın O(n) çerçeveye kadar büyür, bu nedenle çok büyük diziler çağrı yığınını aşabilir.

Bu durumu somutlaştıran iki sayı var. Yukarıdaki kodla 4,096 rastgele değeri sıralamak, teorik n·log₂(n) değeri olan 49,152'ye karşılık yaklaşık 65,000 karşılaştırma kullandı ve en derin özyineleme 24 kareye ulaştı, oysa log₂(4096) 12'dir. Her iki rakam da O(n log n) algoritmasından beklenen küçük sabit faktör içinde yer almaktadır.

Hızlı Sıralama ve Diğer Sıralama Yöntemleri Karşılaştırması Algorithms

Hızlı Sıralama (Quick Sort) nadiren tek seçenektir. Aşağıdaki tablo, karşılaşmanız muhtemel diğer algoritmalarla karşılaştırmasını sunarak, verileriniz için doğru olanı seçmenize yardımcı olur.

Hızlı Sıralama (Quick Sort) genellikle pratikte kazanır çünkü iç döngüsü sıkıdır ve önbellek dostu bitişik aralıklarda çalışır. Garantili O(n log n) sınırı veya kararlı bir sıralama gerektiğinde birleştirme sıralamasını (merge sort), bellek son derece kısıtlı olduğunda yığın sıralamasını (heap sort) ve çok küçük veya neredeyse sıralı diziler için ekleme sıralamasını (insertion sort) seçin. Üretim kütüphaneleri sıklıkla bunları birleştirir: introsort, Hızlı Sıralama ile başlar, özyineleme çok derinleşirse yığın sıralamasına geçer ve küçük aralıklarda ekleme sıralamasıyla (insertion sort) biter.

Nesneleri ve Dizeleri Hızlı Sıralama Nasıl Yapılır?

Şimdiye kadar gösterilen uygulama, değerleri karşılaştırıyor. < hem de >Bu durum, sıralama işlemini sayılarla sınırlandırır. Gerçek uygulamaların sıralama yapması gerekir. nesneler Bir özelliğe, alfabetik sıraya göre dizelere veya kronolojik sıraya göre tarihlere göre sıralama yapılabilir. Çözüm, karşılaştırmayı tıpkı yerleşik işlev gibi bir geri çağırma fonksiyonuna taşımaktır. sort() yapar.

Karşılaştırıcı iki değer alır ve birinci değerin önce gelmesi gerektiğinde negatif bir sayı, ikinci değerin önce gelmesi gerektiğinde pozitif bir sayı ve ikisi eşit olduğunda sıfır döndürür. Sabit kodlanmış iki karşılaştırmayı karşılaştırıcı çağrılarıyla değiştirmek, algoritmanın herhangi bir veri türünde çalışmasını sağlar.

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

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

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Çıktı:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Üç ayrıntıya dikkat çekmekte fayda var. Özyinelemeli koruma artık şu şekilde: left >= rightBu, herhangi bir aralık için doğrudur ve dış dizinin uzunluğuna bağlı değildir. Dize karşılaştırması şunu kullanır: localeCompare() Böylece aksanlı karakterler ve büyük/küçük harf duyarlılığı, ham kod noktası yerine doğru şekilde işlenir. Ayrıca Hızlı Sıralama kararlı olmadığından, aynı maaşa sahip kayıtlar yer değiştirebilir; orijinal sıralama sizin için önemliyse, ikinci bir belirleyici anahtar kullanarak sıralama yapın.

Devam etmeye hazır mısınız? Temellerinizi şu şekilde güçlendirin: JavaSenaryo tanıtımıİşaretçi mekaniği üzerinde pratik yapın. JavaKomut dosyası döngüleridaha fazlasını çalışarak pratik JavaKomut dosyası kod örnekleriUygulamaları karşılaştırın Ekleme Sıralaması hem de Yığın Sıralamaveya bu algoritmaya statik türler ekleyin. TypeScript referans.

SSS