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

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

• Время( C(n) ) — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для типичного алгоритма хорошее поведение — это O(N*logN)и плохое поведение — это O(N^2). Идеальное поведение для упорядочения —O(N). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в N*logNсравнениях.
• Память( M(n) ) — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(logN)памяти.

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

• Устойчивость  — устойчивая сортировка не меняет взаимного расположения равных элементов.
• Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(N*logN), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

• Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
• В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
• Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

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

                  2. Объём данных не позволяет им разместиться в ОЗУ.

        Метод пузырька
        Метод пузырька с флажком
        Метод выбора
        Сортировка простыми вставками
        Метод простых вставок с барьером
        Бинарными вставками  
        Сортировка Шелла
        Quick Sort
        Блочная, карманная