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


Содержание

Алгоритм быстрой сортировки (Quick sort) в Java

Алгоритм быстрой сортировки — это один из самых быстрых существующих алгоритмов сортировки (на момент написания данной статьи), который является примером стратегии «разделяй и властвуй». Большинство готовых библиотек и методов по сортировке используют quick sort алгоритм как основу.

Перед тем, как мы перейдем к написанию кода сначала разберемся как именно работает данный алгоритм. К стати говоря, алгоритм быстрой сортировки как и алгоритм сортировки пузырьком в худшем случае работает за время O( ) что довольно медленно. Но не торопитесь делать поспешные выводы. В среднем алгоритм быстрой сортировки выполняется за время O(n logn); причем время сортировки очень зависит от выбора опорного элемента, о котором Вы узнаете далее.

Алгоритм быстрой сортировки — это рекурсивный алгоритм. Как уже было сказано выше quick sort использует стратегию «разделяй и властвуй». Ее суть заключается в том, что задача разбивается на подзадачи до тех пор, пока не будет элементарной единицы. Так и с алгоритмом: массив делится на несколько массивов, каждый из который сортируется по отдельности и потом объединяется в один массив.

Пошаговое описание работы алгоритма быстрой сортировки

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

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

Подробный анализ алгоритма быстрой сортировки

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

Разбиваем массив на подмассивы: те, что больше 3 и те, что меньше 3

Проделаем то же самое с левый подмассивом

Выбор опорного элемента

Разбиение на подмассивы

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

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

Эти картинки я взял вот отсюда: http://me.dt.in.th/page/Quicksort/. Там Вы найдете завершение для этого массива. Главное, что суть понятна.

Теперь осталось реализовать код. Так, как у нас сайт про Java программирование, то и реализация будет на java. В Интернете очень много реализаций для других языков программирования.

Быстрая сортировка — один из лучших методов сортировки массивов

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

Понятие быстрой сортировки

Быстрая сортировка — Quick Sort или qsort. По названию становится понятно, что это и для чего. Но если не понятно, то это алгоритм по быстрой сортировке массива, алгоритм имеет эффективность O(n log n) в среднем. Что это значит? Это значит, что среднее время работы алгоритма повышается по той же траектории, что и график данной функции. В некоторых популярных языках имеются встроенные библиотеки с этим алгоритмом, а это уже говорит о том, что он крайне эффективен. Это такие языки, как Java, C++, C#.

Алгоритм

Метод быстрой сортировки использует рекурсию и стратегию «Разделяй и властвуй».

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

2. Слева от опоры ищется элемент больший, чем опорный, справа — меньший, чем опорный, затем меняем их местами. Делаем это, пока максимальный справа не будет меньше, чем минимальный слева. Таким образом, все маленькие элементы кидаем в начало, большие — в конец.

3. Рекурсивно применяем данный алгоритм к левой и правой части нашего алгоритма отдельно, затем ещё и ещё, до достижения одного элемента или определённого количества элементов. Что же это за количество элементов? Есть ещё один способ оптимизировать данный алгоритм. Когда сортируемая часть становится примерно равной 8 или 16, то можно обработать её обычной сортировкой, например пузырьковой. Так мы повысим эффективность нашего алгоритма, т.к. маленькие массивы он обрабатывает не так быстро, как хотелось бы.

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

Эффективность быстрой сортировки

Является ли быстрая сортировка самым быстрым алгоритмом сортировки? Однозначно нет. Сейчас появляется всё больше и больше сортировок, на данный момент самая быстрая сортировка — это Timsort, она работает крайне быстро для массивов, изначально отсортированных по-разному. Но не стоит забывать, что метод быстрой сортировки является одним из самых простых в написании, это очень важно, ведь, как правило, для рядового проекта нужно именно простое написание, а не громадный алгоритм, который сам ты и не напишешь. Timsort — тоже не самый сложный алгоритм, но звание самого простого ему точно не светит.

Реализация алгоритма

Ну вот мы и дошли до самого «вкусного». Теперь разберём, как реализовывается данный алгоритм. Как говорилось ранее, он не слишком сложен в реализации, скорее, даже прост. Но мы всё равно полностью разберём каждое действие нашего кода, чтобы вы поняли, как работает быстрая сортировка.

Наш метод называется quickSort. В нём запускается основной алгоритм, в который мы передаём массив, первый и последний его элементы. Запоминаем в переменные i и k первый и последний элемент сортируемого отрезка, чтобы не изменять эти переменные, так как они нам нужны. Затем проверяем расстояние между первым и последним проверяемым: оно больше или равно единице? Если нет, значит, мы пришли к центру и нужно выйти из сортировки этого отрезка, а если да, то продолжаем сортировку.

