1. ## 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...

2. 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 );
}

3. 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;
}

4. The assignment nRightIndex = nSize is probably wrong, depending on the meaning of the nSize parameter.

5. nSize is the size of the array.

6. 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.

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

8. 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?

9. 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

10. 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 ':'.

Popular pages Recent additions