Anmerkungen: Ich habe über Radix-Sortierung, Eimer-Sortierung, Zähl-Sortierung nachgedacht.Was ist der schnellste Weg, um 1 Million ganze Zahlen zu sortieren, wenn ganze Zahlen aus dem Bereich [1.100] kommen?
Gibt es trotzdem einen großen O (n) zu erreichen?
Sie counting sort verwenden können.
Zählen sort (manchmal auch als ultra sort oder math sort bezeichnet) ist ein Sortieralgorithmus, der (wie Bucket-Sortierung) den Bereich der Zahlen im zu sortierenden Array kennt (Array A).
Zählsortierung ist eine stabile Sortierung und hat eine Laufzeit von Θ (n + k), wobei n und k die Längen der Felder A (das Eingangsarray) bzw. C (das Zählarray) sind. Damit dieser Algorithmus effizient ist, darf k nicht viel größer als n sein.
In diesem Fall ist k 100 und n 1000000.
+1 Blendend offensichtlich, aber noch nie zuvor gesehen. Vielen Dank. –
Ich möchte upvote, aber derzeit ist es bei 42 und ich will es wirklich dort bleiben. Das ist das größte Dilemma, mit dem ich mich heute konfrontiert sehe. – EmmaGamma
Eine zählende Sortierung wäre die offensichtliche Wahl unter diesen Umständen. Ja, richtig implementiert sollte es lineare Komplexität haben.
Mit Countingsort erhalten Sie O (N), wenn der Bereich festgelegt ist und klein (wie 1..100 :))
wie etwa nur das Auftreten jedes ganzzahlige zählen und dann mit dem Drucken sie alle. klingt wie O (n)
Ja, und das ist genau zu zählen. Dies zeigt, dass die meisten Algorithmen nicht schwer sind; Sie können selbst mit ihnen kommen. :-) – ShreevatsaR
count sort ist ein bisschen komplexer als das (es sortiert die Schlüssel, aber kann mit assoziierten Daten umgehen), aber ja, das ist die Grundidee –
Ich nehme an, du meinst, du willst ein kleines O (n) erreichen; dann wäre die Eimersortierung am schnellsten. Da Sie den Bereich der Ganzzahlen kennen, wird tatsächlich die Verwendung der Bucket-Sortierung einfach zu einem Problem des Zählens des Auftretens der Zahlen, die in O (n), d. H. Linearer Zeit, ausgeführt werden können.
Die sogenannte Zählsortierung ist einfach ein Spezialfall der Bucket-Sortierung.
Nein, zählen Sort ist kein Sonderfall von Eimer sortieren. In Bucket sort speichern Sie die Elemente tatsächlich in den Buckets. Beim Zählen sortieren Sie nur die Anzahl. –
Für alle Interessierten, warf ich schnell zusammen, um dieses Stück von Ruby, bevor die Antworten zu lesen:
module Enumerable
def counting_sort(k)
reduce(Array.new(k+1, 0)) {|counting, n| counting.tap { counting[n] += 1 }}.
map.with_index {|count, n| [n] * count }.flatten
end
end
ary = Array.new(1_000_000){ rand(100) + 1 }
ary.counting_sort(100) # I'll spare you the output :-)
ich nicht einmal wusste, dass es einen Namen hatte. Es sollte die Idee sogar jemandem vermitteln, der Ruby noch nie zuvor gesehen hat. (Das Einzige, was Sie wissen müssen, ist, dass der K-Kombinator in Ruby tap geschrieben wird.)
Und es ist wirklich verdammt schnell, obwohl ich leider nicht in der Lage gewesen bin, die eingebaute Hand-optimierte O (n & thinsp; log & thinsp; n) sort, das in C in MRI und YARV und Java in JRuby geschrieben ist.
ist hier ein Countingsort in scala:
val res = Array.fill (100)(0)
val r = util.Random
// generate data to sort
val nums = for (i <- 1 to 1000*1000) yield r.nextInt (100)
for (i <- nums) res(i) += 1
println (res.mkString (" "))
Mit Radix Sort (In Ruby):
def sort(array)
sorted_array = Array.new(100,[])
array.each do |t|
sorted_array[t-1] = sorted_array[t-1] + [t]
end
sorted_array.flatten!
end
Es ist nicht möglich, in der Regel ist eine Liste in O (n) zu sortieren, auch wenn jede Nummer in der Liste kleiner als 100 ist. – SLaks
@SLaks: Das Minimum von O (N lgN) gilt nur für Sortierungen, die auf Vergleichen basieren. –
in diesem Fall können Sie, indem Sie einfach Elemente zwischen 1 und 100 zählen. –