Затем за опорный элемент берём первый элемент в сортируемом отрезке. Следующий цикл делаем до того момента, пока не дойдём до центра. В нём делаем ещё два цикла: первый — для левой части, а второй — для правой. Их мы выполняем, пока есть элементы, подходящие под условие, или пока не дойдём до опорного элемента. Затем, если минимальный элемент всё же справа, а максимальный — слева, меняем их местами. Когда цикл заканчивается, меняем первый элемент и опорный, если опорный меньше. Затем мы рекурсивно делаем наш алгоритм для правого и левого участка массива и так продолжаем, пока не дойдём до отрезка длиной в 1 элемент. Тогда все наши рекурсивные алгоритмы будут return, и мы полностью выйдем из сортировки. Также внизу имеется метод swap — вполне стандартный метод при сортировке массива заменами. Чтобы несколько раз не писать замену элементов, пишем один раз и меняем элементы в данном массиве.

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

Алгоритмы и структуры данных для начинающих: сортировка

В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого — сортировки пузырьком — и закончим «быстрой сортировкой» (quicksort).

Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае.

Метод Swap

Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу.

Пузырьковая сортировка

Сложность Наилучший случай В среднем Наихудший случай
Время O(n) O(n 2 ) O(n 2 )
Память O(1) O(1) O(1)


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

Например, у нас есть массив целых чисел:

При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:

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

Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6.

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

Илон Маск рекомендует:  mysql_insert_id - Возвращает ID, сгенерированный при последнем INSERT-запросе.

«Росбанк», Москва, до 60 000 ₽ (до налогов)

При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу.

Сортировка вставками

Сложность Наилучший случай В среднем Наихудший случай
Время O(n) O(n 2 ) O(n 2 )
Память O(1) O(1) O(1)

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.

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

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.

Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

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

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

На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.

Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.

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

Сортировка выбором

Сложность Наилучший случай В среднем Наихудший случай
Время O(n) O(n 2 ) O(n 2 )
Память O(1) O(1) O(1)

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

Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.

При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.

Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение — 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход — на этот раз по индексам от 1 до n – 1.

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

Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.

После еще двух проходов алгоритм завершает свою работу:

Сортировка слиянием

Сложность Наилучший случай В среднем Наихудший случай
Время O(n·log n) O(n·log n) O(n·log n)
Память O(n) O(n) O(n)

Разделяй и властвуй

До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer).

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

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

Насколько эффективны эти алгоритмы?

Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

Сортировка слиянием

При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.

Давайте посмотрим на такой массив:

Разделим его пополам:


И будем делить каждую часть пополам, пока не останутся части с одним элементом:

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

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

  1. Операцию для рекурсивного разделения массива на группы (метод Sort ).
  2. Слияние в правильном порядке (метод Merge ).

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

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

Сложность Наилучший случай В среднем Наихудший случай
Время O(n·log n) O(n·log n) O(n 2 )
Память O(1) O(1) O(1)

Быстрая сортировка — это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:

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

Давайте посмотрим на работу алгоритма на следующем массиве:

Сначала мы случайным образом выбираем ключевой элемент:

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

Перемещение значений осуществляется методом partition .

На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.

Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное — помнить, что нам важно именно ключевое значение, а не его индекс.

Снова применяем быструю сортировку:

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

Заключение

На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#.

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

Быстрая сортировка (quick sort), или сортировка Хоара – один из самых быстрых алгоритмов сортирования данных.

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

Принцип работы алгоритма быстрой сортировки

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

  • Необходимо выбрать опорный элемент массива, им может быть любой элемент, от этого не зависит правильность работы алгоритма;
  • Разделить массив на три части, в первую должны войти элементы меньше опорного, во вторую — равные опорному и в третью — все элементы больше опорного;
  • Рекурсивно выполняются предыдущие шаги, для подмассивов с меньшими и большими значениями, до тех пор, пока в них содержится больше одного элемента.

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

Реализация быстрой сортировки

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

Илон Маск рекомендует:  Что такое код putc

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

Быстрая сортировка использует технику “разделяй и властвуй”, чтобы получить те же преимущества, что и сортировка слиянием, но при этом не использовать дополнительное место. Однако, ценой за это станет то, что список может не поделиться пополам, приводя к уменьшению производительности.

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

Рисунок 12 показывает, как 54 выступает в роли первого опорного значения. Поскольку мы уже рассматривали этот пример несколько раз, то знаем, что 54 в итоге окажется на позиции, занятой сейчас 31. Далее происходит процесс разделения. Он находит точку разделения и одновременно перемещает элементы по соответствующим сторонам списка, в зависимости от того, больше они или меньше опорной величины.

