Сортировка выбором

Описание	Сортировка выбором (Selection sort) — алгоритм сортировки.
Область знаний	Информатика
Область использования (ISTE)
Возрастная категория
Поясняющее видео
Близкие рецепту понятия
Среды и средства для приготовления рецепта:

Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый.

Шаги алгоритма:

1. находим номер минимального значения в текущем списке
2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

C++

template <typename type_arr>
void selection_sort(type_arr *arr, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min_index = i;
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }
        if (min_index != i)
        {
            swap(arr[i], arr[min_index]);
        }
    }
}

Java

public static <T extends Comparable<? super T>>
void sort(T[] array) {
        for (int i = 0; i < array.length - 1; ++i) {
            int minPos = i;
            for (int j = i + 1; j < array.length; ++j) {
                if (array[j].compareTo(array[minPos]) < 0) {
                    minPos = j;
                }
            }
            T saveValue = array[minPos];
            array[minPos] = array[i];
            array[i] = saveValue;
        }
    }

Ruby

def selection_sort(array)
	for min in 0..array.count-2
		least = min
		for j in (min + 1)..array.count-1
			if array[j] < array[least]
				least = j
			end
		end
		temp = array[min]
		array[min] = array[least]
		array[least] = temp
	end
end

Swift

func selectionSort<Element>(_ array: inout Array<Element>) where Element: Comparable {
	for min in 0..<array.count - 1 {
		for j in min..<array.count {
			if array[j] < array[min] {
				let temp = array[min]
				array[min] = array[j]
				array[j] = temp
			}
		}
	}
}

Python

def select_sort(A):
    for i in range(len(A)-1):
        for k in range(i+1, len(A)):
            if A[k] < A[i]:
                A[k], A[i] = A[i], A[k]

Go

func selectionSort(nums []int) {
    n := len(nums)

    for i := 0; i < n; i++ {
        min := i 
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[min] {
                min = j
            }
        }
        nums[i], nums[min] = nums[min], nums[i]
    }
}