(more info)
Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS
Login
 create new user name: pass: forget your password?
Main Menu
 sections EncyclopædiaPapersBooksExpositionsmeta Requests (170)Orphanage Unclass'd Unproven (415)Corrections (64)Classificationtalkback PollsForumsFeedbackBug Reportsdownloads SnapshotsPM Bookinformation NewsDocsWikiChangeLogTODO ListLegaleseAbout
 selection sort (Algorithm)

## The Problem

See the Sorting Problem.

## The Algorithm

Suppose is the initial list of unsorted elements. The selection sort algorithm sorts this list in steps. At each step , find the largest element such that , and swap it with the element at . So, for the first step, find the largest value in the list and swap it with the last element in the list. For the second step, find the largest value in the list up to (but not including) the last element, and swap it with the next to last element. This is continued for steps. Thus the selection sort algorithm is a very simple, in-place sorting algorithm.

## Pseudocode

Algorithm SELECTION_SORT(L, n)
Input: A list of elements
Output: The list in sorted order

begin

end

## Analysis

The selection sort algorithm has the same runtime for any set of elements, no matter what the values or order of those elements are. Finding the maximum element of a list of elements requires comparisons. Thus , the number of comparisons required to sort a list of elements with the selection sort, can be found:

However, the number of data movements is the number of swaps required, which is . This algorithm is very similar to the insertion sort algorithm. It requires fewer data movements, but requires more comparisons.

"selection sort" is owned by mathcam. [ full author list (2) | owner history (2) ]
(view preamble)

 View style: HTML with imagespage imagesTeX source

See Also: insertion sort, sorting problem

Cross-references: insertion sort, order
There is 1 reference to this entry.

This is version 2 of selection sort, born on 2001-10-08, modified 2004-04-27.
Object id is 182, canonical name is SelectionSort.
Accessed 7003 times total.

Classification:
 AMS MSC: 68P10 (Computer science :: Theory of data :: Searching and sorting)

 Pending Errata and Addenda
 None.[ View all 2 ]
 Discussion
 Style: FlatThreaded Expand: allnone123456789 Order: Oldest FirstNewest first forum policy
 Linking Bug? by mathcam on 2004-07-13 15:46:45
 I'm having a hard time fixing this correction. Every time I try to force the link, it replace "The Sorting Problem" with "@@@@@" or something to that effect. Anyone seen this before?Cam
[ reply | up ]

 Interact rate | post | correct | update request | add example | add (any)