Быстрая сортировка - выбор центральной оси - некоторые элементы вышли из строя - PullRequest
Новая
       8

Быстрая сортировка - выбор центральной оси - некоторые элементы вышли из строя

0 голосов
/ 13 января 2020

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

template<typename ItemType>
void sortFirstMiddleLast(ItemType theArray[], int first, int middle, int last) {

    ItemType temp, temp2, temp3;

    if (theArray[first] > theArray[middle]) {

        temp = theArray[first];
        theArray[first] = theArray[middle];
        theArray[middle] = temp;

    }
    if (theArray[middle] > theArray[last]) {

        temp2 = theArray[last];
        theArray[last] = theArray[middle];
        theArray[middle] = temp2;
    }
    if (theArray[first] > theArray[middle]) {

        temp3 = theArray[first];
        theArray[first] = theArray[middle];
        theArray[middle] = temp3;

    }
}

template<typename ItemType>
int partition(ItemType theArray[], int first, int last)
{
    ItemType temp;

    //Choose pivot and reposition it
    int mid = first + (last - first) / 2;

    sortFirstMiddleLast(theArray, first, mid, last);

    //Interchange
    temp = theArray[last - 1];
    theArray[last - 1] = theArray[mid];
    theArray[mid] = temp;

    int pivotIndex = last - 1;
    ItemType pivot = theArray[pivotIndex];

    //Determine the regions S sub 1 and S sub 2
    int indexFromLeft = first + 1;
    int indexFromRight = last - 2;


    bool done = false;

    while (!done) {

        //locate first entry on left that is >= pivot
        while (theArray[indexFromLeft] < pivot)
            indexFromLeft = indexFromLeft + 1;
        //locate first entry on right that is <= pivot 
        while (theArray[indexFromRight] > pivot)
            indexFromRight = indexFromRight - 1;
        //now indexFromLeft has a new index subscript and indexFromRight has a new index subscript
        //compare the two indexes 
        if (indexFromLeft < indexFromRight) {

            ItemType temp2 = theArray[indexFromRight];
            theArray[indexFromRight] = theArray[indexFromLeft];
            theArray[indexFromLeft] = temp2;
            indexFromLeft = indexFromLeft + 1;
            indexFromRight = indexFromRight - 1;

        }
        else
            done = true;
    }
    //Place pivot in proper position between Ssub1 and Ssub2 and mark its new location
    pivot = theArray[pivotIndex];
    theArray[pivotIndex] = theArray[indexFromLeft];
    theArray[indexFromLeft] = pivot;
    pivotIndex = indexFromLeft;

    return pivotIndex;

}

template<typename ItemType>
void quickSort(ItemType theArray[], int first, int last) {
    //sift out small arrays 

    int n = last - first + 1;

    if ( n < MIN_SIZE){//array is of size < 10 so use insertion sort

        insertionSort(theArray, n);

    }
    else {
        //Make the partition : S1 | Pivot | S2
        int pivotIndex = partition(theArray, first, last);

        //Sort subarrays S1 and S2
        quickSort(theArray, first, pivotIndex - 1);
        quickSort(theArray, pivotIndex + 1, last);

    }

}

const int RAND_NUMSIZE = 51; // for quick sort array size (random number gen 1-50)
const int MIN_SIZE = 10;//specify size of smallest array to use quick sort

int main()
{
int array5[RAND_NUMSIZE] = { 50, 41, 45, 43, 48, 40, 47, 42, 46, 49, 44, 39, 31, 37, 35, 33, 32, 38, 33, 34, 30, 36, 21, 29, 20, 22, 28, 23, 27, 24, 26, 25, 19, 13, 18, 14, 17, 15, 16, 12, 10, 11, 7, 8, 1, 4, 2, 6, 3, 9, 5 }

    std::cout << "\nThe quick sort array before sorting: \n";
    for (int i = 0; i < RAND_NUMSIZE; i++) {
        std::cout << array5[i] << ' ';
    }
    //call quick sort
    quickSort(array5, 0, RAND_NUMSIZE - 1);
    std::cout << "\nThe quick sort array after sorting: \n";
    for (int i = 0; i < RAND_NUMSIZE; i++) {
        std::cout << array5[i] << ' ';
    }

Ссылка на изображение, отображающее результаты, о которых я говорю:

вывод консоли quickSort

Ответы [ 2 ]

1 голос
/ 14 января 2020

Я думаю, у вас есть проблема в вашем quickSort() здесь: 

if (n < MIN_SIZE) { //array is of size < 10 so use insertion sort
    insertionSort(theArray, n);
}

Когда у вас небольшой раздел, вы всегда вставляете сортировку первых n элементов theArray.

Вы действительно хотите отсортировать диапазон от first до last. Вы можете сделать это, передав указатель на theArray[first] и небольшой размер раздела, например: 

if (n < MIN_SIZE) { //array is of size < 10 so use insertion sort
    insertionSort(theArray + first, n);
}

Конечно, вы также хотите убедиться, что сортировка вставок также правильна ...

0 голосов
/ 14 января 2020

Проблема решена, как только я исправил реализацию моего базового случая в функции быстрой сортировки, вместо использования сортировки вставкой, я вызвал sortFirstMiddleLast после установки значения константы MIN_SIZE равным 4, таким образом используя функцию выбора сводной последовательности для сортировки 3 записей вместо того, чтобы вызывать ошибку logi c, пытаясь использовать разбиение и рекурсию для небольших подмассивов. 

template<typename ItemType>
void quickSort(ItemType theArray[], int first, int last) {
    //relegate out small arrays 

    int n = last - first + 1;//index range of elements to consider

    int middle = first + (last - first) / 2;

    if ( n < MIN_SIZE){//array is of size < 4 so no partition or quick sort

        sortFirstMiddleLast(theArray, first, middle, last);//base case

    }
    else {
        //Make the partition : S1 | Pivot | S2
        int pivotIndex = partition(theArray, first, last);

        //Sort subarrays S1 and S2
        quickSort(theArray, first, pivotIndex - 1);
        quickSort(theArray, pivotIndex + 1, last);

    }


}
...