Методы сортировки и их вычислительная сложность

В предыдущей части мы познакомились с O-нотацией для оценки вычислительной сложности алгоритмов, и теперь попробуем применить эту нотацию к нескольким известным методам сортировки данных.

Постановка задачи

Дан массив размером N, который заполнен случайными (то есть никак специально не упорядоченными) числами. Необходимо расставить в этом массиве числа в порядке возрастания.

Методы решения

Начнём с самого тупого и смешного. Вы наверняка подумали про сортировку пузырьком, но нет. Сортировка пузырьком будет дальше, а пока есть кое-что тупее. Это...

Случайная перестановка!

Мы будем просто расставлять числа в массиве случайным образом до тех пор, пока не получим отсортированный массив. Звучит абсурдно? Да. Но это рабочий алгоритм! При условии, конечно, что случайная расстановка – истинно случайна.