2016-05-01 3 views
1

Я хочу изменить 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, я бы очень признателен. Просто зная, как изменить это, я не очень хорошо разбираюсь в алгоритме.
Извините, если это звучит так, как будто я имею право на какую помощь я хочу!

+0

Не могли бы вы уточнить, нужна ли вам по крайней мере первая половина, отсортированная или точно первая половина? Кроме того, если вы заботитесь о второй половине, вам нужно, чтобы она была стабильной? Ваш пример указывает, что вы этого не сделали, но это поможет, если вы сделаете это явным. –

+0

По существу первый тайм. Итак, все, что происходит до медианы, нужно сортировать: так что множество как таковое [9 5 7 1 2 4 6], где 5 - медиана, частично отсортированный набор будет примерно таким же, как [1 2 4 5 9 6 7]. –

+0

Итак, сортировка всей последовательности тоже будет в порядке? Это было бы самым простым решением, которое вы ищете? Во всяком случае, вот два подхода: во-первых, найти медиану, раздел этой медианой, а затем отсортировать первый раздел. Во-вторых, для запуска алгоритма Quick Sort-like, который просто не учитывается в разделах, которые начинаются за пределами медианы. –

ответ

0

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