Sortieren einer großen Liste von Testergebnissen

Question

Sie haben eine große Liste (z. B. N > 10.000) von Testergebnissen, die Sie sortieren möchten.Die Testergebnisse liegen zwischen 1 und 100.Wie kann ich die Liste am schnellsten sortieren?

Erster Gedanke.Wir haben eine O(N log N)-Grenze, aber wir haben auch zusätzliche Informationen über die Mengen im Array, also denke ich, dass wir es besser machen könnten.

Zweiter Gedanke:Sollten wir Hash-Tabellen verwenden? Sind uns Duplikate wichtig?Ich kann nicht sehen, wie man Hash-Tabellen verwendet.

Dritter Gedanke:Hat das etwas mit der Radix-Sortierung zu tun?keine Ahnung.

Vierter Gedanke:Könnten wir diese Liste sortieren, indem wir eine weitere Liste erstellen und dann die ursprünglichen Zählhäufigkeiten der aufgetretenen Elemente durchgehen?Aber bräuchten wir einen weiteren Durchgang, um eine größere sortierte Liste zu erstellen, die O(N^2) wäre?also zu groß.

Ist das eine sehr einfache Frage oder eine sehr schwierige Frage?

Answer 1

Dies ist eine sehr einfache Frage, wenn man davon ausgeht, dass alle Ergebnisse ganze Zahlen sind.

Hier ist der einfachste Algorithmus in einfachen Worten.Wir werden initiieren count, ein ganzzahliges Array mit 100 Nullen.Für jede Punktzahl s, wir werden 1 hinzufügen count[s].Um die gewünschten sortierten Ergebnisse zu erzeugen, geben wir aus count[1] 1s, count[2] 2s, ... und schließlich count[100] 100er.

Diese Art von Sortieralgorithmus wird Zählsortierung genannt.

Der Fall von mehr als $N>10000$ Testergebnisse zwischen 1 und 100 sind eine Hauptanwendung der Zählsortierung.Die Zeitkomplexität ist $O(N)$ und die Raumkomplexität wird durch ein kleines konstantes Vielfaches von 100 begrenzt.

Vielleicht möchten Sie es überprüfen Zählsortierung für mehr Informationen.

Answer 2

ja, indem Sie Sortieralgorithmen wie Merge-Sortieren verwenden, können wir dies durch O (n * logn) erreichen, wir können hier besser machen. Die zusätzlichen Informationen in Bezug auf die Bindung von Testergebnissen sind hier sehr nützlich.

kümmern wir uns um Duplikate?

Wenn wir uns nur mit nur Punkten befassen und sich nicht um die anderen Informationen wie Student_Name oder Subject_info kümmern, und wir möchten nur, dass die Ergebnisse im sortierten Format mit diesem Algorithmus verwenden können.

generasacodicetagpre.

Jetzt, wenn wir uns um die Info kümmern, wenn die Punktzahl wie Student / Subjekt, der es gehörte, um diesen untenstehenden Ansatz zu verwenden. Ich gehe davon aus, dass Sie die Punktzahl und verwandte Informationen in einer C / C ++ - Struktur oder einem beliebigen Objektformat speichern.

Halten Sie nun eine Hash-Tabelle mit Größe 100 (Sortiment an Testergebnissen) aufrecht Key= Score. Wert= eine Liste von Objekten oder Instanzen mit dieser Punktzahl (wenn Sie sind Sortieren für eine Liste von Studenten, dann Liste der Schüler mit dieser Punktzahl)

Wenn Sie mit C / C ++ vertraut sind, kann diese Datenstruktur mit der Anordnung von verknüpften Listen implementiert werden. Die hier verwendete Hashing-Technik ist separates Hashing .

Die Datenstrukturfunktionalität ist so DS [Score] hat den Zeiger / Verweis auf die verknüpfte Liste Mit einer anderen Hash-Karte, um die Schwänze jeder Unterlisten in DS zu identifizieren, können wir ein neues Element in O (1) einfügen.

also in einem einzigen Pass von i= 0 bis ich

Nach dem Einfügen können wir eine neue Liste mit einem einzelnen Durchlauf auf DS erstellen, das wir erstellt haben.

Der Algorithmus ist so.

lässt Array alle Objekte mit ihren jeweiligen Bewertungen enthalten

generasacodicetagpre.

Dieser Ansatz ist magisch mit der Warteschlange-basierten Radix-Sortiments-Basis 100. Lesen Sie mehr über Radix Sortieren und Zählen Sortieren mit der Warteschlange-Implementierung.

aus der frage: "Vierer Gedanke: Können wir diese Liste sortieren, indem wir eine andere Liste erstellen, und dann durch die ursprünglichen Zählfrequenzen von Elementen passieren. Aber würden wir einen anderen Pass benötigen, um eine größere sortierte Liste zu erstellen, die o (N ^ 2) ist. Dh zu groß. «

Ich denke, Sie verwechseln einen weiteren Pass, der n auf N2 wechseln würde. Es sei denn, Sie geben den "anderen Pass" in einer Schleife, nicht.

Ich hoffe, ich habe alle Ihre Fragen beantwortet.