Внимание! Практически весь материал этой лекции был в видеолекции.

class=»embed-responsive-item»



Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.

Есть массив чисел. Нужно его отсортировать. Для простоты будем считать, что мы сортируем целые числа в порядке возрастания (от меньшего к большему). Существует несколько известных способов провернуть этот процесс. Плюс, вы всегда можете пофантазировать на тему и придумать модификацию алгоритма. 

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

Алгоритмы сортировки. Сортировка выбором - 1

Основная идея — разбить наш список на две части, отсортированную и неотсортированную. На каждом шаге алгоритма новое число перемещается из неотсортированной части в отсортированную, и так пока все числа не окажутся в отсортированной части. 

  1. Находим минимальное неотсортированное значение.
  2. Меняем местами это значение с первым неотсортированным значением, ставя его таким образом в конец отсортированного массива.
  3. Если остались неотсортированные значения, возвращаемся к шагу 1.

На первом шаге все значения являются неотсортированными. Назовем неотсортированную часть — Unsorted, а отсортированную — Sorted (это просто английские слова, и делаем мы это только потому, что Sorted — гораздо короче, чем «Отсортированная часть» и будет лучше смотреться на картинках). 

Алгоритмы сортировки. Сортировка выбором - 2

Находим минимальное число в неотсортированной части массива (то есть, на этом шаге — во всем массиве). Это число 2. Теперь меняем его с первым среди неотсортированных и ставим его в конец отсортированного массива (на этом шаге — на первое место). На этом шаге это первое число в массиве, то есть 3.

Алгоритмы сортировки. Сортировка выбором - 3

Шаг второй. На число 2 мы не смотрим, оно уже в отсортированном подмассиве. Начинаем искать минимальное, начиная со второго элемента, это 5. Убеждаемся, что 3 — минимальное среди неотсортированных, 5 — первое среди неотсортированных. Меняем их местами и прибавляем 3 к отсортированному подмассиву. 

Алгоритмы сортировки. Сортировка выбором - 4

На третьем шаге мы видим, что в неотсортированном подмассиве самое маленькое число — 4. Меняем его с первым числом среди неотсортированных — 5. 

Алгоритмы сортировки. Сортировка выбором - 5

На четвертом шаге мы обнаруживаем, что в неотсортированном массиве минимальное число — 5. Меняем его с 6 и прибавляем к отсортированному подмассиву. 

Алгоритмы сортировки. Сортировка выбором - 6

Когда среди неотсортированных остается только одно число (наибольшее), это значит, что весь массив отсортирован! 

Алгоритмы сортировки. Сортировка выбором - 7

Вот как выглядит реализация массива в коде. Попробуйте сделать его самостоятельно. 

Алгоритмы сортировки. Сортировка выбором - 8

В обоих, самом лучшем и самом худшем случаях, чтобы найти минимальный неотсортированный элемент, мы должны сравнить каждый элемент с каждым элементом неотсортированного массива, и делать это мы будем на каждой итерации. Но нам нужно просматривать не весь список, а только неотсортированную часть. Меняет ли это скорость алгоритма? На первом шаге для массива из 5 элементов мы делаем 4 сравнения, на втором — 3, на третьем — 2. Чтобы получить количество сравнений, нам нужно сложить все эти числа. Мы получаем сумму

Алгоритмы сортировки. Сортировка выбором - 9

Таким образом, ожидаемая скорость алгоритма в лучшем и худшем случае — Θ(n2) = O(n2)

Не самый эффективный алгоритм! Тем не менее, для учебных целей и для небольших массивов данных — вполне применимый.