В предыдущей части мы познакомились с O-нотацией для оценки вычислительной сложности алгоритмов, и теперь попробуем применить эту нотацию к нескольким известным методам сортировки данных.
Постановка задачи
Дан массив размером N, который заполнен случайными (то есть никак специально не упорядоченными) числами. Необходимо расставить в этом массиве числа в порядке возрастания.
Методы решения
Начнём с самого тупого и смешного. Вы наверняка подумали про сортировку пузырьком, но нет. Сортировка пузырьком будет дальше, а пока есть кое-что тупее. Это...
Случайная перестановка!
Мы будем просто расставлять числа в массиве случайным образом до тех пор, пока не получим отсортированный массив. Звучит абсурдно? Да. Но это рабочий алгоритм! При условии, конечно, что случайная расстановка – истинно случайна.
Допустим, в массиве есть 2 элемента. Значит, есть всего 2 варианта перестановки: 1-2 или 2-1. Причём один из вариантов – это уже отсортированый массив. Пока неплохо, правда? Можно отсортировать массив всего с двух попыток (в среднем). Если элементов 3, то количество возможных расстановок равно 2*3 = 6. Если 4, то 2*3*4 = 24. Видите, как резко растёт число вариантов? Иначе говоря, при N элементах в массиве получается N! (N факториал) возможных расстановок. И лишь одна из них правильная. Значит, для получения правильной расстановки нужно (в среднем) сделать N! попыток.
Таким образом, мы оценили сложность данного алгоритма как O(N!), и она никуда не годится.
Школьное решение
В школах проходят простейшую сортировку. Она работает так:
- Найти в массиве минимальный элемент, начиная с первого элемента
- Поменять этот элемент местами с первым элементом
- Найти в массиве минимальный элемент, начиная со второго элемента
- Поменять этот элемент местами со вторым элементом
- Найти в массиве минимальный элемент, начиная с третьего элемента...
Это значит: мы проходим по массиву циклом, перебирая каждый его элемент. Цикл повторяется N-1 раз, т.к. последний элемент перебирать уже не надо. Начиная с текущего элемента в цикле (назовём его i), мы перебираем оставшиеся N-i элементов, чтобы найти среди них минимальный элемент.
Примеры будут на языке Python.
Значит, вся последовательность циклов выглядит так: N элементов + N-1 элементов + N-2 элементов и т.д. Если записать её задом наперёд, то получим более привычное:
1 + 2 + 3 + ... + N
Сумма этого ряда вычисляется как (N²+N)/2. Чтобы это понять, посмотрите на геометрическое пояснение:
Асимптотическая сложность при N→∞ будет всё же O(N²). Что ж, это квадратичная зависимость, тоже плохая, но значительно лучше, чем O(N!)
Сортировка пузырьком
Она очень забавна как идея и проста в реализации. Мы берём последний элемент массива и считаем его пузырьком воздуха, который находится в самом низу. Потом мы сравниваем его с вышележащим (то есть предпоследним) элементом. Если пузырёк "легче", то он "всплывает", меняясь местами с элементом, который был выше. На следующем шаге он опять сравнивается с вышележащим элементом, и т.д.
А если пузырёк "тяжелее"? Тогда ему некуда подниматься, мы оставляем его в покое и берём вышележащий элемент, делая теперь уже его пузырьком.
Выбранный пузырёк может дойти до самого верха массива, постоянно меняясь местами с другими элементами. Это приведёт к тому, что там, где стояли одни элементы, теперь могут стоять другие. Значит, нужно будет опять пускать пузырёк с самого последнего элемента. Чтобы все пузырьки гарантированно выстроились по порядку, нужно повторить запуск снизу N-1 раз.
Здесь у нас опять сумма циклов 1+2+3+...+N, и значит та же самая квадратичная зависимость O(N²).
Однако у пузырька есть одно хорошее свойство. Если мы прошли снизу доверху и ни разу не переставили элементы друг с другом, то значит они уже отсортированы. Следовательно, как только мы встретим такую ситуацию, то можем досрочно прекращать сортировку. Для этого нужно просто добавить в алгоритм счётчик сделанных перестановок и его проверку:
И тогда мы всё ещё имеем квадратичную зависимость, но в худшем случае. А в лучшем случае, то есть когда данные отсортированы или почти отсортированы, мы пустим пузырьки всего несколько раз, и следовательно оценка становится просто O(N).
Обратите внимание, что в предыдущем (школьном) методе сортировки такой возможности нет – даже если ему дать уже отсортированные данные, он всё равно не сможет это определить и будет пытаться их сортировать.
Следующая часть: Сортировка подсчётом