Алгоритмы и структуры данных

Сортировка выбором (Selection sort)

Алгоритм сортировки выбором — один из самых понятных способов упорядочить массив. Он многократно находит минимальный элемент в массиве и перемещает его в начало. Затем алгоритм переходит к поиску минимального элемента в оставшейся части массива и повторяет этот процесс, пока весь массив не будет упорядочен.
a = [...]
for i in range(len(a)):                  # Нужно поместить минимум из a[i:] в позицию a[i]
    min_idx = i                          # Индекс минимального элемента
    for j in range(i + 1, len(a)):       # Находим индекс минимального элемента
        if a[j] < a[min_idx]:            # Если встретится элемент меньше текущего
            min_idx = j                  # Обновляем индекс минимального элемента
    a[i], a[min_idx] = a[min_idx], a[i]  # Меняем a[i] и a[min_idx] местами
print(a)
На каждом шаге алгоритм извлекает минимум из оставшейся части массива и меняет местами текущий элемент и найденный минимум, используя их индексы. Если текущий элемент уже является минимальным, тогда фактически происходит обмен одного и того же элемента, и массив не меняется.
 
Алгоритм сортировки выбором каждый раз ищет минимальный элемент и меняет текущий индекс на индекс этого минимума. То есть на каждой итерации необходимо просмотреть всю неотсортированную часть массива (функция min по сути обходит элементы последовательно, чтобы найти наименьший). Таким образом, совокупное время работы составляет n итераций, каждая из которых выполняет около n сравнений, что в сумме даёт операций.
Давайте проследим, как алгоритм работает на нескольких массивах:
[4, 1, -1, 0, 2, 8]
  1. i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap (обмен) ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap (обмен) ⇒ [-1, 0, 4, 1, 2, 8]
  1. i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap (обмен) ⇒ [-1, 0, 1, 4, 2, 8]
  1. i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap (обмен) ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap (обмен) ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap (обмен) ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
  1. i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap (обмен) ⇒ [-7, 5, 1, -1, -2, 10]
  1. i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap (обмен) ⇒ [-7, -2, 1, -1, 5, 10]
  1. i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap (обмен) ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap (обмен) ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap (обмен) ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap (обмен) ⇒ [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap (обмен) ⇒ [1, 2, 3, 4, 5]
  1. i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap (обмен) ⇒ [1, 2, 3, 4, 5]
  1. i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap (обмен) ⇒ [1, 2, 3, 4, 5]
  1. i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap (обмен) ⇒ [1, 2, 3, 4, 5]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap (обмен) ⇒ [1, 2, 3, 4, 5]

Задача

Дано n целых чисел, требуется отсортировать их по возрастанию с помощью сортировки выбором.

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 1000) — количество элементов в массиве.
Во второй строке содержится n целых чисел , разделённых пробелами ( ≤ ≤ ).

Выходные данные

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

Примеры

Входные данные
Выходные данные
5 5 5 3 2 3
2 3 3 5 5

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue