почему эта программа не получает условия прямо перед разделом?

Question

Я писал программу для сортировки с использованием алгоритма Quick-Sort .Но моя программа не понимает ситуацию прямо перед разделом. Например, если я ввожу 5 чисел:

100  200  30  1  2

// after first quick sort (considering 30 as the pivot element)

2  200  30  1  100 // i get this fine

// after second quick sort

2   1  30  200  100 // but don't get this one

После того, как я ввел эти числа, я получаю вывод как:

pivot encountereed
2 , 30 , 30 , 1 , 100 ,
2 , 30 , 30 , 1 , 100 ,
2 , 30 , 30 , 1 , 100 ,

Программа

/*
 * @ author Suhail Gupta
 */

включает

using namespace std;

void quickSort(unsigned int,int,int*,int*);
int *ptrTowardsRight; // pointer that points to the element to its right  ( ---> )
int *ptrTowardsLeft;  // pointer that points to the element to its left  ( <--- )
int *arr;
int size;
bool pivotEncountered = false;

int main()
{

    cout << "Number of elements you want to sort : ";
    cin >> size;

    cout << "Enter the numbers : " << endl;
    arr = new int[size]; // declare the size of array
    for(int i = 0 ; i < size ; i++)
    {
        cout << i+1 << ".) ";
        cin >> arr[i];
    }

    int left = arr[0];
    int right = arr[size-1];
    unsigned int pivotIndex = (int)size/2;
    int pivotVal = arr[pivotIndex];

    ptrTowardsRight = &arr[0];
    ptrTowardsLeft = &arr[size-1];
    // call the function to start quick sort
    quickSort( pivotIndex , pivotVal , ptrTowardsRight , ptrTowardsLeft);
}

void quickSort(unsigned int pivotIndex , int pivotVal , int *ptrTowardsRight , int *ptrTowardsLeft )
{

    int count_RP = size-1; // count right of pivot , gets the index of backend
    while(*ptrTowardsLeft >= pivotVal)
    {
        if(*ptrTowardsLeft == pivotVal)
        {
            pivotEncountered = true;
            break;
        }
        ptrTowardsLeft--;
        count_RP--;
    }

    int count_LP = 0;// count left of pivot , gets the index of front end
    while(*ptrTowardsRight <= pivotVal)
    {
        if(*ptrTowardsRight == pivotVal)
        {
            pivotEncountered = true;
            break;
        }
        ptrTowardsRight++;
        count_LP++;
    }

    // Now swap the values
    int temp = arr[count_LP];
    arr[count_LP] = *ptrTowardsLeft;
    arr[count_RP] = temp;
    // values swapped

    ptrTowardsRight = &arr[count_LP];
    ptrTowardsLeft = &arr[count_RP];

    if(pivotEncountered)
    {
        // call to partition(...)
        cout << "pivot encountereed";
    }
    else
    {
        quickSort(pivotIndex,pivotVal,ptrTowardsRight,ptrTowardsLeft);  // recursive call to quickSort(...)
    }
    cout << endl;

    for(int i = 0 ; i < size ; i++)
    {
        cout << arr[i] << " , ";
    }

}

Где логика в программе работает неправильно? Если я прокомментирую рекурсивный вызов для quickSort(...), то вывод будет таким, каким он должен быть. (2 200 30 1 100)

Answer 1

На самом деле все неправильно:

// after first quick sort (considering 30 as the pivot element)

2  200  30  1  100 // i get this fine

НЕ хорошо! 200 больше, чем 30 (стержень), поэтому он должен быть справа от него. 1, OTOH, должно быть слева от него (что-то вроде 2 1 30 200 100).

 // Now swap the values
 int temp = arr[count_LP];
 arr[count_LP] = *ptrTowardsLeft;
 arr[count_RP] = temp;

Это не сработает, если у вас есть ptrTowardsLeft / Right аргументы, не указывающие на конец / начало массива. Попробуйте использовать только свои указатели, и не трогайте arr.

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

Answer 2

Все отлично работает, кроме последнего вызова, когда *ptrTowardsLeft и *ptrTowardsRight оба равны 30. Так что в этом случае также происходит обмен. Чтобы избежать этого:

if(pivotEncountered != true) {  // use this condition 
 // Now swap the values
 int temp = arr[count_LP];
 arr[count_LP] = *ptrTowardsLeft;
 arr[count_RP] = temp;
// values swapped
 ptrTowardsRight = &arr[count_LP];  
 ptrTowardsLeft = &arr[count_RP];
} 

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

выход

2 , 1 , 30 , 200 , 100 // after encountering the pivot element

Хотя этот код требует много исправлений.