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

Алгоритм сортировки выбором заключается в поиске на необработанном срезе массива или списка минимального значения и в дальнейшем обмене этого значения с первым элементом необработанного среза. На следующем шаге необработанный срез уменьшается на один элемент. 

  1. Найти наименьшее значение в списке.
  2. Записать его в начало списка, а первый элемент - на место, где раньше стоял наименьший.
  3. Снова найти наименьший элемент в списке. При этом в поиске не участвует первый элемент.
  4. Второй минимум поместить на второе место списка. Второй элемент при этом перемещается на освободившееся место.
  5. Продолжать выполнять поиcк и обмен, пока не будет достигнут конец списка.
# Заполняем список из 10 элементов
# случайными числами от 1 до 99 и
# выводим неотсортированный список на экран.
from random import randint
N = 10
arr = []
for i in range(N):
    arr.append(randint(1, 99))
print(arr)
 
 
# В цикле переменная i хранит индекс ячейки,
# в которую записывается минимальный элемент.
# Сначала это будет первая ячейка.
i = 0
 
# N - 1, так как последний элемент
# обменивать уже не надо.
while i < N - 1:
 
    # ПОИСК МИНИМУМА
    # Сначала надо найти минимальное значение
    # на срезе от i до конца списка.
    # Переменная m будет хранить индекс ячейки
    # с минимальным значением.
    # Сначала предполагаем, что
    # в ячейке i содержится минимальный элемент.
    m = i
    # Поиск начинаем с ячейки следующей за i.
    j = i + 1
    # Пока не дойдем конца списка,
    while j < N:
        # будем сравнивать значение ячейки j,
        # со значением ячейки m.
        if arr[j] < arr[m]:
            # Если в j значение меньше, чем в m,
            # сохраним в m номер найденного
            # на данный момент минимума.
            m = j
        # Перейдем к следующей ячейке.
        j += 1
 
    # ОБМЕН ЗНАЧЕНИЙ
    # В ячейку i записывается найденный минимум,
    # а значение из ячейки i переносится
    # на старое место минимума.
    arr[i], arr[m] = arr[m], arr[i]
 
    # ПЕРЕХОД К СЛЕДУЮЩЕЙ НЕОБРАБОТАННОЙ ЯЧЕЙКЕ
    i += 1
 
 
# Вывод отсортированного списка
print(arr)

Пример выполнения:

[77, 46, 11, 89, 48, 14, 67, 73, 22, 26]
[11, 14, 22, 26, 46, 48, 67, 73, 77, 89]

Функция сортировки выбором:

from random import randint
 
 
def sel_sort(array):
    for i in range(len(array) - 1):
        m = i
        j = i + 1
        while j < len(array):
            if array[j] < array[m]:
                m = j
            j = j + 1
        array[i], array[m] = array[m], array[i]
 
 
a = []
for i in range(10):
    a.append(randint(1, 99))
 
print(a)
sel_sort(a)
print(a)

Создано

Обновлено