Слайд 3
🎯 Сортировка выбором (Selection Sort)
Алгоритм сортировки выбором — это улучшенная версия пузырьковой сортировки. Он делает только один обмен за каждый проход по списку. Вместо многократного обмена соседних элементов, он сначала находит максимальный (или минимальный) элемент и помещает его на нужное место.
📘 Идея алгоритма
Для списка длиной n нужно выполнить n - 1 проход.
На каждом проходе ищется максимальный элемент неотсортированной части списка и ставится в конец этой части.
🔹 Пример: сортировка a = [5, 1, 8, 2, 4]
Первый проход:
Находим максимальный элемент 8 и меняем его с последним элементом:
[5, 1, 8, 2, 4] → [5, 1, 4, 2, 8]Второй проход:
Находим максимальный элемент 5 в оставшейся части [5, 1, 4, 2]
и меняем его с предпоследним элементом:
[5, 1, 4, 2, 8] → [2, 1, 4, 5, 8]Третий проход:
Находим максимальный элемент 4 в неотсортированной части [2, 1, 4] —
он уже на своём месте:
[2, 1, 4, 5, 8]Четвёртый проход:
Находим максимальный элемент 2 и меняем его с 1:
[2, 1, 4, 5, 8] → [1, 2, 4, 5, 8]💻 Реализация на Python
a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6, 8, -2, 99]
n = len(a)
for i in range(n - 1):
max_index = 0
for j in range(1, n - i):
if a[j] > a[max_index]: # ищем индекс максимального элемента
max_index = j
a[max_index], a[n - i - 1] = a[n - i - 1], a[max_index] # ставим его в конец
print('Отсортированный список:', a)
Результат:
Отсортированный список: [-67, -3, -2, 0, 1, 6, 7, 8, 9, 12, 34, 45, 99, 1000]⚙️ Поиск минимального вместо максимального
Можно сортировать по возрастанию, находя минимальный элемент и перемещая его в начало. Это даёт тот же результат, но визуально алгоритм движется "слева направо", а не "справа налево".
a = [5, 1, 8, 2, 4]
n = len(a)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if a[j] < a[min_index]: # ищем минимальный элемент
min_index = j
a[i], a[min_index] = a[min_index], a[i] # меняем местами
print('Отсортированный список:', a)
Результат:
Отсортированный список: [1, 2, 4, 5, 8]O(n²).