Рисунок 12: Первая опорная величина для быстрой сортировки

Разбиение начинается с определения двух маркеров положения — назовём их leftmark и rightmark — в начале и в конце оставшихся элементов списка (позиции 1 и 8 на рисунке 13). В процессе разбиения элементы, лежащие по неправильным сторонам от опорного, должны перемещаться пока маркеры не сойдутся в точке разделения. Рисунок 13 показывает этот процесс для опорного значения 54.

Рисунок 13: Поиск точки разделения для 54

Мы начинаем с увеличения на единицу leftmark , пока не находим значение, большее опорного. Тогда мы уменьшаем на единицу rightmark , пока не находим значение, меньшее опорного. В этот момент мы имеем два элемента, находящихся не на своих местах относительно итоговой точки разбиения. В нашем примере таковыми являются 93 и 20. Теперь можно поменять их местами и повторить процесс заново.

Когда rightmark становится меньше leftmark , мы останавливаемся. Позиция rightmark в данный момент — точка разбиения. Опорное значение следует поменять местами с её содержимым, и тогда оно будет стоять на своём месте (рисунок 14). В дополнение, все элементы слева от точки разбиения теперь меньше опорного значения, а справа — больше. Список поделен на две части, и быстрая сортировка может быть рекурсивно применена к каждой из них.

Рисунок 14: Завершение процесса с целью поиска точки разбиения для 54


Функция quickSort , показанная в CodeLens 7, вызывает другую рекурсивную функцию — quickSortHelper . Она начинает работать с базового случая, аналогичного сортировке слиянием. Если длина списка меньше или равна единице, то он уже отсортирован. Если больше, то он может быть разделен и рекурсивно отсортирован. Функция partition воплощает описанный ранее процесс.

Быстрая сортировка (lst_quick)

Для большей детализации, CodeLens 7 помогут вам пошагово пройти весь алгоритм.

Трассировка быстрой сортировки (quicktrace)

Для анализа функции quickSort стоит отметить, что для списка длиной \(n\) (если деление приходится на его середину) мы вновь получим \(\log n\) разделений. Чтобы найти точку разбиения, каждый из \(n\) элементов нуждается в сравнении с опорным значением. Результатом станет \(n\log n\) . При этом не требуется дополнительной памяти, как в сортировке слиянием.

К сожалению, в наихудшем случае точка разбиения может быть не посередине, а скакать слева направо, делая разделение очень неравномерным. В этом случае сортировка списка из \(n\) элементов разделится на сортировку списков размером 0 и \(n-1\) элементов. Далее сортировка списка длиной \(n-1\) опять даст подсписки из 0 и \(n-2\) элементов, и так далее. Результат: \(O(n^<2>)\) со всеми накладными расходами, требуемыми для рекурсии.

Ранее мы упоминали, что есть несколько способов выбора опорного значения. В частности, мы можем попытаться сгладить потенциальный дисбаланс в разбиении с помощью метода, называемого медианой трёх. Чтобы выбрать опорное значение, мы рассматриваем первый, средний и последний элементы списка. В нашем примере это будут 54, 77 и 20. Теперь определим из них медиану — 54 в данном случае — и возьмём её в качестве опоры (естественно, это было опорное значение, которое мы использовали первоначально). Идея в том, что когда первый элемент списка не принадлежит его середине, медиана трёх станет лучшим “срединным” значением. Особенно это полезно, если первоначальный список уже подвергался частичной сортировке. Мы оставляем реализацию такого выбора опорного значения в качестве упражнения для вас.

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

среда, 2 ноября 2011 г.

Быстрая сортировка(quicksort, сортировка Хоара)

Математический подход

Не строгая оценка

Строгая оценка

Улучшаем алгоритм

  1. алгоритм выбора значения наиболее приближенного к медиане
  2. вероятностный выбор оси

Инженерный подход

Рассмотрим простенький вариантик с использованием встроенной в Питон возможностью условной генерации списков вместо использования функции partition.

И его однострочная версия

На данных примерах показывается лаконичность и изящность языка, надеюсь вы оценили :)

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

Стоит сказать пару слов про использование методов оптимизации и их применимости на практике.


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

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

( indexLow,indexHigh)=partition(left,right,A[RandomSource.randrange(left, right)])
где RandomSource создаётся перед quicksort_interval(0, len(A)) так
RandomSource = random.Random(6666) # Инициализируем генератор случайных чисел.

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

Производительность

Тестирование проводилось на списке из 50000 не повторяющихся элементов.

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

