Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Сортировка выбором - на каждом i-ом шаге алгоритма находим i-ый минимальный элемент и меняем его местами с i-ым элементом в массиве. Таким образом будет получен массив, отсортированный по неубыванию.

---

Принцип работы алгоритма

Сортировка выбором проходит по каждому элементу последовательности и ищет минимальный элемент от текущего элемента (не включая его) и до конца последовательности. Если минимальный элемент меньше текущего элемента последовательности, то они меняются местами. Иначе - алгоритм переходит к следующему элементу.

---

Схематическая работа алгоритма

Есть неотсортированная последовательность данных

Первый шаг

Первый элемент последовательности - 5, ищем минимальный элемент от текущего и до конца последовательности (это будет 1)

В случае, если текущий элемент меньше или равен минимальному элементу, алгоритм переходит дальше. (как произошло в первом случае, когда 5 поменялась с 1 местами) Иначе - меняет их местами до тех пор, пока не дойдём до конца последовательности.

Второй шаг

$4$ меняется местами с $2$:

Третий шаг

$5$ меняется с $3$:

## Четвёртый шаг

$4$ меняется с $4$, так как это минимальный элемент:

Пятый шаг

На последнем шаге $5$ меняется с $5$, так как это единственный элемент:

---

Вычислительная сложность

Вычислительная сложность $O(n^2)$ во всех случаях (лучшем, среднем, худшем).

---

Псевдокод

Функция сортировка_выбором(данные, количество данных)
    Для индекса числа_1 в диапазоне от 0 до количества данных - 2
        Для индекса числа_2 в диапазоне от индекса числа_1 + 1 до количества данных - 1
            Если данные по индексу числа_1 > данные по индексу числа_2
                Меняем местами данные по индексу числа_1 и данные по индексу числа_2
                
    Вернуть данные

---

Реализация на Python

Аннотация:
selection_sort - функция сортировки выбором
array - массив в котором проводится сортировка
min_index - индекс минимального элемента 

def selection_sort(array: list):  
    for i in range(len(array) - 1):  
        min_index = i  
        for k in range(i + 1, len(array)):  
            if array[k] < array[min_index]:  
                min_index = k  
                
        array[i], array[min_index] = array[min_index], array[i]
          
    return array

---

Олимпиадная реализация на C++

Аннотация:
sel_sort - функция сортировки выбором
arr - массив в котором проводится сортировка
size - размер массива
min_i - индекс минимального элемента

int* sel_sort(int* arr, int size) {
  for (int i = 0; i < size - 1; i++) {
    int min_i = i;
    for (int j = i + 1; j < size; j++) {
      if (arr[j] < arr[min_i]) min_i = j;
    }
    if (min_i != i) swap(arr[i], arr[min_i]);
  }
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
comparator - функция сравнения
firstData - первые данные
secondData - вторые данные
array - сортируемый массив
size - размер массива
min_index - индекс минимального элемента

template <typename T>
bool comparator(const T& firstData, const T& secondData) {
  return firstData < secondData;
}

template <typename T>
void selection_sort(T* array, int size,
                    bool (*comparator)(const T&, const T&) = comparator<T>) {
  for (int i = 0; i < size - 1; i++) {
    int min_index = i;
    
    for (int j = i + 1; j < size; j++) {
      if (comparator(array[j], array[min_index])) min_index = j;
    }
    
    if (min_index != i) {
      swap(array[i], array[min_index]);
    }
  }
}