Sortieren von 10 Millionen Objekten in O (n) Zeit und O (1) extra Speicher

Question

Ich versuche eine Antwort auf eine Interviewfrage zu finden, die ich kürzlich bekommen habe, aber nicht lösen konnte. Ich wurde gebeten, 10 Millionen Objekte (jede enthält eine 10-Bit-Ganzzahl und einen eindeutigen Zeichenfolgenwert) durch die 10-Bit-Ganzzahl an Ort und Stelle mit O (1) Leerzeichen und O (n) Zeit zu sortieren. Für alle intensiven Zwecke erschwert der String-Wert das Problem, aber Sie sortieren die Objekte nicht danach.

Ich dachte an zählende Sortierung jedoch, das würde nur funktionieren, wenn ich nur die 10-Bit-Ganzzahlen sortierte. Das Sortieren der Objekte macht die Dinge etwas komplizierter, da ich ihre eindeutigen String-Werte verfolgen muss. Ich habe Radix sort betrachtet, aber es scheint O (n) als Worst-Case zu verwenden.

Gibt es eine Art von Sorte, die ich vermisse?

Answer 1

There's an in-place (MSB) radix sort.

Es geht ungefähr so:

• beginnt mit dem ersten Bit.

• Verschieben Sie alle Elemente mit diesem Bit gleich 0 nach links und alle diejenigen mit diesem Bit gleich 1 auf der rechten Seite.

  Sie tun dies ähnlich wie Quicksort, indem Sie von beiden Seiten in die Mitte gehen und 1 auf der linken Seite mit 0 auf der rechten Seite tauschen.

• Recurse auf der linken Seite und der rechten Seite unter Berücksichtigung des nächsten Bits.

Der Prozess geht ungefähr so:

 ↓    ↓ 
     0...    1... 
--------------- --------------- 
    ↓  ↓  ↓  ↓ 
00... 01... 10... 11... 
------- ------- ------- ------- 
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 
000 001 010 011 101 110 110 111 
--- --- --- --- --- --- --- --- 
... 

Die Zeitkomplexität ist O(bits*n) und der Raum Komplexität ist O(bits).

Also mit einer konstanten Anzahl von Bits ist die Komplexität der Zeit O(n) und die Raumkomplexität ist O(1).

---

---

Es ist auch möglich, dies mit Countingsort zu tun (mit der gleichen Zeit und Raum Komplexität).

• Zählen Sie, wie viele von jedem Element es gibt.
• Mit diesem können Sie bestimmen, wo im Array diese Elemente angezeigt werden sollen.

• Erstellen Sie eine Nachschlagetabelle (Zuordnungsindex zum Offset, kann ein Array sein), der alle oben genannten Startpunkte enthält, die verwendet werden, um zu bestimmen, wohin das nächste Element gehen soll.

• Jetzt durchlaufen Sie das Array und tauschen jedes Element aus, das nicht an der ersten Stelle ist, an die es gehen kann. Dann machen Sie dasselbe mit jedem Element, das wir vertauscht haben, bis das aktuelle Element dort ist, wo es hingehört.

  Erhöhen Sie den relativen Offset des relevanten Elements in der Nachschlagetabelle mit jedem Schritt.

  Beachten Sie, dass es nicht möglich ist, das gleiche Element zweimal zu vertauschen, daher ist dies eine lineare Zeit.

Das ist alles sehr verwirrend klingt, also hier ein Beispiel:

4 5 3 1 2 3 4 4 1 5 4 3 2 3 

// counts: 
1: 2, 2: 2, 3: 4, 4: 4, 5: 2 

// the starting points (offsets) based on the counts: 
1 at position 0 
2 at position (offset of 1)+(count of 1) = 0+2 = 2 
3 at position (offset of 2)+(count of 2) = 2+2 = 4 
4 at position (offset of 3)+(count of 3) = 4+4 = 8 
5 at position (offset of 4)+(count of 4) = 8+4 = 12 

// sorting: 
4 5 3 1 2 3 4 4 1 5 4 3 2 3 // out of place, swap with offsets[4] = 8 (offsets[4]++) 
^ 

1 5 3 1 2 3 4 4 4 5 4 3 2 3 // in correct position, moving on   (offsets[1]++) 
^ 

1 5 3 1 2 3 4 4 4 5 4 3 2 3 // swap with offsets[5] = 12    (offsets[5]++) 
^

1 2 3 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 2    (offsets[2]++) 
^

1 3 2 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[3] = 4    (offsets[3]++) 
^

1 2 2 1 3 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 3    (offsets[2]++) 
^

1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on   (offsets[1]++) 
^

1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on   (offsets[2]++) 
    ^

Sie erhalten die Idee ...

Beachten Sie, dass die Größe der Zählertabelle und die Lookup-Tabelle O(max value) sind , die O(1) ist, wenn jede Nummer eine feste Anzahl von Bits enthält.

Und Sie tun eine konstante Menge an Arbeit für jedes Element, so dass O(n) Zeit ist.

Answer 2

Mit dem Standard-Quicksort-Pivot-Code können Sie alle Elemente mit der Ganzzahl 0 an den Anfang des Arrays verschieben. Fahren Sie mit 1, 2, 3 usw. auf den verbleibenden Elementen fort und stoppen Sie, sobald Sie 1023 geschwenkt haben.

Dies iteriert 1024 Mal durch das Array, und jeder Pivot benötigt O (n) Zeit Auf).

Ein sehr ähnlicher Ansatz, der in der Praxis effizienter ist, ist die Verwendung eines standardmäßigen Dreiwege-Quicksort-Algorithmus. Man würde normalerweise annehmen, dass dies die Zeit O (n log n) nimmt und im schlimmsten Fall O (log n) -Raum verwendet. Aber hier ist der Bereich der Ganzzahlen auf 1024 Werte beschränkt, so dass er garantiert in O (n) -Zeit endet und O (1) -Raum verwendet, da in jedem rekursiven Aufruf von Quicksort ein Pivot-Wert niemals zweimal verwendet wird.

[Diese Antwort macht eine Annahme - dass "10 Millionen" in der Frage ist n, und dass "10 Bits" fest bleibt].