Können Sie n ganze Zahlen in O (n) amortisierte Komplexität sortieren?

Jede Seite auf den Intertubes, die sich mit vergleichsbasierten Sortierungen beschäftigt sagt Ihnen , dass Sie nicht können Sortiert schneller als O(n lg n) mit Vergleichssorten. Das heißt, wenn Ihr Sortieralgorithmus die Reihenfolge bestimmt, indem Sie zwei Elemente miteinander vergleichen, können Sie nichts Besseres tun. Beispiele sind Quicksort, Bubblesort, Mergesort.

Einige Algorithmen, wie z. B. count sort oder bucket sort oder radix sort, verwenden keine Vergleiche. Sie stützen sich stattdessen auf die Eigenschaften der Daten selbst, wie den Wertebereich in den Daten oder die Größe des Datenwerts.

Diese Algorithmen können schnellere Komplexitäten haben. Hier ist ein Beispielszenario:

  

Sie sortieren 10^6 ganze Zahlen, und jede ganze Zahl liegt zwischen 0 und 10 . Dann kannst du einfach die Anzahl der Nullen, Einsen, Zweien usw. zählen und sie in sortierter Reihenfolge wieder ausspucken. So funktioniert countsort, in O(n + m) , wobei m die Anzahl der Werte ist, die Ihr Datum annehmen kann (in diesem Fall m=11 ).

Ein anderer:

  

Sie sortieren 10^6 binäre Zeichenfolgen, die höchstens aus 5 Zeichen bestehen. Sie können die Radix-Sortierung dafür verwenden: Teilen Sie sie zuerst in zwei Buckets auf, je nach ihrem ersten Zeichen, und sortieren Sie sie dann nach dem zweiten, dritten, vierten und fünften Zeichen. Solange jeder Schritt eine stabile Sortierung ist, sollten Sie eine perfekt sortierte Liste in O(nm) erhalten, wobei m die Anzahl der Ziffern oder Bits in Ihrem Datum ist (in diesem Fall m=5 ).

Aber im allgemeinen Fall können Sie nicht schneller als O(n lg n) sortieren (indem Sie eine Vergleichssortierung verwenden).

Ich bin nicht ganz glücklich mit der bisher akzeptierten Antwort. Also versuche ich eine Antwort:

  

Ist es theoretisch möglich, ein Array von n ganzen Zahlen in einer amortisierten Komplexität von O (n) zu sortieren?

Die Antwort auf diese Frage hängt von der Maschine ab, die den Sortieralgorithmus ausführen würde. Wenn Sie eine Maschine mit wahlfreiem Zugriff haben, die genau 1 Bit verarbeiten kann, können Sie radix sort für ganze Zahlen höchstens verwenden k bits, was bereits vorgeschlagen wurde. Sie enden also mit der Komplexität O(kn) .
Wenn Sie jedoch auf einer Word-Maschine mit fester Größe und einer Wortgröße von mindestens k bits arbeiten (was alle Consumer-Computer sind), erreichen Sie O(n log n) am besten. Dies liegt daran, dass entweder log n < k oder Sie zuerst count sort erstellen und dann mit einem O (n log n) -Algorithmus sortieren können würde auch den ersten Fall ergeben.

  

Was ist mit dem Versuch, einen schlimmsten Fall von O (n) Komplexität zu erzeugen?

Das ist nicht möglich. Ein Link wurde bereits gegeben. Die Idee des Beweises ist, dass, um sortieren zu können, man sich für jedes Element entscheiden muss, das sortiert wird, wenn es größer oder kleiner als jedes andere zu sortierende Element ist. Durch die Verwendung von Transitivität kann dies als Entscheidungsbaum dargestellt werden, der bestenfalls n nodes und log n depth hat. Wenn Sie also eine bessere Leistung als Ω(n log n) erzielen möchten, müssen Sie Kanten aus diesem Entscheidungsbaum entfernen. Aber wenn der Entscheidungsbaum nicht vollständig ist, wie können Sie dann sicherstellen, dass Sie eine richtige Entscheidung über einige Elemente getroffen haben a und b ?

  

Können Sie ohne Einschränkung der Speichernutzung einen solchen Algorithmus erstellen?

So wie von oben ist das nicht möglich. Und die restlichen Fragen sind daher nicht relevant.

Wenn die ganzen Zahlen in einem begrenzten Bereich sind, dann würde ein "Sortieren" von O (n) beinhalten, dass ein Bitvektor von "n" Bits ... die fraglichen ganzen Zahlen durchlaufen und das n% 8 Bit setzen würde Versetzen Sie n // 8 in diesem Byte-Array auf true. Das ist eine "O (n)" -Operation. Eine weitere Schleife über dieses Bitfeld zum Auflisten / Aufzählen / Zurückgeben / Drucken aller gesetzten Bits ist ebenfalls eine O (n) -Operation. (Natürlich wird O (2n) zu O (n) reduziert.)

Dies ist ein Spezialfall, bei dem n klein genug ist, um in den Speicher oder in eine Datei zu passen (mit Suchvorgängen ()). Es ist keine allgemeine Lösung; aber es ist in Bentleys "Programming Pearls" beschrieben --- und war angeblich eine praktische Lösung für ein Problem der realen Welt (mit etwas wie eine "Freelist" von Telefonnummern) ... etwas wie: Suche die erste verfügbare Telefonnummer, die könnte einem neuen Abonnenten ausgestellt werden).

(Anmerkung: log (10 * 10) ist ~ 24 Bits, um jede mögliche ganze Zahl mit einer Länge von bis zu 10 Stellen darzustellen ... also gibt es viel Platz in 2 * 31 Bits eines typischen Unix / Linux-Speichermapping mit maximalem Umfang).

Ich glaube, Sie suchen radix sort .