быстрая сортировка — целые числа разделов C ++ при дублировании Pivot

Question

быстрая сортировка — целые числа разделов C ++ при дублировании Pivot

Обновлено:

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

Такой как массив как:

[5, 3, 2, 4, 3, 1]

на основе оси 3, чтобы

[меньше 3 || 3, 3, больше 3]

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

[меньше 3 || 3, больше или равно 3]

это означает, что 3 не должны быть рядом друг с другом.

И мой код ниже (

int partition(std::vector<int>& v, int pivot)
{
int left = 0;
int right = v.size()-1;
while (left != right)
{
while (v[left] < pivot) ++left;
while (pivot < v[right]) --right;
swap(v[left], v[right]);
}
return left;
}

Бен отмечает, что я должен обновить один критерий с равным, так что один критерий<‘а другой’> = ‘, это сделает условие выполненным.

Тем не менее, раздел

5, 3, 2, 4, 3, 1

на основе оси 3, будет

< 3 || 3, 4, 3, 5

И тройки не соседствуют.

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

0

c++partitioning quicksort

Решение

Другие решения

Попробуйте следующее

#include <iostream>
#include <vector>
#include <utility>

std::vector<int>::size_type partition( std::vector<int> &v, int pivot )
{
std::vector<int>::size_type i = 0, j = v.size();

while ( i != j )
{
while ( i != j && v[i] < pivot ) i++;
while ( i != j && !( v[--j] < pivot ) );
if ( i != j ) std::swap( v[i++], v[j] );
}

return i;
}

int main()
{
std::vector<int> v = { 1, 4, 3, 5, 4, 6 };

std::vector<int>::size_type n = partition( v, 4 );

for ( std::vector<int>::size_type i = 0; i < n; i++ )
{
std::cout << v[i] << ' ';
}
std::cout << std::endl;

for ( std::vector<int>::size_type i = n; i < v.size(); i++ )
{
std::cout << v[i] << ' ';
}
std::cout << std::endl;

return 0;
}

Выход

1 3
4 5 4 6

1

Источник

Accepted Answer

Поменяйте одного из ваших операторов на <=, вместо <,

while (v[left] < pivot) ++left;
while (pivot <= v[right]) --right;

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

Для обобщенного функтора сравнения вы можете просто поменять местами параметры и инвертировать результат, чтобы получить тот же эффект:

while ( compare(v[left], pivot) ) ++left;
while ( !compare(v[right], pivot) ) --right;

1