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

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

Как выбрать опорный элемент? Понятно, что в идеале нам нужно, чтобы опорный элемент являлся медианой исходного массива, чтобы примерно половина элементов оказались слева от него, а другая половина — справа. Для простоты в качестве опорного часто выбирают самый крайний элемент, что при плохом наборе (элементы массива отсортированы в обратном порядке) исходных данных может привести к кардинальному ухудшению времени сортировки до O(N^2).

Функция partition() возвращает индекс опорного элемента. Код написан на языке Java:

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

Теперь приведем реализацию основной функции quickSort():

В итоге сначала будет отсортирована левая часть массива, а затем правая.

Реализация алгоритма на языке С:

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *