Имеет ли следующий алгоритм разбиения Quicksort стабильный вид (т.е. поддерживает ли он относительное положение элементов с равными значениями):
partition(A,p,r)
{
x=A[r];
i=p-1;
for j=p to r-1
if(A[j]<=x)
i++;
exchange(A[i],A[j])
exchang(A[i+1],A[r]);
return i+1;
}
Существует один случай, когда ваш алгоритм разбиения будет делать своп, который изменит порядок равных значений. Здесь изображение, которое помогает продемонстрировать, как работает ваш алгоритм локального разбиения:
Мы проходим через каждое значение с индексом j, и если значение, которое мы видим, меньше значения раздела, мы добавляем его в светло-серый подмассинг, заменяя его элементом, который находится справа от света -gray subarray. Светло-серый подмассив содержит все элементы, которые <= значение раздела. Теперь рассмотрим, скажем, этап (c), и рассмотрим случай, когда три 9 находятся в начале белой зоны, а затем 1. То есть мы собираемся проверить, являются ли 9 <= разделом стоимость. Мы смотрим на первые 9 и видим, что он не равен <= 4, поэтому мы оставляем его на месте и продвигаемся вперед. Мы смотрим на следующие 9 и видим, что он не равен <= 4, поэтому мы также оставляем его на месте и продвигаемся вперед. Мы также оставляем третий 9 на месте. Теперь мы посмотрим на 1 и увидим, что он меньше, чем раздел, поэтому мы заменим его первым 9. Затем, чтобы закончить алгоритм, мы заменим значение раздела значением я + 1, которое является вторым 9. Теперь мы завершили алгоритм разбиения, а 9, который был первоначально третьим, теперь первый.
Любой вид может быть преобразован в устойчивый вид, если вы хотите добавить второй ключ. Второй ключ должен быть чем-то, что указывает на первоначальный порядок, например порядковый номер. В вашей функции сравнения, если первые ключи равны, используйте второй ключ.
Сорт стабилен, когда исходный порядок подобных элементов не изменяется. Ваш алгоритм нестабилен, так как он обменивает равные элементы.
Если это не так, то оно все равно не будет стабильным:
( 1, 5, 2, 5, 3 )
У вас есть два элемента с ключом сортировки "5". Если вы по какой-то причине сравниваете элементы № 2 (5) и № 5 (3), то 5 будет заменено на 3, что нарушит договор стабильного сорта. Это означает, что тщательный выбор элемента сворачивания не помогает, вы также должны убедиться, что копирование элементов между разделами никогда не меняет первоначальный порядок.
Ваш код выглядит подозрительно похожим на примерную функцию раздела, указанную в wikipedia, которая нестабильна, поэтому ваша функция, вероятно, t стабильный. По крайней мере, вы должны убедиться, что ваша точка поворота r указывает на последнюю позицию в массиве значений, равных A [r].
Вы можете сделать quicksort стабильным (я не согласен с Мэтью Джонсом там), но не в нем по умолчанию и самой быстрой (хе) форме.
Мартин (см. комментарии) верен, что quicksort в связанном списке, где вы начинаете с первого элемента как значения pivot и append в конце нижнего и верхнего подсписок при прохождении массив. Тем не менее, quicksort должен работать с простым массивом, а не с связанным списком. Одним из преимуществ quicksort является низкая занимаемая память (потому что все происходит на месте). Если вы используете связанный список, у вас уже возникают издержки памяти для всех указателей на следующие значения и т.д., И вы меняете их, а не значения.
Если вам нужна стабильная сортировка O (n * log (n)), используйте mergesort. (Лучший способ сделать быструю сортировку стабильной, кстати, выбрать медиану случайных значений в качестве шарнира. Это не является стабильным для всех элементов эквивалентно, однако.)
Из Википедии:
Quicksort - это сортировка, и в эффективные реализации, не является стабильный вид.
Один из способов решения этой проблемы - не принимать последний элемент массива в качестве ключа. Быстрый сортировка - это рандомизированный алгоритм.
Его производительность сильно зависит от выбора Key. Хотя алгоритм def говорит, что мы должны взять последний или первый элемент в качестве ключа, на самом деле мы можем выбрать любой элемент в качестве ключа.
Итак, я попробовал метод Median of 3, в котором говорится, что требуется первый, средний и последний элемент массива. Сортирует их, а затем использует среднюю позицию в качестве ключа.
Итак, например, мой массив {9,6,3,10,15}. Поэтому, сортируя первый, средний и последний элемент, он будет {3,6,9,10,15}. Теперь используйте 9 как ключ. Таким образом, клавиша перемещения до конца будет {3,6,15,10,9}.
Все, что нам нужно позаботиться, это то, что происходит, если 9 приходит более одного раза. Это ключ, который он сам приходит не один раз.
В таких случаях после выбора ключа в качестве среднего индекса нам нужно пройти через элементы между краем "Ключ" и "Вправо", и если какой-либо элемент найден одним и тем же ключом, т.е. если между средним и последним будет найдено 9, сделайте это как 9. p >
Теперь в области элементов, больших 9, то есть цикла j, если найдется 9, замените его на область элементов, меньшую, чем область i. Ваш массив будет стабильным.
Быстрая сортировка нестабильна. Вот случай, когда он нестабилен.
5 5 4 8
взяв 1-й пятый в качестве пипетки, у нас будет следующий после 1-го прохождения -
4 5 5 8
Как вы можете видеть, порядок 5 был изменен. Теперь, если мы продолжим сортировку, он изменит порядок 5 в отсортированном массиве.