TOPIC

Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:

1. ordering: arranging items of the same kind, class, nature, etc. in some ordered sequence,
2. categorizing: grouping and labeling items with similar properties together.

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Selection sort can also be used on list structures that make add and remove efficient, such as a linked list. In this case it is more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far. For example:

64 25 12 22 11

11 64 25 12 22

11 12 64 25 22

11 12 22 64 25

11 12 22 25 64

/* a[0] to a[n-1] is the array to sort */
int iPos;
int iMin;
 
/* advance the position through the entire array */
/*   (could do iPos < n-1 because single element is also min element) */
for (iPos = 0; iPos < n; iPos++) {
    /* find the min element in the unsorted a[iPos .. n-1] */
 
    /* assume the min is the first element */
    iMin = iPos;
    /* test against all other elements */
    for (i = iPos+1; i < n; i++) {
        /* if this element is less, then it is the new minimum */  
        if (a[i] < a[iMin]) {
            /* found new minimum; remember its index */
            iMin = i;
        }
    }
 
    /* iMin is the index of the minimum element. Swap it with the current position */
    if ( iMin != iPos ) {
        swap(a, iPos, iMin);
    }
}

Mathematical definition

Let L be a non-empty set and such that f(L) = L' where:

1. L' is a permutation of L,
2. for all and ,
3. ,
4. s is the smallest element of L, and
5. L_s is the set of elements of L without one instance of the smallest element of L.

Analysis

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n²) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).