CODEWITHSUNDEEP
algorithmsorting
wiznaibus
wiznaibus

Reputation: 671

What is the fastest way to sort 1 million integers when integers are from the range [1,100]?

Notes: I've thought about Radix sort, bucket sort, counting sort.

Is there anyway to achieve big O(n)?

Upvotes: 24

Views: 32779

Answers (8)

user3433919
user3433919

Reputation: 11

Using 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

Upvotes: 0

user unknown
user unknown

Reputation: 36229

Here is a counting sort 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 (" "))

Upvotes: 0

J&#246;rg W Mittag
J&#246;rg W Mittag

Reputation: 369420

For anyone interested, I quickly threw together this piece of Ruby, before reading the answers:

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 :-)

I didn't even know it had a name. It should convey the idea even to someone who has never seen Ruby before. (The only thing you need to know is that the K combinator is spelled tap in Ruby.)

And it really is pretty darn fast, although unfortunately I have not been able to beat the builtin hand-optimized O(n log n) sort, which is written in C in MRI and YARV and Java in JRuby.

Upvotes: 0

Lie Ryan
Lie Ryan

Reputation: 64827

I assume, you mean you want to achieve a small O(n); then bucket sort would be fastest. In fact, since you know the range of the integers, then using bucket sort simply becomes a problem of counting the occurrences of the numbers which can be done in O(n), i.e. linear time.

The so-called counting sort is simply a special case of bucket sort.

Upvotes: 4

second
second

Reputation: 28637

how about just counting the occurrence of each integer and then printing them all. sounds like O(n)

Upvotes: 6

Mark Byers
Mark Byers

Reputation: 837916

You can use counting sort.

Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A).

Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n.

In this case k is 100 and n is 1000000.

Upvotes: 72

Razvi
Razvi

Reputation: 2818

With counting sort you get O(N) if the range is fixed and small (like 1..100 :))

Upvotes: 2

Jerry Coffin
Jerry Coffin

Reputation: 490018

A counting sort would be the obvious choice under these circumstances. Yes, properly implemented it should have linear complexity.

Upvotes: 8

Related Questions