Selection AlgorithmsBy this point we have a good grasp on various ways to sort and search through lists of data or classes. Intro computer science classes often have students write a program that needs to find the minimum, maximum, or median of the integers or other data present within the program.
Selection Algorithms try to find the aforementioned data
(Order Statistics) are really a subset of path finding algorithms (shortest path for example) in the earnest sense. Armed with this knowledge we will go over various selection algorithms and their widely varying abilities to do nearly anything within a list of data.
Selection Through SortingThis is by far the easiest way to find the data you are looking for. Assuming we have a valid (but expensive processing) sort method, all we have to do to find the min and max is sort the list and retrieve the first and last elements of the list, respectively.
CODE
//sort
int min = arrayOne[0];
int max = arrayOne[n-1];
//easy and quick, no?
Linear SelectionThis is the method employed by many of the first year programs. It iterates through the list and keeps track of which number is the maximum and minimum so far.
CODE
int max = 0;
while (!done)
//user input
if (userInput > max)
max = userInput
//so on and so forth
Nonlinear general selection algorithmThis implementation is similar to the previous algorithm, but is quite inefficient. We simply find the most extreme value and move it to the beginning until we reach our desired index. This can be seen as an incomplete selection sort. One advantage includes its ability to be used on linked lists, whereas other methods can require random access.
Language SupportVery few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. One exception is C++, which provides a templated nth_element method with a guarantee of expected linear time. (read: hooray for us!)
In ConclusionIn short, there are many ways to arrive at the same destination (i.e. correctly found data). The only difference is the manner in which the data is sought. What dictates this portion of the project? The parameters. How fast does it need to be? How many resources can it take up? What about processing time? The question go on and on. This is especially true in embedded systems programming where resources (read: memory) are very tight and must be as efficient and optimized to the greatest possible extent. Always get your program to work before you try to optimize. Be aware of what your program takes up and how it uses those resources. As always, Happy Coding!
This post has been edited by KYA: 19 Jul, 2008 - 10:36 AM
Optimization: Selection and Order Statistics
18 Jul, 2008 - 04:16 PM
|