[FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

The selection sort algorithm sorts by finding the smallest element of an array, then the next smallest element, and so forth, using Theta(n) time at each step where n is the number of elements remaining. It is and example of a DecreaseByConstant algorithm and runs in Theta(n2) in both the worst and the best case.

Like InsertionSort, selection sort can be implemented in-place, with the output array appearing as a prefix of the input array:

{{{SelectionSort(A)

• for i = 1 to length(A):
• best = i for j = i+1 to length(A):
• if A[j] < A[best]:

• best = j
swap A[i] and A[best]

}}}

Selection sort is more complicated than InsertionSort, has a slightly larger constant, is no faster asymptotically in the worst case, and is slower in the best case. InsertionSort is almost always a better choice.

2014-06-17 11:58