Hello again and welcome back to uoeadspractice! Before I go on and tell you the problems for this week, I would like to remind you that this is an informal blog and is not directly connected to the ADS course or the University of Edinburgh, although they are inspiration for creating and maintaining it. Even if you missed the previous challenges, you can still participate, be it just for fun. Also, you don’t need to solve everything in order to submit solutions, so just relax and enjoy.
This week’s challenge will be all about sorting again (for the last time, I promise). There is something to be excited about, though – you are supposed to do it in linear time! The tasks are the following:
- Counting sort;
- Radix sort;
- Bucket sort.
1. Counting Sort
It is well known that comparison-based sorting can not be done in time less than O(n * lg n). But what if we remove this restriction? Or better said, if we impose more restrictions on the data, particularly that each element belongs to a set of finite possibilities that has a total order. In the context of whole numbers this would mean that each element of the array that we want to sort belongs to a given interval.
Well, if that is the case, then we can simply count the number of occurrences of each number in that interval, and then use this information to reconstruct the array in sorted state. I can put the details in words, but why not look at a simulation instead? Note that this is not the only way of using the counting array to reconstruct the sorted array. It is you chance to be creative! Specs:
Test range:
The size of the input array will be less than 108.
The elements of the input array will be 8-bit integers.
Your function is expected to execute for less than 1 second.
Format:
C++:
vector<int> CountingSort(vector<int> &A);
Java:
List<Integer> countingSort(List<Integer> A);
2. Radix Sort
RadixSort is another “more-than-just-comparison” sorting algorithm. It was invented during the times when you could literally get a hold of someone’s data:
The idea is the following: sort the array multiple times, using the digits of the elements as keys, starting from the least significant one, and finishing at the most significant one. If you use Counting sort for each of these steps the asymptotic run-time would still be better than that of a comparison-based algorithm.
Example:
Sort [123, 13, 1, 542, 521, 132, 2, 10, 21]:
1: [123, 013, 001, 542, 521, 132, 002, 010, 021] -> [010, 001, 521, 021, 542, 132, 002, 123, 013];
2: [010, 001, 521, 021, 542, 132, 002, 123, 013] -> [001, 002, 010, 013, 521, 021, 123, 132, 542];
3: [001, 002, 010, 013, 521, 021, 123, 132, 542] -> [001, 002, 010, 013, 021, 123, 132, 521, 542];
Result: [1, 2, 10, 13, 21, 123, 132, 521, 542], which really is sorted.
Test range:
The size of the input array will be less than 107.
The elements of the input array will be 32-bit integers.
Your function is expected to execute for less than 1 second.
Format:
C++:
vector<int> RadixSort(vector<int> &A);
Java:
List<Integer> radixSort(List<Integer> A);
3. Bucket Sort
The last sorting for this challenge (and my favorite one) is one employing probability to sort. Bucket sort assumes that the input data has a uniform distribution, or, in other words, each element has equal probability of having any value of the domain range. An example where this is not true is if you had a list of shoe-sizes of all the people in the university, as although there might be someone with shoe-size 12 (it is in the domain range), it is certainly not as likely as there being one with size 8. Still, there are many cases where the uniform distribution assumption holds.
So how can we exploit that? Imagine that we have one thousand random numbers from zero to one million and that they have a uniform distribution. Thus we expect that the element with index k in the sorted array to have a value around 1000 * k. So we go through the array and put each element x that we encounter in a “bucket” indexed x / 1000 that corresponds to the x / 1000 – th element in the sorted array. Next, for each bucket, if it contains one or less elements, we can append it to the sorted array (initially an empty one). Otherwise we sort it (either using Bucket Sort again, or Insertion Sort, as it performs well on small inputs) and then append it to the sorted array.
As this explanation was a mess, here is an…
Example:
Sort [25, 0, 3, 21, 4, 5, 20, 8, 7, 13, 15]:
Buckets: [0: [0], 1: [3], 2: [4, 5], 3: [8, 7], 4: [], 5: [13], 6: [15], 7: [], 8:[20, 21], 9: [], 10: [25]]
Result: [0, 3, 4, 5, 7, 8, 13, 15, 20, 21, 25].
Another Example:
Sort [10, 27, 7, 15, 16, 24, 13, 17, 19, 23, 14]
Buckets: [0: [7], 1: [], 2:[10], 3:[14, 13], 4: [16, 15], 5: [17], 6: [19], 7: [], 8: [23, 24], 9: [], 10: [27]]
Result: [7, 10, 13, 14, 15, 16, 17, 19, 23, 24, 27]
Test range:
The size of the input array will be less than 107.
The elements of the input array will be 32-bit integers.
Your function is expected to execute for less than 1 second.
Format:
C++:
vector<int> BucketSort(vector<int> &A);
Java:
List<Integer> bucketSort(List<Integer> A);
How to Submit
After you’re done, put the functions in one file called winchal4.cpp or WinChal4.java. In case you are using Java, obviously you need a class. Call it WinChal4 and let it reside in a package called uoeadspractice.<nickname>.challenge4. Also, add a comment with your nickname in the beginning of the file.
When you’re done with that, send the file(s), together with a nickname, and optionally degree, year and university (if it is not University of Edinburgh) to uoeadspractice a t gmail d o t com. The deadline for submitting your code is Sunday 14 October 2012 2359 GMT.
About next week
Since you have to submit your coursework by the end of week 5, I can tell you what challenge 5 would be right now – get a 100 % on your coursework.
Happy Hacking!
– Stan
uoeadspractice 