copyright Steve J. Hodges   http://steveh.net/cs21/cs21-hw04.html

CS 21

Assignment 4 Spring 2019

Radix/Bucket Sort hybrid

Directory Name

21-4

Required Executable Name

p4

I'll run your program either way:
./p4
java p4

Program Description

Implement the combined O(n) radix/bucket sort as described in class. (i.e. divide the input by radix, bucket sort (with no insertion sort step) once for each radix starting from the least significant. Make sure that your overall implementation is O(n)

 

Input and Output format in assignment #4 is the same as assignment #3.

Input

The input to your program will an unspecified number of entries. Each entry is a non-negative integer containing nine (zero padded) digits ( this means that the integer may have either leading or trailing zeros), one per line. Read your input from STDIN.

 

Output

Send the values, one per line, as they were input (all nine digits including leading zeroes, if any), sorted in ascending order, to STDOUT. The only output of your program is the numeric results. (i.e. don't output your name, assignment number, prompts etc.)

Notes

You may use your (suitably modified if necessary) linked list from assignment #1, a linked list or dynamic array that you code for this assignment, or a standard library dynamic array or sequence container (such as the STL Vector in C++, or ArrayList for Java) for your buckets.

What to turn in

Put all of the source code files (.cpp, .h, makefile if approprite, .java, etc.) but no executeables, binaries, compiler, or data files (omit .o, "a.out" , .class files etc.) in a folder named as shown above in the home directory of your account on pengo. Please don't include any sub-folders.