Блог для любопытных и не только
Сортировка

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

  • Название: quicksort;
  • Применение: Сортировка неупорядоченных данных;
  • Время выполнения: O(n lg n);
  • Сложность: Средний;
  • Входные параметры: Неупорядоченные данные;
  • Результат: Отсортированные данные в порядке возрастания или убывания

Пример из жизни: Представьте большой отель! Каждый день сотни посетителей, каждому посетителю присваивается уникальный номер, например, 23 или 356. Наступает момент, когда необходимо найти конкретного посетителя под номером 44. Порядок действия очевиден — можно воспользоваться бинарным поиском, но данный алгоритм работает только с отсортированными данными, поэтому прийдется искать банальным перебором.

Более интересный пример с базой данных, в которой хранятся пользовательские данные для авторизации. Как только пользователь вводит логин и пароль необходимо быстро его найти и предоставить доступ к ресурсу. Но для того, чтобы быстро найти пользователя, необходимо отсортированные данные т.к. в противном случае придется действовать простым перебором (в худшем случе на это может уйти — O(n) времени, а это очень и очень долго).

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

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

В алгоритмах этот принцип называется — «разделяй и властвуй»! Действительно, давайте воплотим нашу идею на практике, а именно постараемся отсортировать для начала неупорядоченные 6 чисел (-2, 0, 2, 7, 11, 3). Поделим нашу задачу на части, возьмем за середину число 7. И перенесем все числа меньше семи в левую часть, остальные оставим в правой части (-2, 0, 2, 3, 7, 11 ). Осталось произвести ту же самую операцию над левой частью (все что стоит слева от числа 7) и правой (все что стоит справа от числа 7). В левой части (-2, 0, 2, 3 ) за середину принимаем 2 и все что меньше двух отправляем в левую часть, а все что больше в правую. Т.к. числа получились отсортированными, присоединяем их  в левую часть — (-2, 0, 2, 3, 7). Производим ту же операцию с правой частью и получаем отсортированный массив — (-2, 0, 2, 3, 7, 11). Согласитесь гораздо лучше простого перебора? А главное быстрей!

Постановка задачи: Требуется отсортировать массив неупорядоченнх данных.

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

Шаг 1.  Выбираем опорный элемент

Шаг 2. Производим сравнение всех элементов с опорным элементом

Шаг 3. Все что меньше опорного элемента смещаем в левую, что больше в правую части.

Шаг 4.  Выполняем все шаги (1,2,3) до тех пор пока не получим отдельный элемент

Шаг 5. Производим слияние полученных результатов в отсортированные данные

Блок-схема:

 

Реализация:

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

После определения левой и правой частей необходимо подобрать новые опорные элементы. В нашем случае это -2 и 7.

Проводим повоторные шаги с левой, а потом правой частями. Начнем с левой. Итак, перемещаем элементы меньше опорного в левую часть — таких нет значит путой элемент. В правую часть перемещаем 0 т.к. меньше -2. Т.к. в левой и правой частях остались по одному элементу подмассив считается отсортированным.

Проводим повоторные шаги с правой частью массива. Опорный элемент — 7. Все что меньше перемещаем влево, что больше вправо. Соотвественно в левой и правой частях осталось по одному элементу этот подмассив тоже можно считать отсортированным.

Склеиваем отсортированные подмассивы и получаем отсортированный массив.

Программная разработка:

Бывает очень трудно перевести язык алгоритма, который на словах кажется очевидным в программный код. Но мы постараемся это сделать. Обратите внимание! данная программная реализация является по большей части  учебной и не нужно использовать ее в реальных проетах или серьезных задачах. Итак, приступим.

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

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

Как было показано выше, в начале алгортма (шаг 1) требуется определить опорный элемент (определим самый простой случай и возьмем за опорный элемент первый или текущий элемент в массиве).

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

Далее, заполняем массивы соотвественно элементами находящимися слева и справа от опорного.

Наконец, возвращаем результат, применяя рекурсивный вызов к правой части подмассива и левой соотвественно

Наконец, возвращаем результат, применяя рекурсивный вызов к правой части подмассива и левой соотвественно. Приведем полный вариант функции:

Время выполнения

 

Что еще почитать:

http://informatics.mccme.ru/moodle/course/view.php?id=9

Отличное видео на закрепление материала:

https://www.youtube.com/watch?v=oS5bZdtEhHY

Поделиться

Отправить ответ

avatar
wpDiscuz