Найдите минимум и поместите его в левый конец

Сложность

  • O(n²)

Алгоритм

  1. Выберите первый элемент списка
  2. найти наименьший элемент среди остальных
  3. поменять местами первый элемент с наименьшим
  4. повторяйте 1 ~ 3 со вторым элементом, пока не дойдете до конца списка

Сравнение с пузырьковой сортировкой

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

  • Найдите наименьший и поместите его в левый конец. (сортировка пузырьком в конечном итоге приводит к правильному концу)
  • не нужно постоянно менять местами все элементы, а просто поменять местами самые маленькие. (пузырьковая сортировка продолжает менять местами все элементы, перенося самый большой в правый конец)

питон

def selectionsort(list):
  for i in range(len(list) - 1):
    minIndex = i
    for j in range(i+1, len(list)):
      if list[j] < list[minIndex]:
        minIndex = j
    list[i], list[minIndex] = list[minIndex], list[i] 
  return list
   
list = [12,4,7,4,67,8,9,3,2,7,98,6,4]
print(selectionsort(list))

C++

#include <iostream>
using namespace std;
int minIndex;
void selection(int a[], int s){
    for(int i = 0; i < s-1; i++){
        minIndex = i;
        for(int j = i+1; j < s; j++){
            if(a[j] < a[minIndex]){
                minIndex = j;
            }
        }
        swap(a[i], a[minIndex]);
    }
}
int main()
{
    int a[5] = {5,4,3,1,2};
    selection(a, 5);
    for(int i = 0; i < n; i++){
        cout<<a[i]<<endl;
    }
}