NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Radix Sort


1. Sort the 16 names below using LSD radix sort. Show the result (by listing the 16 full words) of each of the four stages of the sort.

Stage 0          Stage 1          Stage 2          Stage 3          Stage 4
-------          -------          -------          -------          -------

Ella

Jane

Adam

Erik

Dave

Evan

Sean

Erin

Jada

Jack

Noah

Luke

Kyle

Owen

Cole

Emma






2. Show the contents of the array after one partitioning step in 3-way radix quicksort of the following 16 names. Use the 3-way partitioning scheme from the quicksort lecture (that begins by partitioning on the first letter of the first string).

                 After partitioning
Input            on the E in Ella
-------          ------------------

Ella

Jane

Adam

Erik

Dave

Evan

Sean

Erin

Jada

Jack

Noah

Luke

Kyle

Owen

Cole

Emma