Быстрая сортировка. 
Классика алгоритмизации

Общая идея алгоритма состоит в следующем:

Выбрать из массива элемент, называемый опорным.

Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».

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

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

Время работы алгоритма быстрой сортировки зависит от степени сбалансированности разбиения. Сбалансированность, в свою очередь, зависит от того, какой элемент выбран в качестве опорного.

Наихудшее поведение алгоритма быстрой сортировки имеет место в случае, когда подпрограмма, выполняющая разбиение, порождает подзадачу с n-1 элементами, а вторую — пустую, то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. Предположим, что такое несбалансированное разбиение возникает при каждом рекурсивном вызове. Для выполнения разбиения требуется время и (n). Поскольку рекурсивный вызов процедуры разбиения, на вход которой подается массив размером 0 приводит к немедленному возврату из этой процедуры, то.

T (0) = и (1).

Таким образом, общее время работы в худшем случае:

T (n)=T (n-1)+T (0)+и (n)=T (n-1)+и (n).

При суммировании промежутков времени, затрачиваемых на каждый уровень рекурсии, получается арифметическая прогрессия, что приводит к результату и (n²).

В наилучшем же случае при каждой операции разделения массив делится на две почти одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит log₂?n. В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения.

T (n)=2T (n/2)+и (n),.

что даёт общее время выполнения алгоритма.

T (n)=n*log₂?n.

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

Один из самых быстродействующих алгоритмов сортировки общего назначения.

Прост в реализации.

Не требует большого количества дополнительной памяти Недостатки:

Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека.

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

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

Имеет квадратичный порядок роста и (n²).