Waarom zou snel sorteren beter zijn dan sorteren samenvoegen?
Antwoord 1, autoriteit 100%
Normaal gesproken is quicksort aanzienlijk
sneller in de praktijk dan andere Θ(nlogn)
algoritmen, omdat de binnenste lus kan
efficiënt worden geïmplementeerd op de meeste
architecturen, en in de meeste real-world
gegevens, is het mogelijk om ontwerp te maken
keuzes die de kans minimaliseren
van het vereisen van kwadratische tijd.
Merk op dat de zeer lage geheugenvereiste ook een groot pluspunt is.
Antwoord 2, autoriteit 66%
Snel sorteren is doorgaans sneller dan samenvoegen wanneer de gegevens in het geheugen worden opgeslagen. Wanneer de dataset echter enorm is en wordt opgeslagen op externe apparaten zoals een harde schijf, is merge sort de duidelijke winnaar in termen van snelheid. Het minimaliseert het dure lezen van de externe schijf en leent zich ook goed voor parallel computergebruik.
Antwoord 3, autoriteit 53%
Voor samenvoegen is de sortering in het slechtste geval O(n*log(n)), voor Snel sorteren: O(n2). Voor andere gevallen (gem, best) hebben beide O(n*log(n)). Snel sorteren is echter een ruimteconstante waarbij Samenvoegen sorteren afhangt van de structuur die u sorteert.
Zie deze vergelijking.
Je kunt het ook visueelzien.
Antwoord 4, autoriteit 10%
Terwijl QuickSort vaak een betere keuze is dan Sorteren, zijn er zeker timpen bij het samenvoegen van sorteren is erotisch een betere keuze. De meest voor de hand liggende tijd is dat het uiterst belangrijk is dat uw algoritme sneller loopt dan O (N ^ 2). QuickSort is meestal sneller dan dit, maar gezien de theoretische slechtste input, kan het in O (N ^ 2) draaien, wat erger is dan de slechtst mogelijke samenvoeging.
QuickSort is ook ingewikkelder dan MERGESS, vooral als u een echt solide implementatie wilt schrijven, en dus als u op het gebied van eenvoud en onderhoudbaarheid streeft, wordt SCOOP Sorteer een veelbelovend alternatief met zeer weinig prestatieverlies.
Antwoord 5, Autoriteit 9%
Ik wilde persoonlijk het verschil testen tussen snel sorteren en sorteren sorteren en zag de looptijden voor een monster van 1.000.000 elementen.
Snelle sortering was in staat om het te doen in 156 milliseconden overwegende dat
samenvoegen sorteren hetzelfde in 247 milliseconden
De snelle sorteergegevens was echter willekeurig en snel sorteren presteert goed als de gegevens willekeurig zijn, waar het niet het geval is met samenvoeging sorteren. D.voorbeeld Sorteren, ongeacht of gegevens worden gesorteerd of niet.
Maar sorteren sorteren vereist een volledige extra ruimte en snelle soort is niet als een in-place sort
Ik heb een uitgebreid werkprogramma voor hen geschreven, ook illustratieve foto’s.
Antwoord 6, Autoriteit 5%
Naast de anderen: Sorteer sorteren is zeer efficiënt voor onveranderlijke datastructuur zoals gekoppelde lijsten en is daarom een goede keuze voor (puur) functionele programmeertalen.
Een slecht geïmplementeerde quicksort kan een beveiligingsrisicozijn.
Antwoord 7, autoriteit 5%
Quicksort is aanwezig. U hoeft alleen de gegevensposities te wisselen tijdens de Partitioneringsfunctie.
Mergesort vereist veel meer gegevens kopiëren. Je hebt nog een tijdelijke opslag nodig (meestal
dezelfde grootte als uw oorspronkelijke gegevensarray) voor de functie Samenvoegen.
Antwoord 8, autoriteit 3%
quicksort heet niet voor niets zo,
hoogtepunten :
beide zijn stabiele soorten, (gewoon een implementatie-overlast), dus laten we verder gaan met de complexiteit
het is erg verwarrend met alleen de big-oh-notaties die worden gemorst en “misbruikt”, beide hebben een gemiddelde hoofdlettercomplexiteit van 0(nlogn),
maar merge sort is altijd 0(nlogn) , terwijl quicksort voor slechte partities, dat wil zeggen scheve partities zoals 1 element-10 element (wat kan gebeuren als gevolg van gesorteerde of omgekeerd gesorteerde lijst) kan leiden tot een 0(n^2) ..
.. en dus hebben we gerandomiseerde quicksort , waarbij we de spil willekeurig kiezen en dergelijke scheve partities vermijden, waardoor het hele n ^ 2-scenario teniet wordt gedaan
hoe dan ook, zelfs voor matig scheve partities zoals 3-4 , hebben we een nlog(7/4)n,
idealiter willen we 1-1 partitie , dus de hele 2 van O(nlog(2)n).
dus het is O(nlogn) , bijna altijd en in tegenstelling tot merge sort zijn de constanten die verborgen zijn onder de “big-oh” notatie beter voor quicksort dan voor mergesort ..en het neemt geen extra ruimte in beslag zoals merge sort.
p>
maar om quicksort perfect te laten werken, moet je het aanpassen, herformuleren, quicksort biedt je mogelijkheden om te tweaken ….
Antwoord 9, autoriteit 3%
Het antwoord zou enigszins kantelen in de richting van quicksort met betrekking tot wijzigingen die zijn aangebracht met DualPivotQuickSort voor primitieve waarden. Het wordt gebruikt in JAVA 7om te sorteren in java.util.Arrays
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.
U kunt hier de Java7-implementatie vinden – http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/Util/arrays.java
Verdere ontzagwekkende aflezing op DUALPIVOTQUICKSORT – http: // Permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
Antwoord 10, Autoriteit 2%
Het is niet waar dat QuickSort beter is. Ook is het afhankelijk van wat u betert, geheugenverbruik of snelheid.
In termen van het geheugenconsumptie, in het slechtste geval, maar Quicksort kan N ^ 2 geheugen gebruiken (d.w.z. elke partitie is 1 tot N-1), terwijl SCOOP-sortering NLOGN gebruikt.
Het bovenstaande volgt in termen van snelheid.
Antwoord 11
Quicksort is op zijn plaats. Je hebt heel weinig extra geheugen nodig. Wat extreem belangrijk is.
Goede keuze aan mediaan maakt het nog efficiënter, maar zelfs een slechte keuze aan mediaan quarantees theta (NLOGN).