Geben Sie einen gegebenen Satz von n ganzen Zahlen im Bereich [0..n^3-1] einen linearen Zeitsortieralgorithmus an.Sortierung in linearer Zeit?
Dies ist eine Überprüfung für meinen Test am Donnerstag, und ich habe keine Ahnung, wie Sie dieses Problem anzugehen.
Schauen Sie auch verwandte Arten zu: pigeonhole sort oder counting sort, sowie radix sort wie von Pukku erwähnt.
Denkst du nicht, dass n^3-1 ein bisschen zu groß ist, um das Zählen zu verwenden? Wenn n = 100 wäre, hätten Sie 100^3 Platz zum Sortieren. Er muss die Basis der ganzen Zahlen ändern und Radix sort verwenden. – unj2
Mit dem Bereich der n d-stelligen Zahlen in [0, n^3 - 1], dann ist die Zahl der Ziffer d 3log (n) und der Algorithmus läuft in O (dn) => O (nlog (n)). Radix sort ist keine lineare Lösung. Außerdem ist eine Schublade nicht geeignet, weil die Anzahl der Elemente nicht "ungefähr gleich" ist wie die Anzahl der möglichen Tasten. – Gevorg
Werfen Sie einen Blick auf radix sort.
Nur eine Einschränkung, Radix-Sortierung ist nur linear, wenn Sie eine feste maximale Länge für Ihre Schlüssel haben ... da Sie eine Reihe von ganzen Zahlen haben, dann ja, kann es linear sein, aber Dies wird nicht immer der Fall sein. –
Dies wird auch als "Bucket-Sortierung" bezeichnet. – GoatRider
Mit dem Bereich der n d-stelligen Zahlen in [0, n^3 - 1], dann ist die Zahl der Ziffer d 3log (n) und der Algorithmus läuft in O (dn) => O (nlog (n)). Radix sort ist keine lineare Lösung. – Gevorg
Ein Satz mit einem begrenzten Zahlenbereich kann durch eine Bitmap von RANGE-Bits dargestellt werden. In diesem Fall eine 500-Bit-Bitmap, also für alles andere als riesige Listen, wäre es mit Radix-Sort besser. Wenn du auf die Zahl k triffst, setze Bitmap [k] = 1. Einfaches Durchlaufen der Liste, O (N).
Beachten Sie, dass n nicht gleich 2 sein kann. – Reunanen
Es ist wirklich einfach, wenn n = 2 und Zahlen sind eindeutig:
Komplexität => O (2n)
Andernfalls verwenden Radix Sortieren:
Komplexität => O (kn) (hoffentlich)
Die Frage lautet n^31 und nicht 2^31. Weiter nehmen Sie an, dass keine Zahl mehr als einmal erscheint. –
Ich nehme n = 2 an. Ich denke, das ist ein Tippfehler. Schließlich verwenden wir normalerweise keine anderen Basen als 2. Sie haben recht, ich bin (wahrscheinlich falsch) davon ausgegangen, dass Zahlen nicht wiederholt werden! – Ash
danbruc, ich kenne Ihren Hintergrund nicht, aber meine Antwort ist sehr gut und ausgewogen (wenn ich das sagen darf). – Ash
wikipedia zeigt ganz viele verschiedene Sortieralgorithmen und ihre Komplexitäten. Sie könnten sie auschecken
Wenn Leute "Sortieralgorithmus" sagen, beziehen sie sich oft auf "Vergleichsortieralgorithmus", welcher Algorithmus ist nur abhängig von der Fähigkeit zu fragen, "ist das Ding größer oder kleiner als das ". Wenn Sie also nur eine Frage zu den Daten stellen, erhalten Sie nie mehr als n * log (n) (dies ist das Ergebnis einer log (n) Suche der n faktoriellen möglichen Ordnungen eines Datensatzes). .
Wenn Sie die Einschränkungen von "comparison sort" umgehen und eine differenziertere Frage zu einem Datenelement stellen können, zum Beispiel "Was ist die Basis 10 radix dieser Daten", dann können Sie eine beliebige Anzahl von linearen finden Zeitsortier-Algorithmen benötigen sie nur mehr Speicher.
Dies ist ein Time-Space-Trade-Off. Comparason-Sortierung benötigt wenig oder keinen RAM und läuft in N * log (n) -Zeit. Radix-Sortierung (zum Beispiel) läuft in O (n) Zeit UND O (Log (Radix)) Speicher.
Sie können eine vor Ort Radix sortieren – aaronman
@Aaronman können Sie auf die Verknüpfung lineare Zeitkonstante Raum Sortieralgorithmus? –
Sicher, bedenken Sie, wenn ich konstanten Raum sagen, es ist in Bezug auf die Größe des Bereichs, der Speicher ist nicht konstant in Bezug auf die Größe von was sortiert wird (32bit v 64bit) ein Link ([radix] (https://github.com/aaronjosephs/radix/blob/master/radix.cpp)) zu meiner eigenen Implementierung, der Code ist chaotisch, aber es ist derjenige mit dem Namen 'msd16_radix', verwendet es zu zählen Sortierung an Ort und Stelle, auch ruft es std :: sort, weil es für kleine Arrays schneller ist, also ist meine Implementierung nicht streng inplace (wenn std :: sort Speicher verwendet), aber es ist klar, dass es inplace erreicht werden kann. – aaronman
gleichermaßen Algo möglich:
M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];
Es ist allein möglich Algo für lineare Komplexität, aber es hat die Komplexität O (k * N) von RAM (N - Anzahl Feldelemente, k - Elemente LEN)
Denken Sie die Zahlen als dreistellige Zahlen, wobei jede Ziffer von 0 bis n-1 reicht. Sortieren Sie diese Zahlen mit der Radix-Sortierung. Für jede Ziffer gibt es einen Aufruf zum Zählen von Sort, der Theta (n + n) Zeit verwendet, so dass die Gesamtlaufzeit Theta (n) entspricht.
Können Sie die Frage noch einmal überprüfen? N gegen n? [0..n^31] gegen [0..2^31] gegen [0..2^32-1]? –
@danbruc - Guter Punkt. Auch Revision 1 sagt [0..n^3-1] - warum ist es [0..n^31] jetzt? –
Ich habe keine Ahnung, warum sich das geändert hat. Ich kann mich nicht erinnern, jemals aktualisiert zu haben. –