Как реализовать алгоритм сортировки выбором на Go?

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

Эффективность и практическое применение

Прежде чем погрузиться в код, давайте оценим алгоритм с практической стороны.

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

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

Временная сложность — О(n²) как в худшем, так и в среднем и лучшем случаях. Это связано с тем, что алгоритм выполняет два вложенных цикла, сравнивая каждый элемент с каждым (хотя и не полностью).

Пространственная сложность — О(1), так как сортировка происходит in-place, то есть прямо в исходном слайсе, без выделения дополнительной памяти.

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

Давайте рассмотрим чистую и понятную реализацию с подробными комментариями к каждому логическому блоку.

package main

import "fmt"

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

    for i := 0; i < n-1; i++ {
        minIndex := i
    
        for j := i + 1; j < n; j++ {
            if slice[j] < slice[minIndex] {
                minIndex = j
            }
        }

        slice[i], slice[minIndex] = slice[minIndex], slice[i]
    }

    return slice
}

func main() {
    someSlice := []int{64, 25, 12, 22, 11}
    fmt.Println(selectionSort(someSlice))
}

Пошаговое объяснение логики:

1. Внешний цикл (for i): Отвечает за границу между отсортированной (слева) и неотсортированной (справа) частями слайса. На каждом шаге он выбирает место, куда будет помещен следующий минимальный элемент.
2. Инициализация minIndex: Начинаем с предположения, что самый маленький элемент в неотсортированной части находится на ее начале (позиция i).
3. Внутренний цикл (for j): Это «поисковик» минимума. Он просматривает все элементы, стоящие после i, чтобы проверить наше предположение.
4. Обновление minIndex: Если находится элемент меньше текущего кандидата (slice[j] < slice[minIndex]), индекс минимума обновляется.
5. Обмен элементов (swap): После завершения внутреннего цикла становится точно известно, где находится самый маленький элемент в неотсортированной части. Меняется его элемент на позиции i, расширяя отсортированный участок на один элемент.

Трассировка алгоритма сортировки выбором

Давайте прогоним алгоритм для someSlice := []int{64, 25, 12, 22, 11} и посмотрим, как меняется состояние слайса.

Шаг 1 (i = 0)

Начальное состояние: [64, 25, 12, 22, 11]

1. Поиск минимума:

• minIndex = 0 (значение 64)
• 25 < 64 - true → minIndex = 1
• 12 < 25 - true → minIndex = 2
• 22 < 12 - false → minIndex — не меняется
• 11 < 12 - true → minIndex = 4

2. Обмен:

• Меняем местами элементы на позициях 0 и 4: slice[0] = 11, slice[4] = 64
• Результат: [11, 25, 12, 22, 64]

Шаг 2 (i = 1)

1. Поиск минимума в [25, 12, 22, 64]:

• minIndex = 1 (значение 25)
• 12 < 25 - true → minIndex = 2
• 22 < 12 - false → minIndex — не меняется
• 64 < 12 - false → minIndex — не меняется

2. Обмен:

• Меняем местами элементами на позициях 1 и 2: slice[1] = 12, slice[2] = 25
• Результат: [11, 12, 25, 22, 64]

Шаг 3 (i = 2)

1. Поиск минимума в [25, 22, 64]

• minIndex = 2 (значение 25)
• 22 < 25 - true → minIndex = 3
• 64 < 22 - false → minIndex не меняется

2. Обмен

• Меняем местами элементы на позициях 2 и 3: slice[2] = 22, slice[3] = 25
• Результат: [11, 12, 22, 25, 64]

Шаг 4 (i = 3)

1. Поиск минимума в [25, 64]:

• minIndex = 3 (значение 25)
• 64 < 25 - false → minIndex не меняется

2. Обмен:

• Меняем местами элементы на позициях 3 и 3  (обмен с самим собой)

Финальный результат: [11, 12, 22, 25, 64]

Важные нюансы реализации на Go

1. In-place сортировка: Функция модифицирует исходный слайс. Если нужно сохранить оригинал — нужно сделать копию в начале функции: sorted := make([]int, len(slice)); copy(sorted, slice) и работайте с sorted.
2. Обмен без временной переменной: В Go можно менять значения местами с помощью кортежного присваивания slice[i], slice[minIndex] = slice[minIndex], slice[i]. Это идиоматично и удобно.
3. Универсальность: Данная реализация работает только с []int. Чтобы сортировать другие типы, нужно использовать интерфейсы (например, sort.Interface) или дженерики (с версии Go 1.18+), но это тема для отдельной статьи.

Ключевой вывод

Сортировка выбором — это классический алгоритм, который должен быть в арсенале каждого разработчика, прежде всего для понимания основ. Он нагляден, прост в реализации, но имеет серьезные ограничения по производительности на больших наборах данных.

Напишите в комментариях, а какие еще классические алгоритмы вы хотели бы разобрать в контексте Go?