Sortieren einer Liste von Zeichenfolgen in lexikografischer Reihenfolge der sortierten Zeichenfolgen

Sei eine Sammlung von Zeichenfolgen über dem Alphabet , die insgesamt Symbole enthalten .$A$$\{0,\ldots,m-1\}$$n$

Ihre Aufgabe ist es, jede der Zeichenfolgen intern zu sortieren und dann die resultierenden Zeichenfolgen in lexikografischer Reihenfolge zu sortieren. (Ihr Algorithmus muss nicht so funktionieren.)

Beispiel:

Eingabe: 33123 15 1 0 54215 21 12

Ausgabe: 0 1 12 12 12333 12455 15

Ich habe einen Weg gefunden, dies in Zeit und Raum zu tun .$O(m+n)$$O(mn)$

Der Speicherplatz ist größer als die Zeit, da ich ein intelligentes Array verwende, mit dem Sie ein Array mit der Größe erstellen und allen Zellen in Anfangswerte geben können .$n$$O(1)$

Ich habe die Bucket-Sortierung verwendet, um jede Zeichenfolge ( Zeit und Raum) und Wortbäume zu sortieren, um die Sammlung selbst ( Zeit und Raum) zu sortieren . aber meine lösung ist zu kompliziert.$O(m+n)$$A$$O(m+n)$$O(mn)$

Hat jemand eine bessere Lösung mit Zeit und weniger Platz oder schneller als ?$O(m+n)$$O(m+n)$

Die Lösung muss deterministisch sein, damit keine Hash-Maps oder andere statistische Algorithmen verwendet werden

Meine Lösung: Ein Smart Array ist ein Array der Größe das wir in erstellen und "initialisieren" können :$m$$O(1)$

Wir erstellen drei Arrays mit der Größe von ohne eines davon zu initialisieren, und wir behalten auch eine einzelne ganzzahlige Variable namens .$m$$C$

Das erste Array enthält die Daten. Das zweite Array enthält Zeiger auf eine Zelle im dritten Array. Das dritte Array enthält Zeiger auf eine Zelle im zweiten Array. enthält die Anzahl der bisher initialisierten Zellen.$C$

Angenommen, wir möchten den Wert von Zelle festlegen (nehmen wir an, es ist das erste Mal, dass wir dies für diese Zelle tun). Dann gehen wir zu Zelle im ersten Array und setzen sie auf den gewünschten Wert.$i$$i$

Jetzt gehen wir zu Zelle im zweiten Array und setzen sie so, dass sie auf Zelle im dritten Array zeigt. Stellen Sie die Zelle im dritten Array so ein, dass sie auf die Zelle im zweiten Array zeigt. Erhöhen Sie um 1.$i$$C$$C$$i$$C$

Angenommen, wir möchten wissen, ob Zelle Papierkorb ist (das heißt, wir müssen noch etwas darauf einstellen).$j$

Wir würden zu Zelle im zweiten Array gehen und uns die Zellennummer (im dritten Array) ansehen, auf die Zelle (im zweiten Array) zeigt - wir werden es .$j$$j$$k$

Wenn dann ist Papierkorb (weil wir bisher nur Zellen initialisiert haben und keine davon ist).$k>C$$j$$C$$j$

Wenn ist, schauen wir uns an, auf welche Zelle (im dritten Array) zeigt. Wenn es nicht dann ist Müll. Sonst ist kein Müll$k<C$$k$$j$$j$$j$

Auf diese Weise können wir bei jedem Schritt feststellen, ob wir diese Zelle initialisiert haben und wenn nicht. Also haben wir ein Array der Größe in -Zeit erstellt und "initialisiert" .$m$$O(1)$

Der Haupttrick besteht nicht darin, das gesamte Array zu Beginn zu initialisieren, sondern einen Weg zu finden, um zu wissen, welche Zellen wir bisher initialisiert haben, und eine Zelle nur dann zu initialisieren, wenn wir sie "betrachten". Im RAM-Modell benötigt Zeit, um ein Array beliebiger Größe zu erstellen, ohne es zu initialisieren.$O(1)$

Ein Wortbaum der Ordnung m ist eine Verallgemeinerung einer TRIE. Jeder Knoten enthält ein Array von Zeigern auf seine Söhne. Die Arraygröße beträgt . Jeder Knoten enthält auch einen Zähler, der angibt, wie viele Sätze von diesem Knoten beschrieben werden.$m$

Da wir jedes Mal, wenn wir ein Wort (eine Menge) hinzufügen, intelligente Arrays verwenden, werden nur Zeit und Raum benötigt.$A$$O(|A|)$$O(m|A|)$

