Компьютерные алгоритмы – сортировки

Поговорим про алгоритмы сортировки данных.

В прошлой серии мы говорили про Big O нотацию и бинарный поиск.

Давайте сегодня посмотрим на алгоритмы сортировок — без них в CS никуда.

Прежде чем начать про них разговор, давай разберемся с таким понятием, как рекурсия.

Почему-то некоторых она сильно пугает, однако – это очень простое понятие, которое легче всего иллюстрируется любимым фильмом.

Все очень просто — пока выполняется некое условие, функция вызывает сама себя. Когда условие не выполняется - код перестает себя вызывать и делает что-то другое.

Если искать примеры в реальной жизни, то в качестве рекурсии можно в пример привести чулан, который наполнен коробками из Ikea. У них есть совершенно разные коробки - большие, средние, маленькие, очень маленькие, и очень-очень маленькие. Представьте, вам нужно найти пару носок, которые были подарены на гендерный праздник 5 лет назад и в тот же день убраны в чулан. За 5 лет было много уборок, перестановок и пара переездов поэтому маленькую коробку с носками положили в коробку побольше, а коробку побольше в совсем большую. Открываете чулан, перед вами полдюжины одинаковых коробок. Что делать ? Правильно, начинать с первой большой коробки, и смотреть все внутри нее. Когда в первой большой коробке всё посмотрели - смотрим следующую большую. И так пока коробки не закончатся или не будут найдены носки. Как только носки найдены - задача достигнута.

А вот пример кодом - скажем, посчитаем от числа N до 0. Как только досчитали до нуля - пишем в консоль «Танцуют все!👯‍♀»

Выполнив функцию, увидем в консоле такое:

Current count 5 Current count 4 Current count 3 Current count 2 Current count 1 Танцуют все!👯‍♀️

При первом вызове функции, она вызывается с аргументом «5». Зайдя в тело функции, if выражение видит, что count не равен 0, он равен 5. А раз так, то функция вызывает сама себя, вычитая из 5 цифру 1. И все это повторяется, пока мы не досчитали до 0.

И это вся рекурсия.

Самое главное - когда будете писать, не забывайте об условии выхода из рекурсии. В моем примере это countsLeft == 0.

Теперь к алгоритмам сортировок.

Это очень простая сортировка. Мы часто пользуемся ей в реальной жизни - например, когда играем в пятикарточный покер или червы. Держа в руке карты, всегда начинаешь инстинктивно сортировать их в руке, чтобы увидеть комбинацию.

Давайте на коде.

Шаг первый

Объявляем переменную minimum. В нее кладем самый первый элемент массива, те 15.

Шаг второй

Сравниваем минимум с элементом, который идет следующим после минимума. Следующий - второй.

Если следующий элемент меньше - делаем его минимумом.

Повторяем процедуру сравнения минимума со следующим элементом, пока не дойдем до конца массива.

Как только дошли до конца массива - кладем минимум в самое начало массива.

Делаем повтор первого и второго шагов для следующего элемента массива.

Сортируем массив [-2, 45, 11, 0, -9]

Расставляем принты, смотрим результат

Устанавливаем минимумом -2 [-2, 45, 11, 0, -9] Меняем минимум с -2 на -9, тк число меньше текущего минимума Меняем новый минимум на старый для [-2, 45, 11, 0, -9] Получаем результат [-9, 45, 11, 0, -2] Устанавливаем минимумом 45 [-9, 45, 11, 0, -2] Меняем минимум с 45 на 11, тк число меньше текущего минимума Меняем минимум с 11 на 0, тк число меньше текущего минимума Меняем минимум с 0 на -2, тк число меньше текущего минимума Меняем новый минимум на старый для [-9, 45, 11, 0, -2] Получаем результат [-9, -2, 11, 0, 45] Устанавливаем минимумом 11 [-9, -2, 11, 0, 45] Меняем минимум с 11 на 0, тк число меньше текущего минимума Меняем новый минимум на старый для [-9, -2, 11, 0, 45] Получаем результат [-9, -2, 0, 11, 45] Устанавливаем минимумом 11 [-9, -2, 0, 11, 45] Устанавливаем минимумом 45 [-9, -2, 0, 11, 45] Результат: [-9, -2, 0, 11, 45]

Selection sort делает (n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2 сравнений что примерно получается n в квадрате.

Таким образом его сложность - O(n²)

Представьте, что у вас магазин мужских костюмов. Каждую среду поставщик привозит несколько новых костюмов, которые нужно выставить на витрину. Как только их привезли - логично будет их повесить сразу, чтобы они не собирали пыль. Повесив их на витрину к уже продающимся, у вас получается 2 части костюмов - новые, не сортированные по размеру, и те, которые уже были раньше - они висят в правильном порядке. Дальше берете каждый новый костюм и двигаете его в нужное место.

А шаги для имплементации алгоритма будут следующие:

Проходимся циклом по всем элементам массива, начиная с array[1] до конца массива.В начале каждого цикла объявляем ключом текущий элемент
Если ключ меньше, чем элемент перед ним, то продвигаем предыдущий элемент на одну позицию вперед.

Слоумо алгоритма.

И иллюстрация работы алгоритма в исполнении румынского ансамбля.

Песни, пляски и танцы. В главной роли – Selection Sort.

Сложность алгоритма зависит от состояния данных.

Если массив уже отсортирован, то сложность будет O(n) - тк надо будет пробежаться по каждому объекту.

Если массив не сортирован, то сложность будет n*(n-1) что приблизительно равно n², те O(n²)

Мы добрались до алгоритма, который использует рекурсию. Merge Sort - построен на базе алгоритма Divide and Conquer, у него логика следующая - проблема последовательно упрощается до состояния, с которым работать проще всего. Так называемый базовый кейс.

На примере Merge Sort это работает так - исходный массив разбивается на небольшие массивы, а каждый небольшой массив разбивается до тех пор, пока в массиве не останется 1 объект.