Problem: |
Bucketsort, for those of you who don't know, is a very fast sorting algorithm (Big O(N)) that requires some extra knowledge about the data you're going to sort. Specifically, you need to know the range of your data. How the algorithm works is as follows:
1) First you must allocate a temporary array that has as many elements as the range of your data, and initialize all the elements to zero. Think of it as an array of buckets.
2) Next, you begin reading values from the array you want to sort. When you read a value N, you increment the Nth element of the temporary array. Think of this as throwing the values into different buckets. Do this until you reach the end of the array.
3) Now each element of the temporary array contains the number of that index to write to the array you want to sort. For example, if element 0 of the temporary array contains the value 5, then you must write the value zero 5 times to the array you want to sort. Do this for every element in the temporary array, and then your data will be sorted!
For this contest, the data you'll be required to sort is an array of 16-bit integers ranging between 0 and 5,000. To help you test your routine, I have written a DOS program that will generate random, 16-bit integers for use with TASM. You can download the source code and executable here.
To use the program, you need to be at a DOS prompt, in the same directory as the program. Simply type "randints <limit> <count>", where <limit> and <count> are integers from 1-32767. <limit> sets the range of data (0 to limit), and <count> is the number of random integers to generate. The output of the program will be to the screen, however you can redirect the output to a file with the > or >> (to append) directives. For example, to generate a file called output.dat that contains 10,000 integers between 0 and 5,000, you would type "randints 5000 10000 > output.dat".
Send your entries to Kouri by December 18th. Good luck!
|
Directions: |
Optimization:
SIZE
Input:
An array of 16-bit integers located at address ARRAY.
A 10,002 byte temporary array located at address TEMP.
BC = The number of elements to sort.
ARRAY: .dw 1238, 3523, 93, 849, 4323, 125, 1294
BC = 7
Output:
The array in ascending order (sorted with the bucketsort algorithm, duh).
ARRAY: .dw 93, 125, 849, 1238, 1294, 3523, 4323
|
Constraints: |
You may assume that ARRAY will only contain BC elements with values between 0 and 5,000, and that BC will always be greater than 0.
You may assume that interrupts will be disabled before your routine runs.
You may assume that ROM begins at $0000.
Do not assume any distribution pattern among the data.
Do not assume that the memory at TEMP is initialized in any way. You must initialize it yourself.
You do not have to initialize all of TEMP to zero. You can use any number you wish.
You do not have to increment the "bucket" elements of TEMP. Decrementing is also acceptable.
|
|