Quick sort partition algorithm

Question

void partition(int *a, int size) {
   int pivot = a[0];
   int left = 0, right = 0;
   for(left = 1, right = size-1; left <= right; left++, right--) {
       if(a[left] >= pivot && a[right] <= pivot){
           swap(left, right, a);
       }
   }
   swap(0, right, a);
}

I wrote this method to partition an array as a preliminary step in order to apply quick sort, I tested it on this sample data:

8 2 5 13 4 19 12 6 3 11 10 7 9

the correct output should be:

6 2 5 7 4 3 8 12 19 11 10 13 9

but the actual output is:

6 2 5 13 4 3 8 12 19 11 10 7 9

The algorithm has to swap 13 with 7 but it fails due to the && condition in the above loop. I want to increment left only if a[left] >= pivot and decrement right only if a[right]<= pivot.

just in case this is not some sort of learning exercises: en.cppreference.com/w/cpp/algorithm/sort — 111111
– 111111, Commented Dec 8, 2012 at 21:43
@111111: Considering the question, std::partition would be the more appropriate reference. — Jerry Coffin
– Jerry Coffin, Commented Dec 8, 2012 at 21:46
@111111: I hope he wasn't too. I, however, am so old I was actually the original inventor of the wheel. :-) — Jerry Coffin
– Jerry Coffin, Commented Dec 8, 2012 at 21:50
@111111: no, he invented the wheel — it's a square (sometimes round) thingy found on wheelbarrows, bicycles, carts, and cars. — Jonathan Leffler
– Jonathan Leffler, Commented Dec 8, 2012 at 21:55
I hope this is homework: given the choice of the pvot, the degenerate case is sorted, or almost sorted input. For the rest, the simplest (but not the most optimal) solution for doing the partitioning is the one used by Jon Bentley in his Programming Pearls book. All of the others I've seen have more or less tricky edge conditions. — James Kanze
– James Kanze, Commented Dec 8, 2012 at 22:01

JasonD · Accepted Answer · 2012-12-08 21:57:58Z

3

You more or less answered your own question. You probably want to do something like this:

void partition(int *a, int size) {
    int pivot = a[0];
    int left, right;
    for(left = 1, right = size-1; left < right; )
    {
        if(a[left] > pivot && a[right] <= pivot)
        {
            swap(left, right, a);
        }
        if(a[left] <= pivot) left++;
        if(a[right] > pivot) right--;
    }
}

answered Dec 8, 2012 at 21:57

JasonD

16.6k2 gold badges31 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

amit Over a year ago

Worth mentioning that using the first element as the partition pivot is a bad practice, since then quicksort decays to worst case on a sorted/almost sorted array - which is not as rare as we wanted it to be.

user3210502 · Accepted Answer · 2015-04-22 15:32:12Z

2

here is another option, little bit more similar to the original one

int partition(int arr[], int left, int right)
{
    int pivot = arr[left];
    while (left != right)
    {
        if (arr[left] > arr[right])
        {
            swap(arr[left], arr[right]);
        }
        if (pivot == arr[left])
            right--;
        else // Pivot == arr[right]
            left++;
    }
    return left;
}

answered Apr 22, 2015 at 15:32

user3210502

335 bronze badges

Collectives™ on Stack Overflow

Quick sort partition algorithm

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related