it-swarm-tr.com

Neden quicksort mergesort'tan daha iyidir?

Röportaj sırasında bu soru soruldu. İkisi de O(nlogn) ve henüz çoğu kişi Mergesort yerine Quicksort kullanıyor. Neden?

344

Quicksort, O (n2) en kötü durum çalışma zamanı ve O (nkütüknortalama ortalama çalışma süresi. Bununla birlikte, birçok senaryoda sıralama birleştirmek üstündür çünkü birçok faktör bir algoritmanın çalışma zamanını etkiler ve hepsini bir araya getirirken quicksort kazanır.

Özellikle, sık sık alıntılanan sıralama algoritmaları çalışma zamanı, verileri sıralamak için yapılması gereken karşılaştırma sayısını veya takas sayısını ifade eder. Bu, özellikle de temel donanım tasarımından bağımsız olduğu için iyi bir performans ölçütüdür. Bununla birlikte, referans yeri gibi (başka bir deyişle, önbellekte bulunan birçok öğeyi okuyor muyuz?) Başka şeyler de mevcut donanım üzerinde önemli bir rol oynar. Özellikle Quicksort, çok az ek alan gerektirir ve iyi önbellek konumu sergiler ve bu da çoğu durumda birleştirme işleminden daha hızlı olmasını sağlar.

Ayrıca, quicksort’un en kötü durumdaki O çalışma süresinden kaçınmak çok kolaydır (n2(neredeyse tamamen uygun bir pivot seçimi kullanarak - rastgele seçmek gibi (bu mükemmel bir stratejidir).

Uygulamada, quicksort'un birçok modern uygulaması (özellikle libstdc ++ 'ın std::sort) aslında introsort , teorik olarak en kötü durumda O (=)nkütükn), birleştirme sıralama aynı. Özyineleme derinliğini sınırlandırarak ve günlüğü aştığında farklı bir algoritmaya ( heapsort ) geçerek bunu başarır.n.

258
Konrad Rudolph

Birçok kişinin belirttiği gibi, quicksort için ortalama vaka performansı mergesort'tan daha hızlıdır. Ama bu sadece talep üzerine herhangi bir hafızaya erişmek için sürekli zaman ayırdığınızı düşünüyorsanız geçerlidir.

RAM'da bu varsayım genellikle çok kötü değildir (önbelleklerden dolayı her zaman doğru değildir, ancak çok da kötü değildir). Bununla birlikte, eğer veri yapınız diskte yaşayacak kadar büyükse, o zaman ortalama diskiniz saniyede 200 rastgele arama gibi bir şey yaparsa quicksort öldürülür . . Ancak aynı disk, saniyede bir saniyede megabayt veri okuma veya yazma konusunda sorun yaşamaz. Mergesort'un yaptığı tam olarak budur.

Bu nedenle, verilerin diskte sıralanması gerekiyorsa, mergesort'ta gerçekten bazı varyasyonlar kullanmak istersiniz. (Genellikle alt listeleri hızlı bir şekilde konumlandırırsınız, daha sonra bunları bir boyut eşiğinin üstünde birleştirmeye başlarsınız.)

Ayrıca, bu büyüklükteki veri kümeleriyle herhangi bir şey yapmak zorundaysanız, diske bakmak istememeyi düşünün. Örneğin, veritabanlarında büyük veri yükleri yapmadan önce endeksleri düşürmeniz ve daha sonra dizini yeniden oluşturmanızın nedeni budur. Yük sırasında endeksin sürdürülmesi, sürekli olarak diske ulaşmak demektir. Buna karşılık, endeksleri düşürürseniz, veritabanı ilk önce ele alınacak bilgileri (elbette bir birleştirme noktası kullanarak!) Ve ardından dizin için BTREE veri yapısına yükleyerek dizini yeniden oluşturabilir. (BTREE'ler doğal olarak sırayla tutulduğundan, sıralı bir veri kümesinden birkaç diske bakma yoluyla birini yükleyebilirsiniz.)

Disk aramalarının nasıl önlenebileceğini anlamanın, veri işleme işlerini günler veya haftalar yerine saatlerce sürmeme izin verdiği bir çok olay oldu.

275
user11318

Aslında, QuickSort O (n2). Onun ortalama durum çalışma süresi O (nlog (n)), ancak (en kötü durum O (n2), birkaç benzersiz öğe içeren bir listede çalıştırdığınızda ortaya çıkar. Randomizasyon O (n) alır. Tabii ki, bu en kötü durumunu değiştirmez, sadece kötü niyetli bir kullanıcının sınıfınızı uzun süre almasını önler.

QuickSort daha popülerdir çünkü:

  1. Yerinde (MergeSort, sıralanacak öğe sayısına doğrusal ekstra bellek gerektiriyor).
  2. Küçük bir gizli sabiti vardır.
88
Dark Shikari

"ve yine de çoğu insan Mergesort yerine Quicksort kullanıyor. Neden bu?"

Belirtilmemiş olan psikolojik sebeplerden biri, Quicksort'un daha akıllıca adlandırılmış olmasıdır. yani iyi pazarlama.

Evet, üçlü ayrıştırma işlemine sahip Quicksort, muhtemelen en iyi genel amaçlı sıralama algoritmalarından biridir, ancak "Hızlı" sıralamanın "Birleştirme" sıralamasından çok daha güçlü sesler olduğu gerçeğini aşmaz.

29
Ash

Diğerlerinin de belirttiği gibi, en kötü Quicksort vakası O (n ^ 2) iken, birleşme noktası ve yığın noktası O'da kalmaktadır (nlogn). Bununla birlikte, ortalama bir durumda, üçü de O (nlogn); bu yüzden karşılaştırılabilir davaların büyük çoğunluğu içindir.

Quicksort'u ortalama olarak daha iyi yapan şey, iç döngünün birkaç değeri tek bir değerle karşılaştırmayı ima ettiği, diğer ikisinde de her karşılaştırma için farklı olduğu. Başka bir deyişle, Quicksort diğer iki algoritmanın yarısı kadar okuma yapar. Modern CPU'larda performans erişim zamanının ağır baskın olması nedeniyle, sonuçta Quicksort harika bir ilk tercih olmaktan çıkıyor.

15
Javier

Şimdiye kadar sözü edilen üç algoritmayı eklemek istiyorum (mergesort, quicksort ve yığın sıralama) sadece mergesort kararlı. Yani, aynı anahtara sahip olan değerler için sıra değişmez. Bazı durumlarda bu arzu edilir.

Ancak, gerçeği söylemek gerekirse, pratik durumlarda çoğu insanın sadece ortalama performansa ihtiyacı vardır ve quicksort… quick =)

Tüm sıralama algoritmalarının iniş ve çıkışları vardır. İyi bir genel bakış için sıralama algoritmaları için Wikipedia makalesi konusuna bakın.

8
Antti Rasinen

Quicksort'taki Wikipedia girişi :

Quicksort ayrıca, bir başka özyinelemeli sıralama algoritması olan mergesort ile rekabet eder, ancak en kötü durum olan Θ (nlogn) çalışma süresinin yararınadır. Mergesort, quicksort ve heatsort'tan farklı olarak sabit bir sıralamadır ve bağlantılı listelerde ve disk depolama veya ağa bağlı depolama gibi erişilmesi yavaş ortamlarda depolanan çok büyük listelerde çalışmak üzere kolayca uyarlanabilir. Her ne kadar hızlı bağlantı bağlantılı listelerde çalışmak üzere yazılabilse de, genellikle rastgele erişime sahip olmayan zayıf pivot seçeneklerinden muzdarip olacaktır. Mergesort'un ana dezavantajı, dizilerde çalışırken en iyi durumda Θ (n) yardımcı alan gerektirmesidir; oysa yerinde yerinde ayırma ve kuyruk özyinelemeli hızlı yuva varyantı sadece Θ (logn) boşluk kullanır. (Bağlantılı listelerde çalışırken, birleştirme işleminin yalnızca küçük ve sabit miktarda yardımcı depolama gerektirdiğini unutmayın.)

7
gnobal

Mu! Quicksort daha iyi değil, mergesort'tan farklı bir uygulama için çok uygun.

Mergesort, hızın özde olup olmadığını, en kötü durum performansının tolere edilemeyeceğini ve fazladan boş alan bulunduğunu düşünmeye değer . 1

Onların her ikisinin de O(nlogn) […] "olduğunu söylediniz. Bu yanlış. "Quicksort, en kötü durumda n = 2/2 karşılaştırması kullanır." 1 .

Ancak deneyimlerime göre en önemli özellik, programlama dillerini zorunlu paradigma ile kullanırken sıralama yaparken kullanabileceğiniz sıralı erişimin kolay uygulanmasıdır.

1 Sedgewick, Algoritmalar

7
Roman Glass

Quicksort pratikte en hızlı sıralama algoritmasıdır, ancak O (n2) kadar kötü performans göstermesini sağlayabilecek çok sayıda patolojik vakası vardır.

Yığının O (n * ln (n)) cinsinden çalışması garanti edilir ve sadece sonlu ek depolama gerektirir. Ancak, yığınlayıcının ortalamadan hızlı kürsüye göre çok daha yavaş olduğunu gösteren birçok gerçek dünya testinden alıntılar var.

6
Niyaz

Wikipedia'nın açıklaması:

Tipik olarak, quicksort pratikte diğer Θ (nlogn) algoritmalardan çok daha hızlıdır, çünkü iç döngüsü çoğu mimaride etkin bir şekilde uygulanabilir ve çoğu gerçek dünya verilerinde kuadratik zaman gerektirme olasılığını en aza indiren tasarım seçimleri yapmak mümkündür. .

Quicksort

mergesort

Mergesort için gerekli olan depolama miktarında da sorun var (which (n)). En kötü durumda, aynı miktarda algoritmik zamandır, ancak birleştirme işlemi daha fazla depolama gerektirir.

5
Mat Mannion

Hızlı bağlantı, birleştirme noktasından daha iyi değil. O (n ^ 2) (nadiren meydana gelen en kötü durum) ile quicksort, birleştirme türünün O(nlogn) değerinden potansiyel olarak çok daha yavaştır. Quicksort'un ek yükü daha azdır, bu nedenle küçük n ve yavaş bilgisayarlarla daha iyidir. Ancak, bilgisayarlar o kadar hızlıdır ki, bir birleşme biriminin ek yükü ihmal edilebilir düzeydedir ve çok yavaş bir üst-üste geçme riski çoğu durumda bir birleşme noktasının önemsiz yüküne ağır basar.

Ek olarak, bir mergesort, aynı anahtarlara sahip öğeleri orijinal sıralarında yararlı bir özellik olarak bırakır.

4
xpda

Neden Quicksort iyidir?

  • QuickSort en kötü durumda N ^ 2 ve ortalama ortalama NlogN alır. En kötü durum, veriler sıralandığında ortaya çıkar. Bu sıralama başlamadan önce rastgele karışık tarafından hafifletilebilir.
  • QuickSort, birleştirme sıralaması tarafından alınan ek belleği almaz.
  • Veri kümesi büyükse ve aynı öğeler varsa, Quicksort'un karmaşıklığı 3 yollu bölüm kullanarak azalır. Daha fazla özdeş madde yok daha iyi sıralama. Tüm öğeler aynıysa, lineer zamanda sıralar. [Bu, çoğu kütüphanede varsayılan uygulamadır]

Quicksort her zaman Mergesort'tan daha mı iyidir?

Pek sayılmaz.

  • Mergesort sabittir ancak Quicksort değildir. Dolayısıyla çıktıda kararlılığa ihtiyacınız varsa Mergesort'u kullanırsınız. Stabilite birçok pratik uygulamada gereklidir.
  • Hafıza bugünlerde ucuz. Bu nedenle, Mergesort tarafından kullanılan fazladan bellek uygulamanız için kritik değilse, Mergesort'u kullanmanın bir zararı yoktur.

Not: Java'da, Arrays.sort () işlevi, ilkel veri türleri için Quicksort'u ve nesne veri türleri için Mergesort'u kullanır. Nesneler ek yükü harcadığından, Mergesort için ek yükü biraz eklemek performans açısından herhangi bir sorun olmayabilir.

Referans : QuickraPort videolarını izleyin. (3. Hafta, Coursera'daki Princeton Algoritmaları Kurs

4

Birleştirme Sıralamasının aksine Hızlı Sıralama yardımcı bir boşluk kullanmaz. Oysa Birleştirme Sıralaması bir yardımcı alan O (n) kullanır. Ancak Merge Sort, O(nlogn) durumunun en kötü durum zaman karmaşıklığına sahipken, Hızlı Sıralamanın en kötü durum karmaşıklığı, dizi zaten sıralandığında gerçekleşen O (n ^ 2) olur.

3
Shantam Mittal

Cevap, ilkel değerler için DualPivotQuickSort ile getirilen değişikliklere bağlı olarak quicksort'a doğru hafifçe eğilecektir. Java 7 'de Java.util.Arrays ' da sıralama yapmak için kullanılır.

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

Java7 uygulamalarını burada bulabilirsiniz - http://grepcode.com/file/repository.grepcode.com/Java/root/jdk/openjdk/7-b147/Java/util/Arrays.Java

DualPivotQuickSort ile İlgili Daha Fazla Okuma - http://permalink.gmane.org/gmane.comp.Java.openjdk.core-libs.devel/2628

3
appbootup

Birleştirme-sıralamada, genel algoritma:

  1. Sol alt diziyi sırala
  2. Sağ alt diziyi sırala
  3. 2 sıralı alt diziyi birleştirme

En üst seviyede, 2 sıralı alt diziyi birleştirmek N elementleriyle uğraşmayı içerir.

Bunun altındaki bir seviye, 3. adımdaki her bir yineleme, N/2 öğeleriyle ilgilenmeyi içerir, ancak bu işlemi iki kez tekrarlamanız gerekir. Demek hala 2 * N/2 == N unsuruyla ilgileniyorsunuz.

Bunun altında bir seviye, 4 * N/4 == N öğeyi birleştiriyorsunuz, vb. Özyinelemeli yığındaki her derinlik, aynı derinlik çağrısı boyunca aynı sayıda öğeyi birleştirmeyi içerir.

Bunun yerine hızlı sıralama algoritmasını göz önünde bulundurun:

  1. Bir pivot noktası seç
  2. Pivot noktasını dizideki doğru yere, tüm küçük öğeler sola ve büyük öğeler sağa yerleştirin
  3. Sol alt diziyi sırala
  4. Sağ alt diziyi sırala

En üst düzeyde, bir dizi N boyutuyla uğraşıyorsunuz. Daha sonra bir pivot noktası seçtiniz, doğru pozisyona getirdiniz ve daha sonra algoritmanın geri kalanı için tamamen görmezden gelebilirsiniz.

Bunun altında bir seviye, birleşik N-1 boyutuna sahip 2 alt diziyle uğraşıyorsunuzdur (yani, önceki pivot noktasını çıkarın). Her bir alt dizi için bir pivot noktası seçersiniz, bu da 2 ek pivot noktası gösterir.

Bunun altında bir seviye, yukarıdaki gibi aynı nedenlerle N-3 birleşik boyutuna sahip 4 alt diziyle uğraşıyorsunuz.

Sonra N-7 ... Sonra N-15 ... Sonra N-32 ...

Özyinelemeli yığınızın derinliği yaklaşık olarak aynı kalır (logN). Birleştirme sıralamasıyla, özyinelemeli yığının her düzeyinde, her zaman bir N öğesi birleştirme işlemi yaparsınız. Hızlı sıralama olsa da, yığında aşağı indikçe uğraştığınız öğe sayısı azalır. Örneğin özyinelemeli yığının ortasındaki derinliğe bakarsanız, uğraştığınız öğelerin sayısı N - 2 ^ ((logN)/2)) == N - sqrt (N) olur.

Feragatname: Birleştirme sırasında, diziyi her seferinde tam olarak eşit parçalara böldüğünüz için özyinelemeli derinlik tam olarak logN olur. Hızlı sıralamada, pivot noktanız dizinin tam ortasında olma ihtimalinin düşük olması nedeniyle özyinelemeli yığınızın derinliği logN'den biraz daha büyük olabilir. Bu faktörün ve yukarıda açıklanan faktörün, algoritmanın karmaşıklığında ne kadar büyük bir rol oynadığını görmek için matematiği yapmadım.

3
RvPr

Quicksort daha iyi bir ortalama durum karmaşıklığına sahiptir, ancak bazı uygulamalarda yanlış seçimdir. Quicksort, hizmet reddi saldırılarına karşı savunmasızdır. Bir saldırgan sıralanacak girişi seçebiliyorsa, o zamanın en kötü durum karmaşıklığını alan bir kümeyi kolayca oluşturabilir (n ^ 2).

Mergesort'un ortalama vaka karmaşıklığı ve en kötü vaka karmaşıklığı aynıdır ve bu nedenle aynı sorunla karşılaşmaz. Birleştirme türünün bu özelliği aynı zamanda gerçek zamanlı sistemler için üstün bir seçimdir - tam olarak, çünkü çok daha yavaş çalışmasına neden olan patolojik durumlar yoktur.

Bu nedenlerden dolayı Mergesort'tan Quicksort'tan daha büyük bir hayranıyım.

2
Simon Johnson

İkisi de aynı karmaşıklık sınıfında olsalar da, ikisi de aynı çalışma zamanına sahip olduğu anlamına gelmez. Hızlı bağlantı, genellikle sıkı bir uygulamayı kodlamak daha kolay olduğundan ve yaptığı işlemler daha hızlı ilerleyebildiğinden, birleştirme bağlantısından daha hızlıdır. Bunun nedeni, hızlı bağlantı noktasının genellikle insanların birleştirme yerine kullanmak yerine daha hızlı olmalarıdır.

Ancak! Ben şahsen sık sık bir bağlantı noktası veya bir bağlantı noktası varyantı kullanacağım. Hatırlamak. Hızlı bağlantı sadece O (n log n) açık ortalama . En kötü durum, O (n ^ 2)! Mergesort her zaman O (n log n) 'dir. Gerçek zamanlı performansın veya yanıt verebilirliğin şart olduğu ve girdi verilerinizin kötü amaçlı bir kaynaktan gelebileceği durumlarda, düz hızlı erişim noktası kullanmamalısınız.

2
DJ Capelis

Hızlı sıralama en kötü durum O (n ^ 2), ancak ortalama durum tutarlı bir şekilde birleştirme sıralaması gerçekleştirir. Her algoritma O'dur (nlogn), fakat Büyük O hakkında konuşurken düşük karmaşıklık faktörlerini bıraktığımızı hatırlamanız gerekir. Hızlı sıralama, sabit faktörler söz konusu olduğunda, birleştirme sıralama konusunda önemli iyileştirmelere sahiptir.

Birleştirme sıralaması ayrıca O(2n) belleği gerektirir, oysa hızlı sıralama yapılabilir (yalnızca O (n) gerektirir). Bu, hızlı sıralamanın genellikle birleştirme sıralaması yerine tercih edilmesinin bir başka nedenidir.

Ekstra bilgi:

Pivot zayıf bir şekilde seçildiğinde, en hızlı sıralama en kötü durumudur. Aşağıdaki örneği düşünün:

[5, 4, 3, 2, 1]

Pivot gruptaki en küçük veya en büyük sayı olarak seçilirse, hızlı sıralama O (n ^ 2) olarak çalışır. Listenin en büyük veya en küçük% 25'inde olan elementi seçme olasılığı 0.5'tir. Bu da algoritmaya iyi bir pivot olma şansını 0,5 verir. Tipik bir pivot seçim algoritması kullanırsak (rastgele bir eleman seçmek), her bir pivot seçimi için iyi bir pivot seçme şansımız 0.5 olur. Büyük boyutta koleksiyonlar için her zaman zayıf bir pivot seçme olasılığı 0,5 * n'dir. Bu olasılığa göre, hızlı sıralama ortalama (ve tipik) durum için etkilidir.

2
Wade Anderson

Bu oldukça eski bir sorudur, ancak son zamanlarda bu konuyla ilgilendiğimden beri benim 2c:

Birleştirme sıralama ihtiyaçlarını ortalama ~ N log N karşılaştırması. Zaten (neredeyse) sıralanmış sıralama dizileri için bu 1/2 N log N'ye düşer, çünkü biz birleştirme (neredeyse) her zaman "sol" kısmı 1/2 N kez seçer ve sonra sadece sağ 1/2 N elemanlarını kopyalarız. Ek olarak, sıralanan girişin işlemcinin şube belirleyicisinin parlamasını sağladığını ancak neredeyse tüm dalları doğru tahmin ettiğini, böylece boru hattı durmalarını önlediğini tahmin edebiliyorum.

Ortalama olarak hızlı sıralama, ~ 1.38 N log N karşılaştırması gerektirir. Karşılaştırmalar bakımından zaten sıralanan dizilerden büyük ölçüde faydalanmamaktadır (ancak takaslar açısından ve muhtemelen CPU içindeki dal tahminleri açısından).

Oldukça modern işlemci üzerindeki kriterlerim aşağıdakileri gösteriyor:

Karşılaştırma işlevi bir geri çağırma işlevi olduğunda (qsort () libc uygulamasında olduğu gibi) quicksort, rasgele girdilerde% 15, 64 bit tamsayılar için önceden sıralanmış dizilerde% 30 daha yavaş olur.

Diğer taraftan, karşılaştırma bir geri arama değilse, benim deneyimim, hızlı desteğin birleştirme birimini% 25'e kadar geride bırakmasıdır.

Ancak, (büyük) dizinizin çok az benzersiz değeri varsa, birleştirme sıralaması her durumda quicksort üzerinden kazanç elde etmeye başlar.

Yani belki de sonuç şu: eğer karşılaştırma pahalıysa (örneğin, geri arama işlevi, dizeleri karşılaştırarak, bir yapının birçok bölümünü karşılaştırarak çoğunlukla ikinci bir üçüncü-üçüncü ile "eğer" fark yaratır) - şansınız daha iyi olacak birleştirme sıralama ile. Daha basit işler için quicksort daha hızlı olacaktır.

Daha önce söylenenlerin hepsi doğru olduğunu söyledi: - Quicksort N ^ 2 olabilir, ancak Sedgewick iyi bir randomize uygulamanın yıldırım çarpması durumunda dizilim sergileyen bir bilgisayarın daha fazla şansa sahip olduğunu iddia ediyor N ^ 2 - Mergesort fazladan boşluk gerektiriyor

2
virco

Her iki sıralama algoritmasını da denediğimde, özyinelemeli aramaların sayısını sayarak, quicksort tutarlı bir şekilde mergesorttan daha az özyinelemeli çağrılara sahiptir. Bunun nedeni, quicksort'un pivotları ve pivotların bir sonraki özyinelemeli çağrılara dahil edilmemesidir. Bu şekilde quicksort özyinelemeli temel duruma mergesort'tan daha hızlı ulaşabilir.

2
Aldian Fazrihady

Çabuk rakiplere küçük eklemeler çeşit birleştiriyor.

Ayrıca, sıralama öğelerinin türüne de bağlı olabilir. Maddelere, takas ve karşılaştırmalara erişim, düzlem bellekteki tam sayıları karşılaştırmak gibi basit işlemler değilse, birleştirme sıralama tercih edilebilir bir algoritma olabilir.

Örneğin, uzak sunucudaki ağ protokolünü kullanarak öğeleri sıralarız.

Ayrıca, "bağlantılı liste" gibi özel kaplarda, hızlı sıralama avantajı yoktur.
1. Bağlantılı listede birleştirme sıralama, ek bellek gerekmez. 2. Hızlı sıralamadaki öğelere erişim sıralı değildir (bellekte)

1
minorlogic

Söylemesi zor. MergeSort'un en kötüsü n (log2n) -n + 1, eğer n = 2 k ise (bu çoktan ispat ettim) doğrudur. Ve herhangi bir n için (n lg n - n + 1) ve (n lg n + n + O (lg n)). Fakat quickSort için en iyisi nlog2n'dir (n = 2 ^ k'ye eşittir). Mergesort'u quickSort ile bölerseniz, n sonsuz olduğunda 1 olur. MergeSort'un en kötü durumu, QuickSort'un en iyi durumundan daha iyidir, neden quicksort kullanıyoruz? Ama unutmayın, MergeSort yerinde değil, 2n memeroy alanı gerektiriyor. Ve MergeSort da birçok dizi kopya yapmamız gerekiyor. Algoritma analizine dahil etmeyin. Bir Word'de MergeSort, theroy'daki quicksort'tan gerçekten daha hassastır, ancak gerçekte, memeory alanını, dizi kopyasının maliyetini düşünmelisiniz, birleşme hızlı sıralamadan daha yavaştır. rastgele sınıf tarafından Java içinde 1000000 basamak verilmiş olan deneyi, ve birleşme noktasıyla 2610ms, quicksort ile 1370ms aldı.

1
Peter

Her şey eşit, çoğu insandan en uygun olanı kullanmalarını beklerdim ve bu qsort olma eğilimindedir (3). Bunun dışında quicksort'un dizilerde çok hızlı olduğu biliniyor, tıpkı mergesort'un listeler için ortak bir seçim olduğu gibi.

Merak ettiğim şey neden radix veya kova türünü görmenin bu kadar nadir olması. Onlar O (n), en azından bağlantılı listelerde ve tek gereken anahtarı bir sıra numarasına çevirmek için bir yöntem. (dizeleri ve yüzer sadece iyi çalışır.)

Sebebin bilgisayar biliminin nasıl öğretildiğiyle ilgisi olduğunu düşünüyorum. Algoritma analizinde öğretim görevlime bile O (n log (n)) 'den daha hızlı sıralama yapmanın mümkün olduğunu göstermek zorunda kaldım. (O (n log (n)) 'den daha hızlı sıralama yapamayacağınıza dair kanıtı vardı karşılaştırması .

Diğer yandan, kayan nokta tam sayı olarak sıralanabilir, ancak negatif sayıları sonradan döndürmeniz gerekir.

Düzenleme: Aslında, tam sayıları gibi tam sayıları sıralamak için daha da kötü bir yol: http://www.stereopsis.com/radix.html . Bit çevirme hilesinin gerçekte hangi sıralama algoritmasını kullandığınızdan bağımsız olarak kullanılabileceğini unutmayın ...

1
Anders Eurenius

Her ikisini de zaman ve mekan karmaşıklığını göz önünde bulundurun. Birleştirme sıralaması için: Zaman karmaşıklığı: O(nlogn), Alan karmaşıklığı: O (nlogn)

Hızlı sıralama için: Zaman karmaşıklığı: O (n ^ 2), Uzay karmaşıklığı: O (n)

Şimdi, ikisi de birer sahnede kazanıyor. Ancak, rastgele bir pivot kullanarak, hemen hemen her zaman Hızlı sıralama Zaman karmaşıklığını O'ya (nlogn) azaltabilirsiniz.

Bu nedenle, Birleştirme sıralama yerine birçok uygulamada Hızlı sıralama tercih edilir.

0
pankaj

Hızlı sıralama, yerinde sıralama algoritmasıdır, bu nedenle diziler için daha uygundur. Öte yandan, birleştirme sıralaması, fazladan O (N) depolanmasını gerektirir ve bağlantılı listeler için daha uygundur.

Dizilerden farklı olarak, sevilenler listesine O(1) boşluk ve O(1) zamanla ortadaki öğeleri ekleyebiliriz, bu nedenle birleştirme işleminde birleştirme işlemi herhangi bir işlem yapmadan gerçekleştirilebilir. Ekstra alan. Bununla birlikte, diziler için fazladan alan tahsis etmek ve yerinden çıkarmak, birleştirme türünün çalışma süresi üzerinde olumsuz bir etkiye sahiptir. Birleştirme sıralama ayrıca, çok rastgele bellek erişimi olmadan verilere sıralı olarak erişildiğinden bağlantılı listeleri de tercih eder.

Öte yandan, hızlı sıralama çok fazla rastgele hafıza erişimi gerektirir ve bir dizi ile bağlantılı listelerin gerektirdiği şekilde herhangi bir geçiş yapmadan doğrudan hafızaya erişebiliriz. Ayrıca diziler için kullanıldığında hızlı sıralama, diziler bellekte bitişik olarak depolandığından iyi bir referans lokasyonuna sahiptir.

Her iki sıralama algoritması da ortalama karmaşıklık O (NlogN) olsa da, genellikle sıradan işler için insanlar depolama için bir dizi kullanır ve bu nedenle hızlı sıralama tercih edilen algoritma olmalıdır.

EDIT: Birleştirme sıralama en kötü/en iyi/avg durumunun her zaman nlogn olduğunu öğrendim, ancak hızlı sıralama n2'den (öğeler zaten sıralandığında en kötü durum) nlogn'a (pivot her zaman diziyi ikiye böldüğünde avg/en iyi durum) arasında değişebilir yarımları).

0
Saad