Sie können dies auch in Zeit und Raum lösen :$O(n \log n)$$O(n)$

• Sortieren Sie zuerst jedes Wort mit Mergesort. Die Laufzeit hierfür beträgt höchstens , und die Speicherplatznutzung beträgt .$O(n \log n)$$O(n)$

• Speichern Sie dann alle Wörter in einem Wortversuch. Die Zeit und der Raum dafür sind , wenn Sie das Wort trie richtig implementieren. Insbesondere sollten Sie an jedem Knoten des Versuchs die untergeordneten Gruppen als Hashtabelle (nicht als Array) speichern. Auf diese Weise ist der Speicher an einem Knoten proportional zur Anzahl der untergeordneten Knoten, und die Suche nach einem untergeordneten Element kann in -Zeit erfolgen. Somit ist die Laufzeit dieser Stufe Zeit und Raum.$O(n)$$O(1)$$O(n)$$O(n)$

• Lesen Sie zum Schluss alle Wörter aus dem Versuch vor. Dazu müssen Sie jede Hashtabelle nehmen und ihren Inhalt sortieren, beispielsweise mithilfe von Mergesort. Alle diese Sortierschritte dauern höchstens .$O(n \log n)$

Die resultierende Datenstruktur scheint recht einfach zu sein. Es ist besonders einfach, wenn Sie in einer Sprache implementieren, die integrierte Unterstützung für Hashmaps bietet (z. B. Javascript, Python).

Alternativ können Sie die Hashmap durch eine ausgeglichene Binärbaumdatenstruktur ersetzen und eine ähnliche Laufzeit erhalten.

Als allgemeine Anmerkung zu "Smart Arrays":

Sie können Ihre Verwendung von "Smart Arrays" durch eine Hashtabelle ersetzen. Auf diese Weise behalten Sie die Fähigkeit, (erwartete) Lese- und Schreibvorgänge durchzuführen. Anstatt , speichern Sie insbesondere den Wert am Schlüssel (dh fügen Sie die Zuordnung zur Hashtabelle hinzu). Wenn Sie den Wert von lesen möchten, suchen Sie stattdessen in der Hashtabelle und geben alles zurück, was Sie dort finden. Auf diese Weise ist die Speicherplatznutzung proportional zur Anzahl der initialisierten Einträge im "Smart Array", und jeder Zugriff benötigt (erwartete) Zeit.$O(1)$$A[i] := v$$v$$k$$k \mapsto v$$A[i]$$i$$O(1)$

Sie können eine Menge von Zeichenfolgen über ein ganzzahliges Alphabet der Größe sortieren, indem Sie einen Versuch in Zeit und Raum verwenden, wobei die Unterscheidung ist Präfix von .$S$$\{0,1,\dots,\sigma-1\}$$\sigma$$O(d\sigma)$$d$$S$

Hier ist eine Lösung, bei der keine Hash-Tabellen verwendet werden.

Sei die Länge des kürzesten Präfixes der Zeichenfolge , das sie von den anderen Zeichenfolgen in . Das Unterscheidungspräfix von ist definiert als .$d_s$$s \in S$$S$$S$$d = \sum_{s\in S}d_s$

Der Algorithmus zur Lösung des Problems verwendet einen Divide & Conquer-Ansatz. Es handelt sich um einen RadixSort, der von der höchstwertigen Ziffer (char) ausgeht.

1) Erstellen Sie Buckets$\sigma$$0,1,\dots,\sigma-1$

2) Verarbeiten Sie die Zeichenfolgen von Anfang an zeichenweise und verteilen Sie sie mit CountingSort in -Zeit in Buckets .$\sigma$$O(1)$

3) Wiederholen Sie den Vorgang für Buckets, die mehr als ein Element enthalten, und sortieren Sie sie mit dem nächsten Zeichen.

4) Verketten Sie die Gruppen von links nach rechts, um die geordnete Sequenz zu erhalten.

Dieser Algorithmus erzeugt einen -ary-Versuch, bei dem jeder Knoten ein Array mit Größe ist und die Zeichenfolgen in den Blättern gespeichert sind.$\sigma$$\sigma$

Hier ist ein Beispiel.

Lass sein$\sigma$$5$ und $S=\{410,013,042,111,001,444\}$.

Das Folgende ist der vom Algorithmus erzeugte Versuch:

Jede Zeichenfolge $s$ formuliert einen Pfad der Größe $O(d_s)$ vor dem Knoten, der auf zeigt $s$geschaffen. Jeder Knoten dieser Pfade nimmt$O(\sigma)$ Raum und $O(\sigma)$ Zeit zuzuteilen.