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

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

  1. Найти наименьшее значение в списке.
  2. Записать его в начало списка, а первый элемент - на место, где раньше стоял наименьший.
  3. Снова найти наименьший элемент в списке. При этом в поиске не участвует первый элемент.
  4. Второй минимум поместить на второе место списка. Второй элемент при этом перемещается на освободившееся место.
  5. Продолжать выполнять поиcк и обмен, пока не будет достигнут конец списка.

Решение задачи на языке программирования Python:

# Заполняем список из 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]

Сортировка выбором с помощью цикла for и помещения реализации алгоритма в функцию:

from random import randint
N = 10
 
 
def sel_sort(row):
    n = len(row)
    for i in range(n-1):
        m = i
        for j in range(i+1, n):
            if row[j] < row[m]:
                m = j
        row[i], row[m] = row[m], row[i]
 
 
arr = [randint(1, 99) for item in range(N)]
print(arr)
 
sel_sort(arr)
print(arr)

Больше задач в PDF


Решение задач на Python




Все разделы сайта