Один из самых быстрых известных универсальных алгоритмов сортировки. В среднем O(n log(n)) обменов при упорядочивании n элементов.

Общее описание алгоритма:

  1. Выбирается элемент каким-либо образом. Существуют разные способы выбора элемента, но алгоритм работает с любым выбранным элементом. Это может быть самый первый, либо самый последний элемент массива, либо элемент где-то посередине. Этот элемент называется опорным.
  2. Элементы в массиве перемещаются так, что элементы меньше опорного оказываются слева от него, а элементы больше опорного — справа.
  3. К подмассивам слева и справа от опорного применяются первые два шага, если в этих подмассивах больше одного элемента.

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

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

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

А лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n 2 , хотя такая ситуация довольно редкая. Быстрая сортировка обычно быстрее других «скоростных» сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая. Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.

Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки. При этом известно, что для каждого болта из ведра есть соответствующая ему по размеру гайка, и для каждой гайки есть соответствующий по размеру болт. Одна беда — у вас отключили свет и вы не можете сравнить болт с болтом и гайку с гайкой. Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача — найти для каждой гайки соответствующий ей болт.

Пусть у нас n пар болт-гайка. Самое простое решение — «в лоб» — берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку, находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + . + 1 = n 2 /2 шагов. Существует ли более простое решение?

Самое быстрое (из известных мне) решение не самое очевидное. Применим подход «разделяй и властвуй». Если множество, которое мы хотим обработать слишком большое, то разобьём его на более мелкие и применим рекурсивно наш алгоритм к каждому из них. В конце концов, когда данных будет немного, обработаем и обратно соберём их вместе.

Возьмём любой (случайный) болт и с его помощью разобьём все гайки на те, которые меньше, и те которые больше, чем нужно для этого болта. Конечно, во время разбиения мы найдём и соответствующую ему гайку. Таким образом мы получим две кучи гаек — те, которые больше и те, которые меньше. С помощью найденной гайки разобьём все болты на те, которые меньше, и те, которые больше, чем первоначальный болт. Получим две кучи болтов, мелкие и крупные.

Илон Маск рекомендует:  Создание динамических форм с помощью javascript

Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой «подкуче». Таким образом, предстоит сделать порядка n·log(n) шагов.


Алгоритм быстрой сортировки напоминает решение нашей задачи. Сначала мы находим опорный элемент — это случайный элемент из множества, относительно которого мы будем проводить разбиение. Далее разобьём множество на три — элементы, которые больше опорного, равны ему и элементы, которые меньше. После чего рекурсивно применим алгоритм к двум оставшимся подмножествам (меньше и больше), если их длина больше единицы.

Рекурсивное решение

Ф ункция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая — длина массива минус один. Нам понадобятся следующие переменные

указывают на левый и правый элементы,

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

Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного, то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n 2 . Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов.

Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы

Далее, если границы ещё не пересеклись, то в случае, если порядок нарушен, то следует обменять местами переменные, после чего опять инкрементировать i и декрементировать j, чтобы не зациклиться.

Здесь, однако, возможна ошибка. i вряд ли переполнится — размер массива не больше, чем максимальное значение типа size_t, умноженное на размер элемента массива байт (более сложные варианты даже рассматривать не будем). Но вот переменная j вообще-то может перейти через нуль. Так как переменная целочисленная, то при переходе через нуль её значение станет больше, чем i, что приведёт к зацикливанию. Поэтому необходима превентивная проверка.

После этого цикла i и j пересекутся, i станет больше j и мы получим ещё два массива, для которых следует применить сортировку: массив от левой границы до i, и массив от j до правой границы, если, конечно, мы не вышли за пределы границ.

Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort.

Итеративное решение

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

Реализация быстрой сортировки на C/C++

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

Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.

Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.

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

Схему алгоритма можно описать таким образом:

  1. Выбрать опорный элемент в массиве — часто встречается вариант с центральным элементом.
  2. Разделить массив на две части следующим образом: все элементы из левой части, которые больше или равны опорному, перекидываем в правую, аналогично, все элементы из правой, которые меньше или равны опорному кидаем в левую часть.
  3. В результате предыдущего шага в левой части массива останутся элементы, которые меньше или равны центральному, а в правой — больше либо равны.
    Наглядно это можно показать таким образом:
    |———————|—————————|———————|
    | mas[i] = mid |
    |———————-|—————————|———————|
  4. Рекурсивно повторяем действие для левой и правой части массива.

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

Иллюстрацию одного шага алгоритма я позаимствовал отсюда , больно уж она наглядная.

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

На вход функция принимает сам массив(указатель на начало) и его размер.

