Я хочу изменить quicksort, где я только сортирую верхние медианные элементы. Итак, множество как таковое [9 5 7 1 2 4 6], где 5 - медиана, частично отсортированный набор будет примерно таким же, как [1 2 4 5 9 6 7].Частично отсортированный Quicksort
template <class Comparable>
void objectSwap(Comparable &lhs, Comparable &rhs) {
Comparable tmp = lhs;
lhs = rhs;
rhs = tmp;
}
template <class Comparable>
void choosePivot(vector<Comparable> &a, int first, int last) {
int middle = (first + last)/2;
objectSwap(a[first], a[middle]);
}
template <class Comparable>
void partition(vector<Comparable> &a, int first, int last, int &pivotIndex) {
// place the pivot in a[first]
choosePivot(a, first, last);
Comparable pivot = a[first];
int lastS1 = first;
int firstUnknown = first + 1;
for (; firstUnknown <= last; ++firstUnknown) {
if (a[firstUnknown] < pivot) {
++lastS1;
objectSwap(a[firstUnknown], a[lastS1]);
}
// else item from unknown belongs in S2
}
// decide a new pivot
objectSwap(a[first], a[lastS1]);
pivotIndex = lastS1;
}
template <class Comparable>
void partialsort(vector<Comparable> &a, int first, int last) {
int pivotIndex;
if (first < last) {
partition(a, first, last, pivotIndex);
partialsort(a, first, pivotIndex - 1);
partialsort(a, pivotIndex + 1, last);
}
}
template <class Comparable>
void partialsort(vector<Comparable> &a) {
partialsort(a, 0, a.size() - 1);
}
Я наблюдал анализ сортировки на YouTube с помощью mycodeschool (дайте мне знать о любых других хороших видео, если вы знаете какой-то!), И я уверен, что мне нужно только изменить partialsort (вектор, int, int).
Моя первая реакция - подумать об этом как mergesort, взять пустой массив и остановить алгоритм после того, как длина/2 была заполнена. Но я знаю, что это не так, как работает quicksort. Все рекурсивные вызовы и то, как первое, последнее, и поворот всегда меняются, затрудняют мне отслеживать, что происходит. Я также не знаю, как я узнаю, когда у меня будет медиана. Это вопрос о домашнем задании, поэтому, если у кого-то есть только советы относительно того, как я должен подходить к этому или ресурсов, которые помогут мне лучше понять quicksort, я бы очень признателен. Просто зная, как изменить это, я не очень хорошо разбираюсь в алгоритме.
Извините, если это звучит так, как будто я имею право на какую помощь я хочу!
Не могли бы вы уточнить, нужна ли вам по крайней мере первая половина, отсортированная или точно первая половина? Кроме того, если вы заботитесь о второй половине, вам нужно, чтобы она была стабильной? Ваш пример указывает, что вы этого не сделали, но это поможет, если вы сделаете это явным. –
По существу первый тайм. Итак, все, что происходит до медианы, нужно сортировать: так что множество как таковое [9 5 7 1 2 4 6], где 5 - медиана, частично отсортированный набор будет примерно таким же, как [1 2 4 5 9 6 7]. –
Итак, сортировка всей последовательности тоже будет в порядке? Это было бы самым простым решением, которое вы ищете? Во всяком случае, вот два подхода: во-первых, найти медиану, раздел этой медианой, а затем отсортировать первый раздел. Во-вторых, для запуска алгоритма Quick Sort-like, который просто не учитывается в разделах, которые начинаются за пределами медианы. –