Сортировка компьютеров по способами

Алгоритмы сортировки

Статья в процессе обновления

Необходимость изучения существующих компьютерных алгоритмов связана с использованием ограниченных вычислительных ресурсов компьютера: память, процессов, скорость чтения данных с диска и запись на диск и др. Эффективность алгоритма напрямую связана с тем, сколько ресурсов компьютеру придётся затратить для решения поставленной задачи. Например, для решения задачи сортировки вставками требуется примерно операций (здесь — количество элементов данных, а — независящая от этих данных константа). Для сортировки слиянием требуется уже порядком операций (здесь — краткая запись , а — некоторая другая константа). Скорость работы второго алгоритма выше, а наглядный пример приводит Кормэн в книге «Алгоритмы. Построение и анализ» (стр.: 34):

…рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нём работает алгоритм сортировкой вставкой, а компьютер Б более медленный, и на нём работает алгоритм методом слияния. Оба компьютеры должны выполнить сортировку множества, состоящего из десяти миллионов чисел. (…) Предположим, что компьютер А выполняет десять миллиардов команд в секунду, а компьютер Б — только 9 миллионов команд в секунду, так что компьютер А в тысячу раз быстрее компьютера Б. Чтобы различие стало ещё большим, предположим, что код для метода вставок (т.е. для компьютера А) написан лучшим в мире программистом на машинном языке и для сортировке чисел надо выполнить команд. Сортировка же методом слияния (на компьютере Б) выполнена программистом-середнячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения команд. Для сортировки десяти миллионов чисел компьютера А понадобиться: секунд (более 5,5 часов), в то время как компьютеру Б потребуется секунд (менее 20 минут).

Как видите, использование кода, время работы которого возрастает медленнее, даже при плохом компиляторе на более медленном компьютере требует более чем 17 раз меньше процессорного времени!

Определение

Алгоритмы сортировки — это алгоритмы, которые берут некоторую последовательность из элементов и переставляют элементы таким образом, чтобы получившаяся последовательность удовлетворяла условию: .

Визуализация алгоритмов сортировки

Классификация алгоритмов

Алгоритмы сортировки можно классифицировать по:

• принципу сортировки
  • сортировки, использующие сравнения: быстрая сортировка, пирамидальная сортировка, сортировка вставками и др.
  • сортировки, не использующие сравнения: блочная сортировка, поразрядная сортировка, сортировка подсчётом и др.
  • прочие, например, обезьянья сортировка
• устойчивости; сортировка является устойчивой в том случае, если для любой пары элементов с одинаковым ключами, она не меняет их порядок в отсортированном списке
• вычислительной сложности
• использованию дополнительной памяти; сортировки, которые не используют дополнительную память в ходе работы, называют in-place
• рекурсивности
• параллельности
• адаптивности; сортировка является адаптивной в том случае, когда она выигрывает от того, что входные данные могут быть частично или полностью отсортированы (напр., сортировка вставками)
• использованию внутренней или внешней памяти компьютера

Простые сортировки

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

Самая простая сортировка, которая для каждой позиции в последовательности ищет минимальный элемент, после чего меняет элементы с индексами текущей позиции и найденного элемента:

Пузырьковая сортировка

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

Сортировка вставками

Алгоритм такой: изначально отсортированная последовательность пуста; на каждом шаге из набора входных данных выбирается элемент и помещается на нужное место в уже отсортированной последовательности; шаги продолжаются до тех пор, пока набор входных данных не закончится.

Вот алгоритм на псевдокоде:

Утверждение, что в начале каждой итерации цикла оператора for, подмассив A[0..j − 1] , которые раньше находились в этом подмассиве, состоит из тех же элементов, но теперь в отсортированном порядке, называется инвариантом цикла. Инварианты позволяют понять, корректно ли работает алгоритм, и обладают 3-мя свойствами:

1. Инициализация. Справедливы перед первой итерации цикла.
2. Сохранение. Если они истины перед очередной итерации цикла, то остаются истинными и после неё.
3. Завершение. Позволяют убедится в правильности алгоритма по завершению цикла.

Разберём это определение инвариантов на примере приведённого выше алгоритма:

1. Инициализация. Перед первой итерации, когда , подмассив A[0..j − 1] состоит из единственного элемента A[0], что является тривиальным случаем, и, очевидно, такой подмассив отсортирован.
2. Сохранение. На каждом последующем этапе осуществляется сдвиг элементов A[j], A[j − 1] и т.д. на одну позицию вправо, освобождая место для A[j] элемента до тех пор, пока не найдётся подходящее место для него. После завершения итерации подмассив A[0..j] состоит из тех же элементов в отсортированном порядке.
3. Завершение. Цикл завершается в том случае, когда j ≥ n, где n — количество элементов в исходном массиве. Поскольку подмассив A[0..j], который по существу является теперь подмассивом A[0..n] отсортирован, а подмассив A[0..n] и есть исходный массив A, то приведённый алгоритм работает правильно.

