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

Алгоритм сортировки

Алгоритм заключается в поиске максимума в неотсортированной части массива. При первом проходе ищем максимальный элемент. Найденный максимальный элемент меняем местами с последним элементом массива. Затем проходим по неотсортированной части массива (от первого элемента до предпоследнего) и находим в ней максимум, который затем меняем местами с предпоследним элементом массива. Продолжаем действия, пока не отсортируем полностью.

Визуализация работы алгоритма

Оптимизации

Скорость алгоритма можно увеличить в 2 раза если кроме минимального элемента в неотсортированном подмассиве также находить и максимальный. Максимум при этом перемещать в конец подмассива, а минимум — в начало.

Визуализация работы алгоритма

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

        static void SelectionSort (int arr[])
        {
            for (int i = 0; i < arr.Length; i++)
            {
                int tempmin = arr[i];
                int i_tempmin = i;
                for (int j = i; j < arr.Length; j++)
                {
                    if (arr[j] < tempmin)
                    {
                        tempmin = arr[j];
                        i_tempmin = j;
                    }
                }
                int temp = arr[i];
                arr[i] = tempmin;
                arr[i_tempmin] = temp;
            }
        }

Характеристики алгоритма