Selection Sort

See SortingAlgorithms. For more complete reference material see http://www.nist.gov/dads/HTML/sort.html

---

Selection Sort works by finding the smallest/largest item and then placing it at the front/back. Runtime analysis:

                Worst case  Average case  Best case
 Comparisons      O(n^2)       O(n^2)        O(n)
 Swaps             O(n)         O(n)         O(1)

The "best case" analysis assumes the "stop early" strategy is used, checking that things are in order as you run along. If comparisons are expensive and swaps cheap you'd be better using InsertionSort.

---

Example Code:

The first version uses YAGNI - hence the selection is done in-line because the abstraction isn't needed.

  void insertionSort(int A[], int n)
  {
    int i,j,m;
    while (n>1)
    {
       m = A[0]; j = 0;
       for (i=1;i<n;i++)
          if (m<A[i]) m = A[i], j = i;
       swap(A,--n,j);
    }
  }

This second version uses ShortMethods - "Factor out units of semantic meaning, even if they are only ever used once. "

  void insertionSort(int A[], int n)
  {
    while (n>1)
    {
       int j;
       j = indexOfLargest(A, n);
       swap(A,--n,j);
    }
  }

  int indexOfLargest(int A[], int n)
  {
    int i, j, m;
    m = A[0]; j = 0;

    for (i=1;i<n;i++)
      if (m<A[i])
        m = A[i], j = i;
    return j;
  }

You might think that this last algorithm is the equivalent of BubbleSort, but it isn't. This only does n exchanges to get every item to its correct place.

This third version is in the StlStyle:

  template<typename ForwardIterator?>
  void SelectionSort(ForwardIterator? start, ForwardIterator? stop)
  {
    for(; start != stop; ++start)
      std::iter_swap(std::min_element(start, stop), start);
  }

Of course, this isn't an optimal implementation (the last element is swapped with itself).

---

Moved here from SortingAlgorithms (RefactorMe):

SelectionSort: sweep your data to find the largest element and swap that with the last element. Repeat on smaller and smaller initial arrays. You perform an exchange almost every time because the largest item in the original array is almost never at the end. Complexity is (n-1)*(n-2)/2 comparisons and n exchanges. When coded in-line in C, possibly the smallest code. Can easily be stable.

There is a "stop early" strategy:

  For each sweep:
    set "sorted_so_far" to "true".
    As you sweep:
      If the item you're looking at is more than max_so_far:
        update max_so_far and the index pointing to it.
      If the item you're looking at is less than max_so_far:
        set "sorted_so_far" to false.

At the end of any sweep, if "sorted_so_far" is still true, then the array is sorted and you can stop early.

This is can be the most economical sort to choose if you perform each selection interleaved with other work, and that work may abort the sort operation. For example, an AlphaBetaSearch? is most efficient if most valuable edges ("moves") are traversed first. SelectionSort can pick out the estimated most valuable edge to traverse, with a high probability of an immediate beta cutoff. A cutoff would eliminate the need to sort any further edges, thus saving the work that would have been required to do a full sort of the edges.

---

CategoryAlgorithm