Понятия сортировки. Оценка алгоритмов сортировки. Классификация алгоритмов сортировки.

Основные понятия:

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

 

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

- Дан ряд элементов (A1, A2, …, An). Необходимо осуществить их перестановку в порядке (Ak1, Ak2, … Akn) так, чтобы элементы подчинялись функции упорядочивания F(Ak1) <= F(Ak2) <= … <= F(Akn), при этом вводят понятие "ключ сортировки".

- Ключом сортировки называют атрибут элемента, по значению которого осуществляется упорядочивание.

 

Любой алгоритм сортировки состоит из 3 частей:

1) сравнение, определяющее упорядоченность пары элементов;

2) перестановка, позволяющая менять местами пару элементов (A2 на место A1, A1 на место A2);

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

 

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

1) время сортировки – основной параметр, характеризующий быстродействие алгоритма.

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

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

Пример устойчивости:

1a 3q 1b 1c 2z: исходный массив (индекс, значение)

1a 1b 1c 2z 3q: устойчивая сортировка

1c 1b 1a 2z 3q: неустойчивая сортировка

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

 

Все выполняемые алгоритмы сортировки могут быть разделены на 2 основных класса:

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

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

 

Методы внутренней сортировки делятся на универсальные и специальные. Универсальные -> простые и улучшенные. Простые и улучшенные методы отличаются своей эффективностью. Специальные методы предназначены для сортировки информации определенной структуры.

 

Простые методы сортировки массивов.

К простым методам сортировки массивов относятся:

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

- сортировка выбором

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

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

 

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

Сортировка пузырьком – наиболее простейший для реализации и понимания алгоритм сортировки, но эффективен он лишь для небольших массивов. Сложность алгоритма – n^2.

 

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

 

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

 

Сортировка пузырьком не меняет взаимного расположения равных элементов и не использует дополнительной памяти.

 

Достоинства:

- Алгоритм является естественным и устойчивым.

Недостатки:

- Высокая вычислительная сложность алгоритма.

 

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

 

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

Может быть как устойчивым, так и неустойчивым.

 

Алгоритм:

- Находится минимальный (максимальный) элемент последовательности. Для этого первый элемент сравнивается со вторым, первый с третьим и т.д. Номер найденного элемента помечается.

- Если индекс первого элемента не тождественен этому элементу, то они обмениваются значениями.

- Сортировка продолжается на отсортированной части массива.

 

Число сравнений: N^2

 

Достоинства:

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

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

 

Недостатки:

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

- На больших объемах данных данная сортировка является неэффективной.

 

 

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

 

Данный алгоритм выстраивает результирующий массив по одному элементу за раз. Он намного менее эффективен на больших списках, чем улучшенные методы сортировки (qsort/hsort). Однако, у данного алгоритма есть следующие достоинства:

- Простая реализация

- Эффективен на небольших наборах данных

- Естественен

- Наилучший случай – O(n)

- Устойчивый

- Требует только O(1) дополнительной памяти

 

Недостатки – высокая вычислительная сложность O(n^2).

 

Алгоритм:

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

 

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

 

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

 

Наихудший случай – O(n log(n)).

 

Алгоритм:

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

 

Достоинства:

- Сортировка является устойчивой.

- Эффективна при обработке данных с большим временем доступа.

- Наилучший способ сортировки связанных списков.

- Алгоритм удобен для структур с последовательным доступом к элементам.

 

Недостатки:

- Требует дополнительное пространство (O(1)).

- Уступает по быстродействию быстрой сортировке.