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

    Cортировка  выбором (англ. selection sort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n²), предполагая что сравнения делаются за постоянное время.

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

    Это простой алгоритм сортировки. Хотя этот метод сортировки намного менее  эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

             - прост в реализации;

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

             - эффективен на наборах данных, которые уже частично отсортированы;

          - это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

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

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

4.4 Сортировка Шелла

    Этот  метод был предложен автором Donald Lewis Shеll в 1959 г. Алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга.

    При сортировке Шелла сначала сравниваются и сортируются между собой  ключи, отстоящие один от другого  на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше).

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

    Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать либо средний по положению элемент (элемент с индексом [n/2], тогда алгоритм будет работать за время O(n log n) в худшем случае), либо элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
1. два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
2. вычисляется опорный элемент m;
3. индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;
4. индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
5. если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
6. если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

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

       Оценка эффективности

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

• Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C_N = 2C_N/2+N. Это дало бы наименьшее время сортировки.
• Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.

      На  практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C_N/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C_N = N lg N.

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

      Худший  случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

       Улучшения

• При выборе опорного элемента из данного диапазона  случайным образом худший случай становится очень маловероятным  и ожидаемое время выполнения алгоритма сортировки — O(n log n).
• Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит lg₂n, а в худшем случае она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.
• Использовать в качестве опорного элемента медиану-средний элемент массива. Т.к. медиана ищется за O(n), алгоритм всегда будет работать за O(n log n).

          Достоинства и недостатки

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

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

      Недостатки:

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

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

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

      Для решения задачи сортировки эти три  этапа выглядят так:

      1) Сортируемый массив разбивается  на две половины меньшего размера; 

           2) Каждая из получившихся  половин сортируется отдельно;

      3) Два упорядоченных массива половинного  размера соединяются в один.

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

     Нетривиальным этапом является соединение двух упорядоченных  массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.

Этот алгоритм был изобретён Джоном фон Нейманом в 1945 году.

4.7 Сортировка подсчётом

      Сортировка  подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

      Описание алгоритма

      Идея  сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

      Более понятное описание алгоритма (с  примерами): Есть массив А - исходный, есть массив В - выходной и С - массив счетчиков для каждого элемента исходного массива. В массиве А содержатся числа, не выходящие за пределы размерности самого массива. Т.е. алгоритм работает ТОЛЬКО для целых чисел (отрицательные тоже могут быть, при условии, что нумерация массива начинается именно с отрицательного индекса, >= минимальному отрицательному эл-ту массива!). Но работает приимущественно для положительных!