array partition function

Question

I'm writing a function that gets an array of int and its size:

void partition(int data[], int size)

The first element of the array is assigned to a variable named val, and the function needs to partition the array such that elements to the left of val are smaller than val, and elements to the right are greater.

For example,

if the array is : 5 2 10 4 1 12 7 (val becomes 5)
The output should be 2 4 1 5 10 12 7

The order doesn't matter so 1 2 4 5 12 7 10 is also valid output

So I wrote this code:

void partition(int data[], int size)
{
    int val = data[0];
    int i = 0, j = size - 1;//array indices
    while (i != j)
    {
        while (data[i] < val)
            i++;
        while (data[j] > val)
                j--;
        swapInArray(data, i, j);
    }
}

which works fine unless it gets an array with elements equivalent to val.

For example : 7 8 5 176 18 19 7 12 44

while (data[i] <= val) instead of while (data[i] < val) should do it. — R Sahu
– R Sahu, Commented Dec 28, 2015 at 22:31
it doesn't help, and moreover when changed it now program crashes even with input it worked before the change — user4464936
– user4464936, Commented Dec 28, 2015 at 22:40
The other problem was use of while (i != j) instead of while (i < j). — R Sahu
– R Sahu, Commented Dec 28, 2015 at 22:42
still not working, giving the func int data[8] = { 5, 2, 10, 4, 1, 12, 5, 7 }; and it prints 5 2 5 4 12 1 10 7 — user4464936
– user4464936, Commented Dec 28, 2015 at 22:47
I hope you've got it working by now. Just a supplementary comment - I assume this is part of an exercise towards creating a Quicksort algorithm (or something similar) so for learning it's ok, but in the real world a quality piece of code should make best use of the Standard Library. Use std::array instead of raw C-style arrays; and use std::swap instead of reinventing your own function. — Klitos Kyriacou
– Klitos Kyriacou, Commented Dec 29, 2015 at 20:03

R Sahu · Accepted Answer · 2015-12-29 17:39:13Z

3

Couple of changes should fix it.

Use while ( i < j ) instead of while ( i != j ).
Use while (data[i] <= val) instead of while (data[i] < val)

Here's my suggestion:

void partition(int data[], int size)
{
   int val = data[0];
   int i = 0, j = size - 1;
   while (i < j)
   {
      while (data[i] <= val)
         i++;
      while (data[j] > val)
         j--;
      swapInArray(data, i, j);
   }
}

Update

Couple of more changes are necessary.

Call swapInArray only if i < j.
Swap the pivot with the j-th element at the end, if necessary.

Updated function:

void partition(int data[], int size)
{
   int val = data[0];
   int i = 1, j = size - 1;//array indices
   while (i < j)
   {
      while (i < j && data[i] <= val)
         i++;

      while (data[j] > val)
         j--;

      if ( i < j )
         swapInArray(data, i, j);
   }
   if ( val > data[j] )
      swapInArray(data, 0, j);
}

See it working at http://ideone.com/5A3wTN.

edited Dec 29, 2015 at 17:39

answered Dec 28, 2015 at 22:39

R Sahu

207k15 gold badges168 silver badges291 bronze badges

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

6 Comments

user4464936 Over a year ago

still not working, giving the func int data[8] = { 5, 2, 10, 4, 1, 12, 5, 7 }; and it prints 5 2 5 4 12 1 10 7

Klitos Kyriacou Over a year ago

That's because the two inner loops pass each other without checking; i points to 12 while j points to 1, and then those two get swapped. You need to stop increasing i and decreasing j once they meet. while (i < j && data[i] <= val) and while (i < j && data[j] > val) - and if (i < j) swapInArray(...).

user4464936 Over a year ago

i didnt clearly understand what you mean. Can u show me wht changes in code to do?

Klitos Kyriacou Over a year ago

I've updated my comment above. Also, I think you need to return the index of the first element of the second part of the partitioned array; otherwise you don't know how it was partitioned.

R Sahu Over a year ago

@KlitosKyriacou, thanks for pointing out the error. It's fixed now.

|

Collectives™ on Stack Overflow

array partition function

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related