Важная особенность работы этого алгоритма заключается в том, что при уже отсортированных исходных данных цикл while не будет выполняться вовсе, т.к. проверка условия A[i] > value будет срабатывать сразу. Это позволяет алгоритму выполнить не команд, а только , чем пользуются другие, более сложные алгоритмы.

Эффективные сортировки

Сортировка методом слияния

Многие алгоритмы имеют рекурсивную структуру: для решения поставленной задачи они вызывают сами себя несколько раз, решая вспомогательные подзадачи. Обычно, разбиение происходит на подзадачи, сходные с исходной, но имеющим меньший объём. Далее они рекурсивно решаются, после чего полученные решения комбинируются для получения решения исходной задачи. Такой подход к решению задачи называется методом «разделяй и властвуй». Этот метод включает в себя 3 пункта:

1. Разделение задачи на несколько подзадач, которые представляют собой меньшие экземпляры той же задачи.
2. Властвование над подзадачами путём их рекурсивного решения. Если размер задач становится достаточно мал, то они может быть решена непосредственно.
3. Комбинирование решений подзадач в решение исходной задачи.

Типичный пример этого метода — сортировка методом слияния, суть которой заключается в следующем:

1. Разделение-элементной сортируемой последовательности на две подпоследовательности по элементов.
2. Рекурсивная сортировка подпоследовательности с использованием сортировки методом слияния.
3. Соединение 2-х отсортированных подпоследовательности для получение окончательного отсортированного ответа.

Рекурсия останавливается тогда, когда длина сортируемой подпоследовательности становится равной 1, поскольку любая такая последовательность уже является отсортированной (тривиальный случай). Главной операцией является объединение двух осторированных последовательностей в ходе комбинирования. Её суть заключается в том, что из двух отсортированных последовательностей выбираются элементы в порядке их возрастания. Поскольку каждая из последовательностей уже отсортирована, то выбор осуществляется между 2-я значениями из разных подпоследовательностей, после чего наименьшее значение перемещается из своей подпоследовательности в комбинируемую.

Алгоритм на псевдокоде:

Быстрая сортировка

Основной алгоритм работы

1. Выбрать опорный элемент (pivot).
2. Разделение: изменить порядок элементов последовательностей таким образом, чтобы все элементы большие или равные, чем опорный элемент, находились после опорного элемента. После разделения опорный элемент будет находится на своём месте.
3. Рекурсивно повторить предыдущие два шага обеих образовавшихся подпоследовательностей («слева» и «справа» от выбранного опорного элемента).

Недостатки алгоритма

Предложенный ниже алгоритм использует разбиение Ломуто, где опорным элементом для каждой последовательности, будет выступать последний её элемент. На отсортированной последовательности алгоритм деградирует до .

Пирамидальная сортировка

Идея пирамидальной сортировки заключается в использовании такой структуры данных, как бинарная куча, являющаяся бинарным деревом со следующими ограничениями:

1. Значение в любом узле не меньше, чем в любом из его потомков
2. Бинарное дерево является полным

Для представления дерева через массив можно использовать следующую идею: на первой позиции находится корень бинарного дерева, тогда для каждого потомка будет верно, что его индекс определяется как для левого потомка и для правого потомка:

Алгоритм сводится к следующим шагам:

1. Элементы входной последовательности необходимо переставить таким образом, чтобы они удовлетворяли условиям для бинарной кучи
2. Обменять первый элемент с последним, убрать из рассмотрения данных элемент и выполнить операцию по восстановлению бинарной кучи, т.к. после обмена полученное дерево может не соответствовать ограничению 1

Функция, которая перемещает элемент вниз по дереву для восстановления свойств дерева будем называть Heapify:

Нашли ошибку в тексте? Выделите ошибку в тексте и нажмите Ctrl + Enter на любой странице сайта.

Источник

Основные виды сортировок и примеры их реализации

Памятка для тех, кто готовится к собеседованию на позицию разработчика

На собеседованиях будущим стажёрам-разработчикам дают задания на знание структур данных и алгоритмов — в том числе сортировок. Академия Яндекса и соавтор специализации «Искусство разработки на современном C++» Илья Шишков составили список для подготовки с методами сортировки, примерами их реализации и гифками, чтобы лучше понять, как они работают.

Пузырьковая сортировка и её улучшения

Сортировка пузырьком

Сортировка пузырьком — один из самых известных алгоритмов сортировки. Здесь нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.

Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

Сортировка перемешиванием (шейкерная сортировка)

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

Сортировка расчёской

Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.

Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.

Простые сортировки

Сортировка вставками

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

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

Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.

Быстрая сортировка

Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.

Быструю сортировку изобрели в 1960 году для машинного перевода: тогда словари хранились на магнитных лентах, а сортировка слов обрабатываемого текста позволяла получить переводы за один прогон ленты, без перемотки назад.

Сортировка слиянием

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

Пирамидальная сортировка

При этой сортировке сначала строится пирамида из элементов исходного массива. Пирамида (или двоичная куча) — это способ представления элементов, при котором от каждого узла может отходить не больше двух ответвлений. А значение в родительском узле должно быть больше значений в его двух дочерних узлах.

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

Источник