still on O’Reilly’s Computer Science Programming Basics in Ruby

radix sort: sort the list by each successive digit

Here’s their take on Radix Sort (it’s not an exact copy; there’re some modifications made but the core functions the same)

def radix_sort(n) grades = rndm_grades(n) #randomly generate grades puts "grades: #{grades}" max_length = 0 grades.each_index do |i| grades[i] = grades[i].to_s len = grades[i].length if len > max_length max_length = len end end #add 0 padding so that all numbers have the same max length grades.each_index do |i| grades[i] = grades[i].rjust(max_length, "0") end for i in (0..max_length - 1) buckets = {} for j in 0..9 buckets[j.to_s] = [] end for j in 0..n-1 num = grades[j] digit = num[max_length - 1 - i] buckets[digit].push(num) end grades = buckets.values.flatten end end

debug output:

grades: [69, 63, 10, 54, 6]

get the ones digits:

9

3

0

4

6

buckets: {“0″=>[“10”], “1”=>[], “2”=>[], “3”=>[“63”], “4”=>[“54”], “5”=>[], “6”=>[“06”], “7”=>[], “8”=>[], “9”=>[“69”]}

grades flattened — [“10”, “63”, “54”, “06”, “69”]

get the ones digits:

1

6

5

0

6

buckets: {“0″=>[“06”], “1”=>[“10”], “2”=>[], “3”=>[], “4”=>[], “5”=>[“54”], “6”=>[“63”, “69”], “7”=>[], “8”=>[], “9”=>[]}

grades flattened — [“06”, “10”, “54”, “63”, “69”]

inspired by rosetta code, which is absolutely beautiful (it even takes into account negative numbers and base numbers), here’s a radix sort that utilizes more advantages of ruby compared to the one above.

def radix_sort_ii(n) grades = rndm_grades(n) puts "grades: #{grades}" max_length = grades.max.to_s.length max_length.times do |i| bucket = Hash.new {|h,k| h[k] = []} grades.each do |g| digit = (g/10**i) % 10 bucket[digit] << g end grades = bucket.values_at(*(0..10)).compact.flatten end puts "grades are sorted now: #{grades}" end

debug output:

————– Radix Sort ii ————–

grades: [49, 71, 77, 18, 32]

{9=>[49]}

{9=>[49], 1=>[71]}

{9=>[49], 1=>[71], 7=>[77]}

{9=>[49], 1=>[71], 7=>[77], 8=>[18]}

{9=>[49], 1=>[71], 7=>[77], 8=>[18], 2=>[32]}

{7=>[71]}

{7=>[71], 3=>[32]}

{7=>[71, 77], 3=>[32]}

{7=>[71, 77], 3=>[32], 1=>[18]}

{7=>[71, 77], 3=>[32], 1=>[18], 4=>[49]}

grades are sorted now: [18, 32, 49, 71, 77]

so how did the last step happen? the magic happens at line 13, check this out:

bucket = {9=>[90], 8=>[80], 6=>[67], 0=>[7], 2=>[27]}

bucket.values_at(*(0..10))

=> [[7], nil, [27], nil, nil, nil, [67], nil, [80], [90], nil]

bucket.values_at(*(0..10)).compact

=> [[7], [27], [67], [80], [90]]

bucket.values_at(*(0..10)).compact.flatten

=> [7, 27, 67, 80, 90]

don’t you just looovveee ruby? I do (: