Was ist der schnellste Sortieralgorithmus für ein Array von ganzen Zahlen?

Ich bin während meines Gymnasialstudiums auf viele Sortieralgorithmen gestoßen. Ich weiß jedoch nie, welche (für ein zufälliges Array von ganzen Zahlen) die schnellste ist. Meine Fragen sind also:

• Welches ist der schnellste derzeit bekannte Sortieralgorithmus?
• Ist es theoretisch möglich, dass es noch schnellere gibt? Also, was ist die geringste Komplexität beim Sortieren?

Im Allgemeinen gibt es die -Sortierungsalgorithmen wie Einfügesortierung, Blasensortierung und Auswahlsortierung, die Sie normalerweise nur unter bestimmten Umständen verwenden sollten. Quicksort, das im schlimmsten Fall aber häufig mit guten Konstanten und Eigenschaften ist und als Allzweck-Sortierverfahren verwendet werden kann; die -Algorithmen wie Merge-Sort und Heap-Sort, die auch gute Allzweck-Sortieralgorithmen sind; und den - oder linearen Sortieralgorithmus für Listen mit ganzen Zahlen, z. B. Radix, Bucket und Zählsortierungen, der je nach Art der ganzen Zahlen in Ihren Listen geeignet sein kann.$O(n^2)$$O(n^2)$$O(n\log n)$$O(n\log n)$$O(n)$

Wenn die Elemente in Ihrer Liste so beschaffen sind, dass Sie nur die Gesamtordnungsbeziehung zwischen ihnen kennen, haben optimale Sortieralgorithmen die Komplexität . Dies ist ein ziemlich cooles Ergebnis, für das Sie online problemlos Details finden sollten. Die linearen Sortieralgorithmen nutzen mehr Informationen über die Struktur der zu sortierenden Elemente als nur die Gesamtordnungsbeziehung zwischen den Elementen.$\Omega(n\log n)$

Noch allgemeiner hängt die Optimalität eines Sortieralgorithmus stark von den Annahmen ab, die Sie über die Art der zu sortierenden Listen treffen können (sowie von dem Maschinenmodell, auf dem der Algorithmus ausgeführt wird, was selbst ansonsten zu einer schlechten Sortierung führen kann) Algorithmen sind die beste Wahl. Erwägen Sie die Blasensortierung auf Maschinen mit einem Band zur Speicherung. Je stärker Ihre Annahmen sind, desto mehr Ecken kann Ihr Algorithmus abschneiden. Unter sehr schwachen Annahmen darüber, wie effizient Sie die "Sortierbarkeit" einer Liste bestimmen können, kann die optimale Worst-Case-Komplexität sogar Sein .$\Omega(n!)$

Diese Antwort befasst sich nur mit Komplexitäten. Die tatsächlichen Laufzeiten von Implementierungen von Algorithmen hängen von einer Vielzahl von Faktoren ab, die in einer einzigen Antwort nur schwer zu berücksichtigen sind.

Die Antwort lautet, wie so oft, "es kommt darauf an". Es hängt von Dingen wie (a) wie groß die ganzen Zahlen sind, (b) ob das Eingabearray ganze Zahlen in zufälliger Reihenfolge oder in nahezu sortierter Reihenfolge enthält, (c) ob der Sortieralgorithmus stabil sein muss oder nicht, sowie andere Faktoren, (d) ob die gesamte Liste der Nummern in den Speicher passt (In-Memory-Sortierung im Vergleich zur externen Sortierung) und (e) den Computer, auf dem Sie sie ausführen.

In der Praxis ist der Sortieralgorithmus in der Standardbibliothek Ihrer Sprache wahrscheinlich ziemlich gut (nahezu optimal), wenn Sie eine speicherinterne Sortierung benötigen. Verwenden Sie daher in der Praxis einfach die von der Standardbibliothek bereitgestellte Sortierfunktion und messen Sie die Laufzeit. Nur wenn Sie feststellen, dass (i) das Sortieren einen großen Teil der Gesamtlaufzeit ausmacht und (ii) die Laufzeit inakzeptabel ist, sollten Sie sich die Mühe machen, mit dem Sortieralgorithmus herumzuspielen. Wenn diese beiden Bedingungen tun halten, dann können Sie auf die spezifischen Aspekte Ihrer bestimmten Domain suchen und mit anderen schnellen Sortieralgorithmen experimentieren.

In der Praxis ist der Sortieralgorithmus jedoch realistisch gesehen selten ein wesentlicher Leistungsengpass.

Beantworten Sie außerdem Ihre zweite Frage

Ist es theoretisch möglich, dass es noch schnellere gibt?
Also, was ist die geringste Komplexität beim Sortieren?

Für die allgemeine Sortierung beträgt die Komplexität des vergleichsbasierten Sortierproblems Ω (n log n) . Es gibt einige Algorithmen, die eine Sortierung in O (n) durchführen, aber alle basieren auf Annahmen über die Eingabe und sind keine Allzweck-Sortieralgorithmen.

Grundsätzlich ergibt sich die Komplexität aus der minimalen Anzahl von Vergleichen, die zum Sortieren des Arrays erforderlich sind (log n steht für die maximale Höhe eines binären Entscheidungsbaums, der beim Vergleichen der einzelnen Elemente des Arrays erstellt wird).

Den formalen Nachweis für die Sortierung der Komplexität finden Sie hier :

Der schnellste Ganzzahl-Sortieralgorithmus, der mir im schlimmsten Fall begegnet ist, ist der von Andersson et al. Es hat einen Worst-Case von , der natürlich schneller ist als O ( n log n ) .$O(n\log\log n)$$O(n\log n)$

Ich habe die beiden anderen Antworten zum Zeitpunkt des Schreibens durchgelesen, und ich dachte, keine der beiden Antworten hat Ihre Frage angemessen beantwortet. Andere Antworten betrachteten irrelevante Vorstellungen über zufällige Verteilungen und Raumkomplexität, die für ein Abitur wahrscheinlich nicht in Frage kommen. Also hier ist meine Einstellung.

$A$$n$$(n-1)$$A$$(n-1)$$\Omega(n)$$O(n)$$\Omega(n)$

$\Omega(n)$$O(n)$$n$$2n$$3n-5$$1$$n^2$

$\log(n!)$

$\Omega(n)$

Da Sie keine Hardwareeinschränkungen erwähnen und nach "den schnellsten" Ausschau halten, sollten Sie einen der Algorithmen für die parallele Sortierung auswählen, die auf der verfügbaren Hardware und der Art Ihrer Eingaben basieren.

In der Theorie zB quick_sortist O(n log n). Bei pProzessoren sollte dies idealerweise der Fall sein, O(n/p log n)wenn wir es parallel ausführen.

Wikipedia zitieren: Zeitkomplexität von ...

Optimale parallele Sortierung ist O (log n)

In der Praxis ist dies O(log n)aufgrund von Skalierbarkeitsproblemen bei großen Eingabegrößen nicht möglich .

Hier ist der Pseudocode für die parallele Zusammenführungssortierung . Die Implementierung von merge()kann dieselbe sein wie bei der normalen Zusammenführungssortierung:

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid = ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Siehe auch:

• Welcher parallele Sortieralgorithmus weist die beste durchschnittliche Fallleistung auf?
• https://en.wikipedia.org/wiki/Sorting_algorithm - Es gibt Links zu parallelen Versionen vieler Sortieralgorithmen.