Разница двух версий раздела, используемых в быстрой сортировке
Первый простой, просто идите с обеих сторон, пока не найдете реверсию.
/*C++ version, [first, last), last needs --first to fetch the last element*/
/*returns the middle of partitioning result*/
int* partition( int *first, int *last, int pivot ) {
while (true) {
while (*first < pivot) ++first;
--last;//Don't edit this, it's true.
while (pivot < *last) --last;
if (!(first < last)) return first;
swap(*first, *last);
++first;
}
}
Второй (показан вВведение в алгоритмы«) является:
int* partition( int a[], int n, int pivot ) {
bound = 0;
for ( i = 1; i != n; ++i )
if ( a[i] < pivot )
swap( &a[i], &a[++bound]);
swap(a, a + bound);
return a + bound;
}
Инвариант второго » Все элементы перед границей меньше, чем пивот «
Q: А в чем преимущества и недостатки двух версий?
Я приведу один первый, второй требует операции ++ на итераторе (указателе), чтобы его можно было применить к некоторым ForwardIterator как итератор связанного списка. Другие советы?
Решение
Что касается основной идеи двух алгоритмов, то оба они верны. Они будут делать то же количество сравнений, но второе сделает больше свопов, чем первое.
Вы можете увидеть это, пройдя по алгоритмам, которые разделяют массив 1 9 2 8 3 7 4 6 5 используя 5 в качестве оси. Когда первый алгоритм меняет местами два числа, он никогда не касается ни того, ни другого. Второй алгоритм сначала меняет местами 9 и 2, затем 9 и 3 и т. Д., Принимая несколько перестановок, чтобы переместить 9 в свою конечную позицию.
Есть и другие отличия. Если я не допустил ошибок, вот как первый алгоритм разделяет массив:
1 9 2 8 3 7 4 6 5
f l
1 9 2 8 3 7 4 6 5 # swap 9,5
f l
1 5 2 8 3 7 4 6 9 # swap 8,4
f l
1 5 2 4 3 7 8 6 9 # return f = 5
l f
Вот как второй алгоритм разделяет массив:
1 9 2 8 3 7 4 6 5 # 1<5, swap 1,1
bi
1 9 2 8 3 7 4 6 5 # 9>5, no swap
bi
1 9 2 8 3 7 4 6 5 # 2<5, swap 9,2
b i
1 2 9 8 3 7 4 6 5 # 8>5, no swap
b i
1 2 9 8 3 7 4 6 5 # 3<5, swap 9,3
b i
1 2 3 8 9 7 4 6 5 # 7>5, no swap
b i
1 2 3 8 9 7 4 6 5 # 4<5, swap 8,4
b i
1 2 3 4 9 7 8 6 5 # 6>5, no swap
b i
1 2 3 4 9 7 8 6 5 # 5=5, exit loop, swap 9,5
b i
1 2 3 4 5 7 8 6 9 # return b = 4
b i
Обратите внимание, что это делает 5 перестановок, по сравнению только с 2 другими алгоритмами. Он также перемещает последний элемент в массиве в средний массив. В этом случае последним элементом является точка, так что эта точка перемещается в середину, но это не общий случай.
Другие решения
Других решений пока нет …