Сортировка посредством выбора

При сортировке посредством выбора^[1] из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например, если применить метод выбора к массиву dcab, каждый проход будет выглядеть так, как показано ниже:

Начало       d c a b
Проход 1     a c d b
Проход 2     a b d c
Проход 3     a b c d

Нижеследующий код демонстрирует простейшую сортировку посредством выбора:

/* Сортировка посредством выбора. */
void select(char *items, int count)
{
  register int a, b, c;
  int exchange;
  char t;

  for(a=0; a < count-1; ++a) {
    exchange = 0;
    c = a;
    t = items[a];
    for(b=a+1; b < count; ++b) {
      if(items[b] < t) {
        c = b;
        t = items[b];
        exchange = 1;
      }
    }
    if(exchange) {
      items[c] = items[a];
      items[a] = t;
    }
  }
}

К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n - 1 раз, а внутренний — в среднем n/2 раз. Следовательно, сортировка посредством выбора требует

1/2(n²-n)

сравнений. Таким образом, это алгоритм порядка n², из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.

^[1]Называется также сортировкой выбором и сортировкой выборками.