по информатике |
Смысл сортировки состоит в том, чтобы упорядочить все элементы последовательности по возрастанию или убыванию.
Есть несколько алгоритмов, и каждый из них имеет свою особенность и временную сложность. Мы перечислим наиболее часто встречающиеся.
1. Сортировка "пузырьком". Алгоритм сортировки по возрастанию (убыванию): Если в последовательности встречаются два подряд идущих элемента такие, что последующий меньше (больше) предыдущего, то мы меняем их местами. Эту операцию мы проводим пока возможно. Тогда каждый последующий больше (меньше) предыдущего, а значит последовательность отсортирована по возрастанию (убыванию). Временная сложность алгоритма O(N2). Особенности: нет.
2. Cортировка вставкой. Алгоритм сортировки по возрастанию (убыванию): Находим в массиве минимальный (максимальный) элемент и меняем его с первым. Далее среди оставшихся опять находим минимальный (максимальный) элемент и меняем уже со вторым. И так далее пока не останется один элемент. Временная сложность алгоритма O(N2). Особенности: нет.
3. Сортировка по ключу (карманная сортировка). Алгоритм сортировки по возрастанию (убыванию): Бежим по последовательности и считаем количество каждых элементов (например: если последовательность состоит только из цифр от 0 до 3, то надо подсчитать количество нулей, единиц, двоек и троек). А потом выводим сначала все меньшие (большие) из них потом все поменьше (побольше) и так далее. (Выводим все нули, ведь мы знаем их количество, потом все единицы, двойки и тройки). Временная сложность алгоритма O(N). Особенности: Мы должны знать диапазон, в котором могут быть элементы, если он слишком велик, то мы не сможем подсчитать количество различных элементов.