Как работает сортировка выбором? В чем ее особенности?

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

Алгоритм делит массив на две части:

• отсортированную левую часть;
• неотсортированную правую часть.

Сначала отсортированная часть пуста. После каждого шага она увеличивается на один элемент.

Идея алгоритма

Для сортировки по возрастанию:

1. Найти минимальный элемент во всем массиве.
2. Поменять его с первым элементом.
3. Найти минимальный элемент среди оставшихся.
4. Поменять его со вторым элементом.
5. Продолжать, пока массив не будет отсортирован.

Пример

Исходный массив:

[4, 2, 5, 1]

Первый шаг: минимальный элемент 1, меняем с первым.

[1, 2, 5, 4]

Второй шаг: среди [2, 5, 4] минимум 2, он уже на месте.

Третий шаг: среди [5, 4] минимум 4, меняем.

[1, 2, 4, 5]

Код

function selectionSort(values) {
  const result = [...values];

  for (let i = 0; i < result.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < result.length; j++) {
      if (result[j] < result[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      const temp = result[i];
      result[i] = result[minIndex];
      result[minIndex] = temp;
    }
  }

  return result;
}

function selectionSort(values: number[]): number[] {
  const result = [...values];

  for (let i = 0; i < result.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < result.length; j++) {
      if (result[j] < result[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      const temp = result[i];
      result[i] = result[minIndex];
      result[minIndex] = temp;
    }
  }

  return result;
}

func selectionSort(values []int) []int {
  result := append([]int(nil), values...)

  for i := 0; i < len(result)-1; i++ {
    minIndex := i

    for j := i + 1; j < len(result); j++ {
      if result[j] < result[minIndex] {
        minIndex = j
      }
    }

    if minIndex != i {
      result[i], result[minIndex] = result[minIndex], result[i]
    }
  }

  return result
}

public class Example {
  static int[] selectionSort(int[] values) {
    int[] result = java.util.Arrays.copyOf(values, values.length);

    for (int i = 0; i < result.length - 1; i++) {
      int minIndex = i;

      for (int j = i + 1; j < result.length; j++) {
        if (result[j] < result[minIndex]) {
          minIndex = j;
        }
      }

      if (minIndex != i) {
        int temp = result[i];
        result[i] = result[minIndex];
        result[minIndex] = temp;
      }
    }

    return result;
  }
}

def selection_sort(values):
  result = values.copy()

  for i in range(len(result) - 1):
    min_index = i

    for j in range(i + 1, len(result)):
      if result[j] < result[min_index]:
        min_index = j

    if min_index != i:
      result[i], result[min_index] = result[min_index], result[i]

  return result

Сложность

Сортировка выбором всегда ищет минимум в оставшейся части массива. Поэтому число сравнений почти не зависит от исходного порядка.

Сложность:

• худший случай: O(n²);
• средний случай: O(n²);
• лучший случай: O(n²);
• дополнительная память: O(1), если сортировать на месте.

Особенности

Мало обменов

В отличие от пузырьковой сортировки, сортировка выбором делает не больше n - 1 обменов. Это полезно, если операция обмена дорогая.

Неустойчивость

Классическая сортировка выбором обычно не является устойчивой. Это значит, что равные элементы могут изменить относительный порядок.

Простота

Алгоритм легко понять и реализовать, поэтому его часто используют в учебных курсах.

Низкая практическая эффективность

Для больших массивов сортировка выбором не подходит из-за квадратичной сложности.

Когда может быть уместна

Сортировка выбором может быть приемлема:

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

Вывод

сортировка выбором на каждом шаге выбирает минимальный элемент и переносит его в начало неотсортированной части. Она проста и требует мало обменов, но имеет сложность O(n²).