Сортировка

Термины   23 Февраль 2012  Автор статьи:  

Сортировка — это упорядочение элементов по какому-либо признаку. Если элементы — числа, то их упорядочивают по возрастанию или убыванию. Контейнером для элементов, которые подлежат сортировки чаще всего выступают массивы или неупорядоченные коллекции. Приведем пример упорядочивание чисел по возрастанию:
Дано:
5 3 2 4 1
Стало:
1 2 3 4 5
Возникает вопрос как нужно действовать для того, чтобы получить упорядоченное множество чисел?
Существует много различных алгоритмов упорядочивание. Рассмотрим критерии по которым можно сравнить данные алгоритмы сортировки и выбрать наиболее подходящий для вас.

  1. Устойчивость
  2. Время работы
  3. Затрачиваемая память
  4. Наличие дополнительного оборудования

Виды сортировок:

  • Сортировка пузырьком
  • Сортировка вставками
  • Сортировка выбором
  • Сортировка подсчетом
  • Сортировка слиянием
  • Сортировка Шелла
  • Пирамидальная сортировка
  • Быстрая сортировка

Задача сортировки состоит: пусть задан массив записей a0, a1, .. an-1, требуется переупорядочить элементы массива так, чтобы они шли по неубыванию некоторого ключа. Говорят, что, сортировка осуществляется по некоторому ключу. Формально говоря на элементы массива вводится отношение «меньше либо равно» и в соответствии с ними происходит сортировка.
Выделим два вида сортировки:

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

Получим, что существует нижняя оценка числа сравнений произвольного алгоритма сортировки, основанного на сравнениях, причем это верно для менее общей задачи, когда все ключи различны по значению. Пусть задан попарно различный набор элементов. Эти элементы подаются на вход алгоритма в виде одной из n! перестановок, на выходе получается одна единственная.Можно считать, что для заданной перестановки алгоритм должен определить заранее заданную ранюю перестановку его элементов, чтобы после ее применения на входные данные они оказались отсортированными. Для этого надо из n! входных данных в конце концов алгоритм придет в свое уникальное состояние, отличающее этот вариант от всех остальных. Если изобразить работу алгоритма графически, то рисунок примет вид бинарного дерева, где каждый уровень дерева представляет какое-либо сравнение в исходной перестановке, которое уменьшает количество подходящих ей состояний(необязательно поровну). Общее количество состояний на любом уровне дерева всегда равна n!. В этом дереве принятия решений решение не нужно будет применять и ответ будет определен, когда количество перестановок, допустимых для нашей вершины равно 1. Таким образом, каждый лист этого дерева несет ровно одну перестановку, следовательно листов в дереве будет ровно n!. Если высота дерева равна h, то на i-ом уровне дерева не больше 2^{i-1} вершин. Всего же вершин не более 2^{h-1}. Таким образом, количество листьев в h-вершинном дереве (в дереве высотой h) не более 2^h. Но в каждом дереве n! листьев, поэтому h обязательно такая, что {2^h} \ge {n!} Прологарифмируем по основанию 2 обе части: {h}\ge{\log_2{n!}}
{n!}={1}\times{2}\times{3}\times{. . .}\times{n}\ge\frac{n}{2}\times(\frac{n}{2}+1)\times{. . .}\times{n}\ge{(\frac{n}{2})}\times{. . .}\times{(\frac{n}{2})}=(\frac{n}{2})^{\frac{n}{2}}
{h}\ge{\log_2{n!}}\ge{\log_2{(\frac{n}{2})^{\frac{n}{2}}}=\frac{n}{2}\log_2{\frac{n}{2}}
То есть асимптотическая высота дерева не имеет размер меньше, чем n\log_2{n}, то есть h=O(n\log_2{n}) — нижняя оценка на высоту дерева, то есть асимптотическая временная сложность любого алгоритма сортировки, основанного на сравнениях не может быть меньше O(n\log_2{n})

Еще сортировки делятся на:

  1. Стабильные
  2. Нестабильные

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

Научиться программировать

  • на Delphi

  • на Java

  • на C++