Optimization: Selection and Order Statistics

Page 1 of 1

0 Replies - 4544 Views - Last Post: 18 July 2008 - 04:16 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=57964&amp;s=8ee244a93062167d177739b2e10ecace&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 KYA

• Wubba lubba dub dub!

Reputation: 3186
• Posts: 19,211
• Joined: 14-September 07

Optimization: Selection and Order Statistics

Posted 18 July 2008 - 04:16 PM

Selection Algorithms

By 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 Sorting

This 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.

```	 //sort
int min = arrayOne[0];
int max = arrayOne[n-1];

//easy and quick, no?

```

Linear Selection

This 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.

```	 int max = 0;
while (!done)
//user input
if (userInput > max)
max = userInput

//so on and so forth

```

Nonlinear general selection algorithm

This 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 Support

Very 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 Conclusion

In 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 July 2008 - 10:36 AM

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul{list-style-type:circle;font-size:12px;font-weight:bold;}.related li{margin-bottom:5px;background-position:left 7px!important;margin-left:-35px;}.related h2{font-size:18px;font-weight:bold;}.related a{color:blue;}