codepad

Language:

def compare_items_element(item1, item2, elem_idx)  
  ch_item1 = item1[elem_idx]
  ch_item2 = item2[elem_idx]

if !ch_item1 && !ch_item2
    nil
  elsif !ch_item1
    1
  elsif !ch_item2
    -1
  else
    ch_item1 <=> ch_item2
  end

end

def radix_exchange_recurse(array, start_idx, end_idx, curr_char_idx)
  # If start index is equal or higher from end_idx, it doesn't need to sort
  return if start_idx >= end_idx

# If all elements' nth char. is nil, sort for current range(set) is complete
  all_nil = true
  (start_idx..end_idx).each do |idx|
    all_nil = nil if array[idx][curr_char_idx]
  end

return if all_nil

# sort by current character index
  quicksort(array, start_idx, end_idx) do |item1, item2|
    compare_items_element(item1, item2, curr_char_idx)
  end

p "#{start_idx} ~ #{end_idx} step end... current array is \'#{array.join " "}\'"

# grouping and re-sort
  last_char = array[start_idx][curr_char_idx]
  char_group_start_idx = start_idx

((start_idx + 1)..end_idx).each do |idx2|
    if array[idx2][curr_char_idx] != last_char
      radix_exchange_recurse(array, char_group_start_idx, idx2 - 1,
        curr_char_idx+1)

last_char = array[idx2][curr_char_idx]
      char_group_start_idx = idx2
    end

end

# last group
  radix_exchange_recurse(array, char_group_start_idx, end_idx,
        curr_char_idx+1)
end

def radix_exchange_sort(array)
  radix_exchange_recurse(array, 0, array.length - 1, 0)
end

def quicksort(array, begin_idx, end_idx, &compare_block)
  return if begin_idx >= end_idx

#p "Quicksorting #{begin_idx} to #{end_idx}..."

pivot_idx = partition(array, begin_idx, end_idx, &compare_block)

#p "Pivot is #{pivot_idx}"

quicksort(array, begin_idx, pivot_idx - 1, &compare_block)
  quicksort(array, pivot_idx + 1, end_idx, &compare_block)

end

def partition(array, begin_idx, end_idx)
  pivot_idx = begin_idx
  pivot = array[pivot_idx]

left_idx = begin_idx + 1
  right_idx = end_idx

while left_idx <= right_idx

while left_idx <= end_idx && yield(array[left_idx], array[pivot_idx]) <= 0
      left_idx += 1
    end

while right_idx >= begin_idx && yield(array[right_idx], array[pivot_idx]) > 0
      right_idx -= 1
    end

if left_idx <= right_idx
      array[left_idx], array[right_idx] = array[right_idx], array[left_idx]
    end

end

array[pivot_idx], array[right_idx] = array[right_idx], array[pivot_idx]

#p "Partition End : pivot_idx is #{right_idx} / #{array.join(" ")}"

right_idx
end

def make_example_array
  %w(add cab fee bad dad bee bed ace)
end

array = make_example_array
p array
radix_exchange_sort(array)
p array

Private [?]

Run code