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

быстрая сортировка, алгоритм быстрой сортировки,метод быстрой сортировки, быстрая сортировка на с++

 

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

Среднее время алгоритма быстрой сортировки NlogN, худший случай O(N^2), где N – длина массива. Чтобы избежать худшего случая нужно: перед использованием быстрой сортировки массива перемешать его.

 

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

Давайте рассмотрим работу алгоритма на примере. Пусть у нас есть массив с элементами: 4,9,7,6,2,3,8

быстрая сортировка пример, быстрая сортировка массива,метод быстрой сортировкиВыберем число относительно которого мы будем сравнивать – 6. Обычно выбирается число стоящее в середине. И определим два указателя b (begin) и e (end). Теперь мы двигаем наши указатели до тех пор пока не встретим число большее(если указатель b) или меньшее(указатель e) 6.

Так как числа на нужных местах, то мы продвигаем наши указатели вперед. Теперь мы наткнулись на числа 9 и 3. Мы должны поменять их местами так как 9>6, а 3<6.

Снова сдвигаем указатели на одну итерацию. Видим числа стоящие не на своем месте 7>6 и 2<6. Меняем их местами.

Вновь передвигаем указатели, они оказываются на 6.

Теперь делим массив на две части и в каждой части производим такую же сортировку.

 

 

 

 

 

 

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

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

Все первая часть отсортирована, займемся второй частью массива.

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

6 и 8 оставляем на своих местах, сдвигаем указатели. 7 и 9 тоже не трогаем. Теперь давайте поделим эту половинку еще на две. И отдельно сравним элементы в каждой из половинок: 9 и 8 меняем местами, 6 и 7 не изменяем.

Ну вот и все мы отсортировали массив методом быстрой сортировки.

Результат быстрой сортировки

быстрая сортировка пример, быстрая сортировка массива,метод быстрой сортировки

Быстрая сортировка на си++

 

Результат быстрой сортировки

быстрая сортировка на си, быстрая сортировка,быстрая сортировка массива, самая быстрая сортировка



Оставить комментарий

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