CEG220: Introduction to C
Programming for Engineers – I
Section 2
Homework for Week 7
- Alice
has to sort 10,000 names stored as strings, “LastName, FirstName.”
While bubble sort would be slow, and quick sort potentially as slow, let’s
try a different approach. Put all the As in one
bucket, the Bs in another, and so on. Then sort the buckets. When needing
to find the name “Johnson, Todd,” we can go right to the Js, and then do a
linear search on the Js, which would be faster than having to search
through all of them. Furthermore, if you wish to add more names to the
list, you would only have to sort the bucket in which the entry was added!
Implement bucketsort that uses
mergesort on the buckets.
NOTE: This will be a 2-Dimensional
array of char*/unsigned char* OR a 3-Dimensional array of char/unsigned char.