Перейти к содержанию

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

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

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

Не будем лить воду и давайте сразу перейдем к массиву данных на котором мы будем разбирать алгоритм:

4 6 9 7 8 3 1 5 2

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

Так вот, у нас есть массив и нам нужно его отсортировать. На первом шаге нам нужно выбрать какой-то из элементов массива опорным. Какой ? В первых версиях алгоритма в качестве опорного выбирался самый первый элемент массива. Но если наш массив уже отсортирован, то вы как раз и получите наихудший по времени вариант работы алгоритма быстрой сортировки. Более оптимальным вариантом считается выбор элемента из середины последовательности или вообще рандомный элемент. Идеальным вариантом является выбор медианного элемента, однако такой подход на практике не используется потому что это слишком трудоемкая задача которая съест всю выгоду от применения быстрой сортировки.

Мы знаем что наш массив не отсортирован, поэтому давайте пойдем по классическому варианту и выберем опорным элементом первый — цифру 4.

Теперь мы берем поочередно все элементы массива и сравниваем их с нашим опорным (четверкой), если элемент меньше, он уходит влево, если больше, уходит вправо.

Первый элемент(после того, который взят опорным) 6, он больше опорного элемента 4, кидаем его вправо. 9 больше и тоже вправо. 7 больше, вправо, 8 вправо, 3 и 1 меньше и уходят влево, 5 вправо, 2 влево. Получаем такую картину:

3 1 2 4 6 9 7 8 5

Элемент (цифра) 4 в нашей последовательности встала на свое конечное место. Теперь мы имеем 2 последовательности справа и слева от опорного элемента. Далее необходимо взять каждую из частей и проделать точно такие же манипуляции. В программном коде на этом моменте функция будет рекурсивно вызывать саму себя. Но с кодом мы разберемся чуть позже, смотрим дальше. Наши последовательности:

3 1 2 и 6 9 7 8 5

Теперь в каждой из них снова выбираем свой опорный элемент. Как вы помните, в качестве опорного мы берем тот что стоит первым:

3 1 2 и 6 9 7 8 5

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

1 2 3

В последовательности 6 9 7 8 5 после сравнения с опорным получаем:

9 7 8 6 5

Мы только что закончили «вторую разбивку» нашей последовательности, надеюсь вы ещё не запутались, ниже я прикреплю всё единой схемой чтобы никто ничего не упустил. Давайте посмотрим что мы имеем сейчас. Опорные элементы с прошлой итерации опять же отсортировались далее в процессе не участвуют, сейчас мы имеем 4 подмассива данных:

1 2 и пустой и 9 7 8 и 5

Самое время сказать несколько слов про рекурсию. Её основная сложность или если хотите проблема, это не уйти в вечный цикл. Как было сказано выше, алгоритм быстрой сортировки основан на рекурсии, каждая разбивка это подмассива на более мелкие подмассивы это рекурсивный вызов функции. Но в какой-то момент нам нужно остановиться и завершить её. Так вот любая рекурсивная функция состоит из двух частей, первая часть называется базовым случаем, это условие когда нужно остановиться. В алгоритме быстрой сортировки базовый случай это когда подмассив состоит из 1 элемента или вообще их не имеет. Такие массивы не имеет смысла дальше сортировать и нужно просто возвращать данные. Вторая часть рекурсивной функции описывает рекурсивный случай, когда функция снова должна вызывать саму себя пока не доберется до базового случая. Давайте посмотрим на примере наших 4 подмассивов:

1 2 — выбираем опорным первый элемент и продолжаем сортировать, это рекурсивный случай

пустой (справа от тройки ничего не было)а тут нам попросту нечего сортировать, это базовый случай, закончили

9 7 8 — выбираем опорным первый элемент и продолжаем сортировать, это рекурсивный случай

5 — один элемент сортировать не имеет смысла, это базовый случай, закончили

На очередной итерации рекурсивной функции, в которую попадают подмассивы не достигшие базового случая, мы получаем снова 4 подмассива:

пустой (слева от единицы ничего не было) — базовый случай, закончили

2 — базовый случай, закончили

пустой (слева от десятки ничего не было) — базовый случай, закончили

7 8 — более одного элемента, это рекурсивный случай, выбираем первый элемент опорным и продолжаем

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

пусто (слева от семерки ничего не было)

8

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

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

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

Каждый раз мы рекурсивно делили массив на 2 части относительно опорного элемента. Затем достигнув базового случая в каждом из подмассивов завершаем рекурсивный вызов.

Сложность алгоритма

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

Практическое применение:

Алгоритм быстрой сортировки имеет очень широкое применение и встроен в качестве функции/метода в большинство языков программирования.

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

Ваш адрес email не будет опубликован.