Algorithms in a Nutshell

Selection Sort

Given a pile of cards with numbers on them, a common way to sort the pile is to select and remove the largest card, and then repeat the process until all cards are gone. This approach describes Selection Sort, which sorts in place the elements in A[0,n), as shown in Example 4-8.

Example 4-8. Selection Sort implementation in C

static int selectMax (void **ar, int left, int right,
                      int (*cmp)(const void *,const void *)) {
  int  maxPos = left;
  int  i = left;
  while (++i <= right) {
    if (cmp(ar[i], ar[maxPos])> 0) {
      maxPos = i;
    }
  }

  return maxPos;
}

void sortPointers (void **ar, int n,
                   int(*cmp)(const void *,const void *)) {
  int i;

  /* repeatedly select max in A[0,i] and swap with proper position */
  for (i = n-1; i >=1; i--) {
    int maxPos = selectMax (ar, 0, i, cmp);
    if (maxPos != i) {
      void *tmp = ar[i];
      ar[i] = ar[maxPos];
      ar[maxPos] = tmp;
    }
  }
}

Selection Sort is the slowest of all the sorting algorithms described in this chapter; it requires quadratic time even in the best case (i.e., when the array is already sorted). It repeatedly performs almost the same task without learning anything from one iteration to the next. Selecting the largest element, max, in A takes n−1 comparisons, and selecting the second largest element, second, takes n−2 comparisons—not much progress! Many of these comparisons are wasted, because if an element is smaller than second, it can't possibly be the largest element and therefore had no impact on the computation for max. Instead of presenting more details on this poorly performing algorithm, we now consider Heap Sort, which shows how to more effectively apply the principle behind Selection Sort.