"Выборочная" сортировка

¹ : В лучшем случае тоже достигается квадратичная сложность, так как на каждом шаге мы обязаны пройтись по всему оставшемуся массиву для поиска минимума.

Алгоритм

Selection sort — простая и эффективная сортировка, которая как и Insertion sort условно делит массив на две части (отсортированную и неотсортированную), только изначально кол-во элементов в отсортированной части - 0. Далее алгоритм ищет минимальный элемент в неотсортированной части и добавляет его в отсортированную. Данный процесс повторяется, пока все элементы не перейдут в отсортированный массив

1. Не используется дополнительная память.
2. Лёгкий для понимания и воспроизведения алгоритм.
3. Эффективен для маленьких массивов.

Недостатки алгоритма

1. Сложность $O(n^2)$ в худшем и среднем случаях
2. Нестабильный алгоритм

Реализация алгоритма

void selectionSort(int* a, int n) {
  int i, j, min_ind;

  // Рассматривание минимального элемента в неотсортированной части и заполнение
  // отсортировнного
  for (i = 0; i < n - 1; i++) {
    // Поиск минимального элемента(его индекса)
    min_ind = i;

    for (j = i + 1; j < n; j++) {
      if (a[j] < a[min_ind]) {
        min_ind = j;
      }
    }

    // Замена первого элемента неотсортированного массива на его минимальный
    // элемент
    if (min_ind != i) {
      std::swap(a[min_ind], a[i]);
    }

    // В окончании цикла совершается операция i++, которая сдвигает указатель на
    // начало неотсортированной части массива
  }
}

Почему не стабильная?

Selection Sort не является устойчивым алгоритмом сортировки, поскольку меняет местами несмежные элементы. Например, при задании [2, 2, 1] значения 2 не сохранят свой первоначальный порядок в в выходном отсортированном массиве.

Запуск функции сортировки selectionSort(array, size);

Ввод:

12 865 -1233 47 2

Работа алгоритма

Знак | отделяет отсортированную часть от неотсортированной 0. Изначальный массив: { | 12 865 -1233 47 2 }

1. Ищем минимальный элемент в массиве (-1233), меняем его местами с первым элементом, итоговый массив: { -1233 | 865 12 47 2 }
2. Повторяем: { -1233 2 | 12 47 865 }
3. { -1233 2 12 | 47 865 }
4. { -1233 2 12 47 | 865 }
5. { -1233 2 12 47 865 | } - Ура! Весь массив отсортирован! ПОБЕДАААААА!

Вывод:

-1233 2 12 47 865