Заключение

Это задание одновременно помогает понять, как работает рекурсия и учит прослеживать изменение данных во время исполнения алгоритма. Рекомендуется «дойти» и написать это самостоятельно, но все же вот моя реализация, мне и самому она может пригодиться. На этом у меня все, спасибо за внимание!

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

Алгоритм Шелла был значительным шагом в повышении эффективности сортировки по сравнению с простыми алгоритмами. Однако он явно уступает по скорости другому алгоритму, для которого его автор, Ч.Хоар, придумал несколько нескромное, но вполне заслуженное название QuickSort («быстрая сортировка»).

В основе этого алгоритма – операция разделения массива. Пусть x – некоторый произвольно выбранный элемент сортируемого массива (разделяющий элемент). Операция разделения имеет целью переставить элементы массива таким образом, чтобы сначала шли элементы, меньшие или равные x (не обязательно в порядке возрастания), а затем элементы, большие или равные x. При этом совершенно неважно, где именно окажется после разделения сам элемент x.

Чтобы выполнить разделение, начнем просматривать элементы массива слева направо и остановимся на первом из элементов, большем или равном x. Пусть индекс этого элемента равен i. Аналогичным образом, начав с правого конца массива, остановимся на самом правом элементе, меньшем или равном x (индекс элемента – j). Поменяем местами элементы i и j, а затем продолжим идти вправо от i и влево от j, меняя местами пары элементов, стоящих не на месте. Разделение окончится, когда будет i > j.

Алгоритм быстрой сортировки можно теперь описать таким образом. Возьмем произвольный элемент массива x и выполним для него операцию разделения. Если левый и/или правый отрезки массива содержат более одного элемента, то выполним для каждого из этих отрезков ту же операцию, что и для всего массива (т.е. выберем произвольный элемент, выполним разделение и т.д.). Сортировка заканчивается, когда все полученные отрезки содержат по одному элементу.

Организовать вышеописанное многократное выполнение операции разделения проще всего с помощью рекурсивного определения процедуры сортировки, как показано ниже.

procedure QuickSort(var A: TableType);

procedure SortInterval(l, h :Integer);

от индекса l до h>

while A[i] z do begin

Основная работа выполняется в рекурсивной процедуре SortInterval.

В некоторых местах программы напрашиваются улучшения. Например, хочется заменить условие цикла “while A[i]

Беда в том, что мы не можем выбирать средний по величине элемент в качестве разделяющего. Отыскание такого элемента (он называется медианой массива), как будет показано в разделе 7, представляет собой задачу не намного проще, чем сама сортировка. Поэтому приходится применять более простые правила выбора. Обычно в качестве x выбирают либо элемент из середины массива, либо элемент со случайно выбранным индексом. При этом может оказаться, что сделан самый неудачный выбор, а именно – выбран максимальный либо минимальный элемент массива. В этом случае в результате разделения массива длиной n будет получен только один отрезок длиной n–1, а второй отрезок будет содержать только один элемент. Если невезение продолжится при следующих выборах, то придется выполнить n–1 разделение, просматривая в среднем по n/2 элементов. Очевидно, в этом худшем случае Tмакс(n) = O(n 2 ), т.е. алгоритм QuickSort ведет себя не лучше пузырька.

К счастью, можно доказать, что в среднем случае, когда элементы массива случайны, имеет место такая же оценка, как и в лучшем случае: Tср(n) = O(n×log(n)). Это говорит о том, что худший случай для QuickSort является большой редкостью и может встретиться скорее в специально подобранном контрпримере, чем на практике.

Если исходный массив состоит из случайных элементов, то разделяющий элемент z может выбираться произвольным образом, можно даже всегда брать первый элемент массива в качестве разделяющего. Однако легко видеть, что выбор в качестве z первого или последнего элемента приводит к очень плохим результатам, если исходный массив оказывается уже сортированным или близким к сортированному. Поэтому, как было сказано выше, обычно выбирают элемент из середины массива или элемент со случайным номером. Иногда используют чуть более сложное правило: взять первый элемент массива, последний элемент, элемент из середины массива и выбрать в качестве x средний по величине из этих трех. В этом случае есть гарантия, что при разделении не будет получен отрезок длиной 1. Однако неясно, компенсирует ли это небольшое улучшение затраты времени на более сложное правило выбора.

Алгоритм QuickSort показал себя на практике как самый быстрый из известных алгоритмов сортировки массивов, несмотря на то, что в худшем случае он может потребовать времени порядка O(n 2 ).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент — человек, постоянно откладывающий неизбежность. 10530 — | 7319 — или читать все.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL