Sorting with RADIX & COUNTING: How to?

[mathmari]

Hey!

I have to describe the operation of the processure "RADIX SORT" at the following list of words:

[m]COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX[/m]
When I want to show the work of the algorithm RADIX SORT do I have to sort the letters by comparing them or do I have to show also the work of COUNTING SORT ?? (Wondering) In my book there is the following algorithm of Radix Sort:

RADIX_SORT(A, d) 
      for i ← 1 to d 
          sort A as for the digit i with a stable algorithm

The algorithm of Counting Sort is the following:

COUNTING_SORT (A, B, k)
    
    for i ← 0 to k do
        c[i] ← 0
    for j ← 1 to length[A] do
        c[A[j]] ← c[A[j]] + 1
    //c[i] now contains the number of elements equal to i
    for i ← 1 to k do
        c[i] ← c[i] + c[i-1]
    // c[i] now contains the number of elements ≤ i
    for j ← length[A] downto 1 do
        B[c[A[j]]] ← A[j]
        c[A[j]] ← c[A[j]] - 1

 

[Future Bruno]

Radix Sort uses Counting Sort as a subroutine so you will need to show the work of both algorithms to demonstrate the process of sorting the list of words. The Radix Sort works by sorting the characters of each word by comparing them one at a time, starting from the least significant character. The algorithm first sorts the list of words based on the first letter of each word, then it continues with the second letter of each word and so on until all the letters of each word have been sorted. To do this, the algorithm uses Counting Sort to sort each letter. For example, for the list of words given, the first step would be to sort them based on their first letter, so we'd have: BOX, BAR, BIG, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, RUG, SEA, TAB, TAR, TEA. Then we'd move on to the second letter, so we'd have: BAR, BOX, BIG, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, RUG, SEA, TAB, TAR, TEA. We'd continue this process until each word is sorted.