Notatki: Myślałem o sortowaniu Radix, sortowaniu kubełków, sortowaniu liczenia.Jaki jest najszybszy sposób sortowania 1 miliona liczb całkowitych, gdy liczby całkowite są z zakresu [1100]?
Czy istnieje szansa na uzyskanie dużej liczby O (n)?
Można użyć counting sort.
Sortowanie zliczające (czasami określane jako sortowanie ultra lub sortowanie matematyczne) jest algorytmem sortowania, który (podobnie jak sortowanie wiadra) wykorzystuje znajomość zakresu liczb w tablicy do posortowania (tablica A).
Sortowanie zliczania jest sortowaniem trwałym i ma czas działania Θ (n + k), gdzie n ik są długościami macierzy A (tablica wejściowa) i C (tablica zliczania) odpowiednio. Aby ten algorytm był efektywny, k nie może być dużo większe niż n.
W tym przypadku k 100 i n wynosi 1000000.
+1 Oszołomanie oczywiste, ale nigdy wcześniej tego nie widziałem. Dzięki. –
Chcę przegłosować, ale obecnie ma 42 lata i naprawdę chcę, żeby tam został. To największy dylemat, z jakim miałem do czynienia dzisiaj. – EmmaGamma
Sortowanie zliczania byłoby oczywistym wyborem w tych okolicznościach. Tak, prawidłowo wdrożone, powinno mieć liniową złożoność.
Z sortowanie przez zliczanie dostać O (n), jeśli zakres jest stała i małe (jak 1..100 :))
jak o tylko liczenie wystąpienie każdej liczby całkowitej, a następnie drukowanie ich wszystkich. brzmi jak O (n)
Tak, i to jest dokładnie takie sortowanie. To pokazuje, że większość algorytmów nie jest trudna; możesz sam je wymyślić. :-) – ShreevatsaR
sortowanie zliczania jest nieco bardziej skomplikowane (sortuje klucze, ale może obsługiwać dane skojarzone), ale tak, to jest podstawowy pomysł –
Zakładam, masz na myśli, że chcesz osiągnąć małe O (n); wtedy sortowanie wiadra będzie najszybsze. W rzeczywistości, ponieważ znasz zakres liczb całkowitych, użycie sortowania wiaderek staje się po prostu problemem zliczania wystąpień liczb, które można wykonać w O (n), tj. W czasie liniowym.
Tak zwany sortowanie zliczania jest po prostu szczególnym przypadkiem sortowania kubełkowego.
Nie, sortowanie zliczania nie jest szczególnym przypadkiem sortowania wiadra. W sortowaniu wiaderek faktycznie przechowujesz elementy w wiadrach. W sortowaniu liczącym przechowujesz tylko licznik. –
Dla wszystkich zainteresowanych, szybko rzucił razem ten kawałek Ruby, przed przeczytaniem odpowiedzi:
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 :-)
ja nawet nie wiem, że miał nazwę. Powinien przekazać pomysł nawet komuś, kto nigdy wcześniej nie widział Rubiego. (Jedyne co musisz wiedzieć to to, że kombinator K jest pisany w Ruby jako tap).
I naprawdę jest bardzo cholernie szybki, chociaż niestety nie udało mi się pokonać wbudowanego ręcznie zoptymalizowanego O (n & thinsp; log & thinsp; n) sort, który jest napisany w C w MRI i YARV i Java w JRuby.
Oto porządek liczenia w 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 (" "))
Korzystanie sortowanie pozycyjne (w 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
To nie jest możliwe w ogóle, aby posortować listę w czasie O (n), nawet jeśli każda liczba na liście jest mniejsza niż 100. – SLaks
@SLaks: Minimalna liczba O (N lgN) ma zastosowanie tylko do sortowania na podstawie porównań. –
w tym przypadku możesz, po prostu licząc elementy od 1 do 100. –