Обсуждение:Быстрая сортировка
"Хоар разработал этот метод применительно к машинному переводу": источник - личный разговор с Ч. Э. Р. Хоаром. Mercury 20:17, 31 августа 2006 (UTC)
Предлагаю добавить замечание по практической реализации алгоритма: способ(ы) избежания рекурсии, например.--93.120.155.69 14:20, 5 марта 2008 (UTC)
Примеры реализации[править код]
К сожалению, версия на C работает неправильно. 62.117.90.1 10:54, 21 сентября 2006 (UTC)
Для чего здесь столько (уже 13) примеров реализации на различных языках? Скорее захламляют, чем улучшают статью. Предлагаю убрать, оставив 2-3 реализации. -- NZeemin 11:06, 24 ноября 2006 (UTC)
Пока закоментировал некоторые.... Ors archangel 13:50, 15 марта 2007 (UTC)
Алгоритм наглядно предствлен в ..видеоролике (английская редакция)!А программная реализация его -дело вкуса и не должно вызвать трудностей.
Предлагаю добавить реализацию на Brainfuck --194.44.198.45 14:24, 20 сентября 2007 (UTC)
исправил алгоритм на Си. точно работает (сам проверял). по сути это вариант из книги Сэджвика, только немного упрощённый. 83.237.48.206 19:28, 23 февраля 2008 (UTC)
Пример на Java не работает, индекс выходил за пределы границ массива. 84.51.116.134 13:03, 16 июля 2012 (UTC)
Пример на java, с, с++ и c# если передать массив {1,2}, а значения low = 0, high = 1, то будет стэковерфлоу, так как вызовется ровно с теми же параметрами
int i = low; // = 0
int j = high; // = 1
int x = A[(low+high)/2]; // = 1
do {
while(A[i] < x) ++i; // 1 < 1 - false
while(A[j] > x) --j; // 2 > 1 - true, j = 0
if(i <= j){ // 0 == 0
Обменяли A[0] и A[0]
i = 1
j = 1
} while(i < j); // 1 < 1 - false
if(low < j) qSort(A, low, j); - вызвали с теми же аргументами ({1,2}, 0,1)
Правильно ли передаются параметры в примере для С? Там указано: qsort(a, 0, N); - но при этом, далее запрашивается элемент массива: a[ N ] - которого в массиве быть не может (нумерация с нуля). Должно быть qsort( a, 0, N - 1 ); ?
109.194.220.245 19:31, 14 сентября 2015 (UTC) Гость.
Пример на Прологе не работает[править код]
Текущая версия quicksort на Прологе:
quicksort([], X, X). quicksort([H|T], S, X) :- split(H, T, A, B), quicksort(A, S, [H|Y]), quicksort(B, Y, X).
Я не только не смог понять смысл и назначение дополнительного (не знаю даже, второго или третьего) аргумента, но и не смог даже запустить этот вариант на Прологе, предполагая самые разнообразные назначения этих двух последних аргументов. Первый аргумент - судя по всему, исходный список...
В моём варианте, по сравнению со старым, я ввёл дополнительные два предиката - middle и append.
append - для того, чтобы повысить читаемость программы (то есть, теперь есть полное соответствие алгоритму быстрой сортировки: мы делим список на две части, сортируем эти два части по отдельности и потом собираем два отсортированных списка в один), в отличие от старой версии (когда список делился на две части, а потом с обоими частями производились непонятные телодвижения)
middle - чтобы в качестве разделителя выбирать центральный элемент списка, а не первый. Выбор первого элемента списка в качестве разделителя приводит ко времени сортировки О(n*n) для уже отсортированных списков.
Вспомогательные предикаты:
/* middle(L, L, X, L1) Находит в списке L центральный элемент и возвращает его в Х и список без него в L1. В первом аргументе L убираем по два элемента, а во втором аргументе L - по одному элементу. Фиксируем факт нахождения среднего элемента, если первый аргумент - пустой или содержит в себе ровно один элемент. */ middle([],[X|T],X,T). middle([_],[X|T],X,T). middle([_,_|T1],[H2|T2],X,[H2|T3]):- middle(T1,T2,X,T3). /* split(X, L, A, B) Разбивает список L на два подсписка A и B так, что все элементы А меньше Х, а все элементы В больше Х. (Куда добавляются элементы, равные Х, не имеет значения для алгоритма сортировки. Здесь они (к примеру) добавляются в В.) */ split(_, [], [], []). split(H, [A|X], [A|Y], Z) :- /* используем механизм отсечений, чтобы не проверять дважды */ order(A, H), !, split(H, X, Y, Z). /* это правило может быть применено только в случае, если not(order(A, H)) - благодаря использованному отсечению это перепроверять не нужно */ split(H, [A|X], Y, [A|Z]) :- split(H, X, Y, Z). /* append(X,Y,L) Соединяет два списка в один. Берём Х, добавляем в конец Y, получаем L. */ append([],X,X). append([H|T],X,[H|T1]):- append(T,X,T1). /* qsort(X,Y) Быстрая сортировка. Х - исходный список, Y - результат */
/* если сортируем пустой список, то
результат - пустой список
*/
qsort([], []).
qsort(L, X) :-
/* собственно, алгоритм быстрой сортировки. */
/* находим центральный элемент и удаляем его */
middle(L,L,M,L1),
/* центральный элемент будет разделителем.
разбиваем спискок без элемента-разделиеля на два списка.
*/
split(M, L1, A, B),
/* сортируем по очереди оба списка */
qsort(A, X1),
qsort(B, X2),
/* соединяем отсортированные списки в один.
не забываем поставить разделитель на место.
*/
append(X1,[M|X2],X).
если убрать предикат middle и в качестве разделителя всегда выбирать самый первый элемент списка, то второе утверждение для qsort будет таким
qsort([H|T], X) :- split(H, T, A, B), /*делим*/ qsort(A, X1), /*сортируем*/ qsort(B, X2), /*сортируем*/ append(X1,[H|X2],X). /*соединяем*/
Не стал вставлять из-за вопросов о количестве реализаций. Но оставил здесь, так как эта реализация может вызвать интерес, думаю, в первую очередь у тех, кто изучает язык Пролог --Yuri Popoff 00:24, 3 декабря 2007 (UTC)
Подозрительное условие[править код]
в описании алгоритма пункт 6:
если l < r — найденную пару элементов нужно обменять...
Разве должно быть l < r? Может всетаки l > r? --- 93.84.241.55 10:03, 1 августа 2008 (UTC)
- Нет, это условие правильное. Индексы l и r указывают на концы разделеных фрагментов; если бы l>r то разделение завершается. --CiaPan 08:14, 27 апреля 2016 (UTC)
Корректность алгоритма и выбор опорного элемента[править код]
Предлагаю заменить в пункте 2.6 фразу "значение m изменяется на r-й или l-й элемент соответственно" на "значение m изменяется на r или l соответственно". Ибо m - это индекс опорного элемента, и предложение заменить его на l-й элемент несколько некорректно. 91.199.143.34 10:49, 8 декабря 2010 (UTC)
Кто-нибудь может привести пример входных данных, когда quicksort работает с выбором медианы и работает неправильно? Всегда считал, что не может выбор опорного элемента влиять на корректность. На производительность, да.
88.201.200.66 16:56, 23 марта 2009 (UTC)
На рисунке неправильная последовательность действий алгоритма[править код]
На рисунке "Быстрая сортировка" неправильная последовательность действий: после первого шага указано что поменяются местами элементы "5" и "4", хотя, по описанному алгоритму, должны меняться элементы "7" и "4".
Судя по всему картинка была взята с английской статьи (подпись под картинкой "In-place partition in action on a small list. The boxed element is the pivot element, blue elements are less or equal, and red elements are larger.") без особого рассмотрения её (там описывается какой-то вариант алгоритма, в котором опорный элемент в начале процедуры разбития массива перемещается на последнее место).
Предлагаю заменить эту картинку на картинку с той же английской статьи (подпись под картинкой "Full example of quicksort on a random set of numbers. The boxed element is the pivot. It is always chosen as the last element of the partition.")
- Обе эти иллюстрации предназначены для модифицированного алгоритма, а не оригинального. --Кыс 19:37, 22 июня 2010 (UTC)
База рекурсии[править код]
"Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов." Это неверно, базой являются наборы из нуля и одного элемента. Набор из двух может обрабатываться общим случаем.
...разработанный английским информатиком Чарльзом Хоаром в МГУ в 1960 году.[править код]
Ребята, какое МГУ? Википедия, мда. 109.184.166.165 22:31, 13 августа 2013 (UTC)
- Такое МГУ. Вполне обычное. А что? --dm обсужд. 00:30, 14 августа 2013 (UTC)
- А, да, посмотрел, действительно МГУ, удивительно. 95.79.49.191 08:46, 14 августа 2013 (UTC)
Сообщение об ошибке[править код]
Функция partition, описанная в пункте 2.1 "Общий механизм сортировки", может уходить в бесконечный цикл. Рассмотрим работу функции на следующий входных данных: A = [0, 1, 2, 3, 8, 5, 6, 7, 8, 9, 10], lo = 0, hi = 10. Предположим, что фукнция get_pivot вернула значение 8. После выполнения цикла на строках 6-7 переменная i будет иметь значение 4. После выполнения цикла на строках 8-9 переменная j будет иметь значение 8. С этого момента цикл на строках 5-11 будет бесконечно обменивать значения элементов A[4] и a[8].
Автор сообщения: i876g35s1r 93.125.107.34 06:37, 15 августа 2017 (UTC)
- Википедия - не фонд алгоритмов и программ. Приведенный фрагмент кода - это иллюстрация, а не программный продукт. --KVK2005 (обс.) 10:14, 15 августа 2017 (UTC)
- Хоть это и пример, но он не верен. Для если после swap A[i] with A[j] дописать i := i + 1, j := j - 1 это должно исправить наблюдаемый баг. Изменения сделал --IDIB (обс.) 12:49, 2 сентября 2017 (UTC)
К обсуждению --Well-Informed Optimist (?•!) 14:51, 26 сентября 2017 (UTC)
(UTC)
Разбиение Хоара[править код]
Там рекурсия вызывается по подмассивам, включащим разрешающий элемент. В английской вики это написано, в российской нет. Должно быть: quicksort(A,lo,p); quicksort(A,p+1,hi);
Supervisual (обс.) 19:15, 23 октября 2018 (UTC)
Время работы алгоритма[править код]
Не пойму оценку под анимацией в лучшем случае: Лучшее время O(n log n) (обычное разделение) или O(n) (разделение на 3 части) 185.67.55.10 20:34, 7 ноября 2018 (UTC) Юрий.
В статье нет ничего про оценку по времени в О(n). Возможна она только если следить были ли перестановки и в случае их отсутствия не вызывать следующий шаг. Конечно на отсортированном массиве и при выборе средним опорного элемента. Но в тексте про это ничего не вижу. 185.67.55.10 20:34, 7 ноября 2018 (UTC)
Про разделение на 3 части действительно ничего нет. описан принцип действия такой сортировки --IDIB (обс.) 11:32, 9 ноября 2018 (UTC)