Enjoy the goodness:
- Due: Friday May 12, 2006
- Worth: 6 points, or 6% of your grade
- Why: arrays in assembly code and much more
Description
If you're like me, then probably 3-4 times a week you'll see at an unordered list of integers and think aloud, "I wonder what the median of that list is?" Well, wonder no more as Program #2, Captain Median, will come to your rescue! Program #2 will do 2 things:
- Query the user for a list of integers, and
- Print the median value of the list
The median is the middle number if you sorted the the list. Here's an example:
| Numbers: 12, 43, 7, 89, 2 |
| Median = 12 |
Now, one (slow) way to do this is to sort the list and then just access the (size+1)/2 element. I'd rather not sort the whole list if we don't have to... and we don't.
The set of algorithms that solve this general problem are referred to as selection algorithms in computer science. They ask the question, "How can we efficiently select the K'th element in an unordered list?" Well, below I offer some pseudo-code for a simple solution that sorts only the k elements of the list that we are interested in, rather than the whole list. See if you can follow it:
| // Select (return) k'th element in array of n integers |
| int select( int k, int array[], int n) |
| for i = 0 to k-1 |
| min_index = i |
| min_value = array[i] |
| for j = (i+1) to n-1 |
| if array[j] < min_value |
| min_index = j |
| min_value = array[j] |
| end for j |
| swap array[i] and array[min_index] |
| end for i |
| return array[k-1] |
Here are two tasty Wikipedia pages on this topic:
- http://en.wikipedia.org/wiki/Median - defines the statistical concept of "median"
- http://en.wikipedia.org/wiki/Selection_algorithm - surveys a variety of selection algorithms... selecting the K'th item out of a list, that is. BTW, look at that linear selection algorithm... yum yum!
Implementation
Obviously, we'll do our work in assembly code. I'd like to see the following details:
- A main() function (of course) and 3 other functions:
| # select the Kth element in an array of size n |
| # using the algorithm described above |
| int select( int k, int array[], int n) |
| # return the median of the array by calling select() |
| int median( int array[], int n) |
| # print the n elements in the array |
| void print_array( int array[], int n) |
- Please define your array of integers as a global variable. You have to set the size of the array (rather than allocate it dynamically); I set mine to 25. Don't let the user's list get longer than your array!
- This global variable thing is for educational purposes only. I still want you to pass your array into your functions as parameters.
- If you want to try the -S option on the compiler that turns C into assembly, go ahead. It's a wild ride though, so be careful as the compiler does some weird things.
Here's a sample session from mine:
Grading
Same as last time. Please put your completed code on the k: drive. This should include:
- Your assembly code file (median.s)
- Your executable (a.exe)
- A README file describing the status of your program
You must comment your code; uncommented code will face a harsh brand of grading justice.
- File header – a block comment at the top of the file: file name, author, creation date, description
- Function header – a block comment at the top of each function (only main() in this program): function, parameters, return value, description
- Inline comments – describe the purpose of each logical block of assembly code statements
Please use meaningful label names to make your program easier to understand.
Notes
If you have an even number of integers in your array, then there isn't one number in the middle with the same amount of elements above and below it. So, you can:
- Return either number around the median, one above or one below it
- Return the average of those two "medians"
thanks... yow, bill