About the program that illustrates the Quick Sort method on wikipedia

Mr_Shameless · 03-29-2007, 05:56 AM

Here is the link: http://en.wikipedia.org/wiki/Quick_sort

But i post it here for convenience sake:

Code:

void q_sort(int numbers[], int left, int right)
{
        int l_hold=left, r_hold=right;
        int pivot=numbers[left];
        int t;
        while(left<right)
        {
                while((numbers[right]>=pivot) && (left<right))
                        right--;
                if(left!=right)
                {
                        t=numbers[left];
                        numbers[left]=numbers[right];
                        numbers[right]=t;
                        left++;
                }
                while((numbers[left]<=pivot) && (left<right))
                        left++;
                if(left<right)
                {
                        t=numbers[left];
                        numbers[left]=numbers[right];
                        numbers[right]=t;
                        right--;
                }
        }
        numbers[left]=pivot;
        pivot=left;
        left=l_hold;
        right=r_hold;
        if(left<pivot)
                q_sort(numbers, left, pivot-1);
        if(right>pivot)
                q_sort(numbers, pivot+1, right);
}

The 9th line from bottom up,

Code:

numbers[left]=pivot

what is it used for? Is it unnecessary? I dont understand. Please help me figure out. Thank you very much

Mr_Shameless · 03-29-2007, 06:08 AM

O, btw, these 3 lines:

Code:

pivot=left;
left=l_hold;
right=r_hold;

are they a bit unnecessary too? Why dont we just use q_sort(numbers, l_hold, left-1), say.

Thank you

ta0kira · 03-29-2007, 10:40 PM

That line happens to work out since the sorted element type is the same as the array boundary indicator, however if the element wasn't int-compatible then it would not work. You can remove it and the sort should still work. I've taken it upon myself to fix up the example so that it will work with other element types, plus added a few "proper" things. Here are the fixes:

Code:

void q_sort(int numbers[], int left, int right)
{
        int l_hold=left, r_hold=right;
        int pivot; //boundary indicator, not a value holder
        int t;
        while(left<right)
        {
                while((left<right) && (numbers[right]>=numbers[left])) //dynamic benchmark value
                        right--;
                if(left!=right)
                {
                        t=numbers[left];
                        numbers[left]=numbers[right];
                        numbers[right]=t;
                        left++;
                }
                while((left<right) && (numbers[left]<=numbers[right])) //dynamic benchmark value
                        left++;
                if(left!=right) //consistency
                {
                        t=numbers[left];
                        numbers[left]=numbers[right];
                        numbers[right]=t;
                        right--;
                }
        }
         /* numbers[left]=pivot; */ //who knows
         pivot=left;
         left=l_hold;
         right=r_hold;
         if(left<pivot)
                 q_sort(numbers, left, pivot-1);
         if(right>pivot)
                 q_sort(numbers, pivot+1, right);
}

Yes, I would go with what you said to remove those three lines. I would have done a lot with it, actually.

The green types should be changed to fit the element type. All others should stay the same except maybe 'int' should be unsigned. Also, the whole thing could use some cleaning up.
ta0kira

Mr_Shameless · 04-13-2007, 11:32 AM

O, thank you