Я хотел бы знать, сколько сравнений, в худшем случае, QuickSort необходимо отсортировать двоичный массив размером n.
Я не могу понять, в чем наихудший случай для этой проблемы. [0 1 0 1 0 1..]?
Приветствия,
EOБыстросортирующий двоичный массив
Не совсем быстрой сортировки, но если вы хотите, чтобы отсортировать двоичный массив вы можете сделать это в O (N). Просто подсчитайте количество 1 и 0, которые у вас есть, затем напишите в том порядке, в котором вы хотите.
Например, для следующего массива:
[0 1 0 1 0 1 1]
Вы можете рассчитывать, в О (п), что у вас есть три 0 и четыре 1-х. Затем вы просто переписываете свой массив сначала с тремя 0, а затем с четырьмя 1.
, но в этом случае вы повторили через массив 2 раза один для подсчета и один для записи –
Правильно, но алгоритм O (n). –
Второй проход не выполняет сравнения ключей. –
Сортировка массива, состоящего из небольшого количества уникальных ключей, является обычной практикой. Один алгоритм, который адаптируется к O (n) времени, когда количество уникальных ключей - O (1). Что в вашем случае есть только два уникальных ключа.
QuickSort является O (NlogN) в среднем, но O (N^2) на худшем случае, для вашего случая я проверил алгоритм быстрой сортировки на этом массиве [ 0 1 1 0 1 0 1 0 0 0 1 0 1 ], то длина массива является 13 элементов, и алгоритм принимает 170 итерацию для сортировки этого массива, который равен n^2.
И этот псевдо код O (N) алгоритма:
let n0 <- 0;
for i=0 to lenght(A)
if A[i] == 0
A[n0] = 0;
++n0
for i=n0 to lenght(A)
A[i] = 1
худший случай O (n2) не имеет отношения к содержанию, но в среднем это будет O (п § п) –
Если вы знаете массив состоит только из 0 и 1, тогда не используйте quicksort. Простой раздел будет достаточно хорошим. –
Я знаю, что это не лучший способ использовать quicksort, но мне нужно знать его худшую сложность в этой проблеме. – eouti