# qsort

• 09-16-2004
dayknight
qsort
hey,

i am having problems with partition:
Code:

```int Partition(int* panNumbers, int nSize) {                 int nPivot = panNumbers[0];         int nLeftIndex = 0;         int nRightIndex = nSize;         while (nLeftIndex < nRightIndex)         {                 while (panNumbers[nLeftIndex] <= nPivot)                         nLeftIndex++;                         while (nRightIndex > nLeftIndex)                         while (panNumbers[nRightIndex] >= nPivot)                                 nRightIndex--;                                 if (nLeftIndex < nRightIndex)                 {                                int temp = panNumbers[nLeftIndex];                         panNumbers[nLeftIndex] = panNumbers[nRightIndex];                         panNumbers[nRightIndex] = temp;                 }         } return nRightIndex; }```
i have been looking at some examples but cant seem to figure it out...
• 09-16-2004
Prelude
That's a lot of loops for a simple partition algorithm. Try something along these lines and call me in the morning:
Code:

```int partition ( int a[], int low, int high ) {   int pivot;   int i, prev;   swap ( a[low], a[( low + high ) / 2] );   pivot = a[low];   prev = low;   for ( i = low + 1; i <= high; i++ ) {     if ( a[i] < pivot )       swap ( a[++prev], a[i] );   }   swap ( a[low], a[prev] );   return prev; } void quicksort ( int a[], int low, int high ) {   int pivot;   if ( low >= high )     return;   pivot = partition ( a, low, high );   quicksort ( a, low, pivot - 1 );   quicksort ( a, pivot + 1, high ); }```
• 09-16-2004
okinrus
I have not tested this, but I think this is what you want:
Code:

```int Partition(int* panNumbers, int nSize) {     int nPivot = panNumbers[0];     int nLeftIndex = 0;     int nRightIndex = nSize;     while (nLeftIndex < nRightIndex)   {           while (panNumbers[nLeftIndex] <= nPivot)                 nLeftIndex++;                     while(panNumbers[nRightIndex] > nPivot)                 nRightIndex--;           //  panNumbers[nLeftIndex] > nPivot and panNumbers[nRightIndex] <= nPivot           //  Because of this condition we may safely swap           swap(panNumbers[nLeftIndex], panNumbers[nRightIndex]);     }     return nRightIndex;      }```
• 09-16-2004
okinrus
The assignment nRightIndex = nSize is probably wrong, depending on the meaning of the nSize parameter.
• 09-16-2004
dayknight
nSize is the size of the array.
• 09-16-2004
okinrus
Quote:

nSize is the size of the array.
Ok, you then want "nRightIndex = nSize - 1" instead of nRightIndex = nSize. You also must add code that correctly places the pivot.
• 09-17-2004
dayknight
Code:

```                Swap ( panNumbers[nLeftIndex], panNumbers[0] );                 if (panNumbers[nLeftIndex] < panNumbers[0])                         return nLeftIndex;                 else                         return nLeftIndex-1;```

it works but with 1 mistake:
ex:
Code:

```Size of Array:12 Range: 10 Random Values: 4 6 6 5 1 6 3 9 7 9 3 4 Pivot: 4 Left Side: 1 4 3 3 6 MidPoint: 4 Right Side: 5 9 7 9 6 6 Final Array: 1 4 3 3 6 4 5 9 7 9 6 6```
if u see above in the final array it swaps 1 with 4 and displays 3 after 4
• 09-17-2004
okinrus
Code:

```int Partition(int* panNumbers, int nSize) {     int nPivot = panNumbers[0];     int nLeftIndex = 0;     int nRightIndex = nSize - 1;     while (nLeftIndex < nRightIndex)     {         while (panNumbers[nLeftIndex] <= nPivot                     && nLeftIndex < nRightIndex)             nLeftIndex++;         while(panNumbers[nRightIndex] > nPivot                     && nLeftIndex < nRightIndex)             nRightIndex--;         // Because  panNumbers[nLeftIndex] > nPivot         // and panNumbers[nRightIndex] <= nPivot,         // we may safely swap         swap(panNumbers[nLeftIndex], panNumbers[nRightIndex]);     }     if (nLeftIndex > 1)         swap(panNumbers[0], panNumbers[nLeftIndex - 1]);     return (nLeftIndex > 1)? nLeftIndex - 1 : 0;      }```
Does this work?
• 09-17-2004
dayknight
it is 99% there, there is still 1 minor problem:
final array:
1 4 3 3 4 6 5 9 7 9 6 6

and also could u plz explain me the return?, like wat exactly it is doing
• 09-17-2004
okinrus
dayknight, I think this is what the final array is supposed to look like after partioning. Partioning just means that everything left of the pivot, which is index 4, is less than the pivot and everything right of the pivot is greater than the pivot. It might be a good idea to try to prove the correctness of this partioning method to see if it's really correct, but I'm rather not up to the challenge.

The return of the partioning method is an operator that evaluates differently based upon whether expression before the '?', the condition, is true. If the condition is true, then the operator evaluates to the expression inbetween the '?' and the ':'. If, however, the condition is false, the operator evaluates to the expression after the ':'.