I was writing a program to sort using Quick-Sort algorithm. But my program does not get the situation right just before partition.For example if i enter 5 numbers :

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

After i have entered these numbers i get the output as :

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

Program

/*
 * @ author Suhail Gupta
 */

include

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] << " , ";
    }

}

Where does the logic in the program go wrong ? If i comment the recursive call to the qui开发者_高级运维ckSort(...) , then the output is , what it should be. (2 200 30 1 100)

Everything works fine except the last call when *ptrTowardsLeft and *ptrTowardsRight both are equal to 30. So in this case also swapping is done. To avoid this :

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];
} 

and after this else part won't work and you can carry on your partition.

output

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

Though this code requires many fixes.

Actually, it is all wrong:

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

2  200  30  1  100 // i get this fine

NOT fine! 200 is more than 30 (the pivot), so it should be to the right of it. 1, OTOH, should be to the left of it (something like 2 1 30 200 100).

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

This is not gonna work once you have ptrTowardsLeft/Right arguments not pointing at the end/beginning of the array. Try to use your pointers only, and don't touch arr.

Also, the structure of your algorithm doesn't even resemble to QuickSort. QuickSort swaps the elements so that all values less than the pivot are in the left part and values greater than the pivot are in the right. Then recurse to sort the two parts of the array. You don't do anything like that.