SORTING and Searching


Selection Sort

Another possible strategy for sorting elements is minimum finding. With minimum finding, we first find the smallest element in the list. Now, we know that the smallest element in the list is going to be the first element in the sorted order, so we make this element and the first element. At this point, the first element is in it's correct location, so we can concentrate on sorting the rest of the list. How do we do that? The same way, of course!

Like the Insertion Sort algorithm, the Selection Sort algorithm grows a sorted list at the front of the array. It repeatedly finds the smallest element in the unsorted part of the array and sticks on the end of the sorted part of the array. To find the smallest element in the array, it scans the array and keeps track of the smallest element it's seen so far. Once the scan is finished, it knows the smallest element overall.


If your browser recognized the applet tag, you would see an applet here.

A big difference between Insertion Sort and Selection Sort that once an element is moved in Selection Sort, it never moves again, while in Insertion Sort, an element can be moved many times in order to make room for other (smaller) elements at the front of the list. (Go back and run the Insertion Sort applet again if you don't believe me.)

Next, let's look at an application of sorting that doesn't involve phone books.


[Desperately Seeking Simone]