Selection sort is a sorting algorithm, a comparison sort that works as follows:

1. find the minimum value in the list
2. swap it with the value in the first position
3. sort the remainder of the list (excluding the first value)

It is probably the most intuitive sort algorithm to invent.

This algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n²), assuming that comparisons can be done in constant time. Among simple O(n²) algorithms, it is generally outperformed by insertion sort, but still tends to outperform contenders such as bubble sort and gnome sort.

Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), this algorithm is stable (but slower). Selection sort is an in-place algorithm.

Heapsort greatly improves the basic algorithm by using an implicit heap data structure to speed up finding and removing the lowest datum.

A bidirectional variant of selection sort, called shaker sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. Note, however, that shaker sort more often refers to a bidirectional variant of bubble sort.

__NOTOC__

Implementations

C

// selection sort function module in C
void selectionSort(int data*, int count)
{
	int i, j, m, mi;
        for (i = 0; i < count - 1; i++) {
        	/* find the minimum */
        	mi = i;
                for (j = i+1; j < count; j++) {
        	    if (data< data[mi) {
	        	mi = j;
        	    }
        	}
	        m = data*;
        	/* move elements to the right */
        	for (j = mi; j > i; j--) {
        	    data= data[j-1;
        	}
        	data* = m;
        }
}

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 138–141 of Section 5.2.3: Sorting by Selection.

External links

• Selection Sort Demo
• Selection Sort Demo
• Selection Sort Demonstration
• Pointers to selection sort visualizations

Sort algorithms

Selectionsort | Ordenamiento por selección | Tri par sélection | 선택 정렬 | Selection sort | מיון בחירה | Išrinkimo rūšiavimo algoritmas | 選択ソート | Sortowanie przez wybieranie | Selection sort | Сортировка методом выбора | 选择排序