partition of multidimensional array

Question

i am trying to implement following algorithm: suppose there is array a[3][3], my aim is choose some pivot element,for example a[1][1] and make partition such that, all element less then a[1][1] must be on left side and above the pivot element, and all greater element on the right side and below pivot element. for example consider following matrix:

6 4 3
8 5 2
1 7 9

one of the possible partition of it is

3 4 6
2 5 7
1 8 9

as you see all less element are on the left side and above the pivot called 4. and others on the right side and below the pivot as 8. here is my code

#include <iostream>
using namespace std;
int main(){
  int a[3][3];
  for (int i=0;i<3;i++) {
    for (int j=0;j<3;j++){
      cin>>a[i][j];
    }
  }

  int i=0;
  int j=0;
  int n=2;
  int m=2;
  int pivot=a[1][1];

  while(  m>i && n>j) {
    while(a[m][n]>pivot)  --m;--n;
    while( a[i][j]<pivot) ++i;++j;

    int t=a[i][j];
    a[i][j]=a[m][n];
    a[m][n]=t;
  }

  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      cout<<a[i][j]<<"  ";
    }
    cout<<endl;
  }
  return 0;
}

but when i enter matrix above mentioned i got wrong result

6  5  3
8  4  2
1  7  9

please help me

May you forgot parenthesis after while(a[m][n]>pivot) and while( a[i][j]<pivot) ? — Manlio
– Manlio, Commented Sep 7, 2011 at 14:46

wormsparty · Accepted Answer · 2011-09-07 15:16:17Z

2

I haven't looked if your algorithm is right, but when I see:

while(a[m][n]>pivot) --m;--n;

I think you meant:

while(a[m][n]>pivot) { --m;--n; }

answered Sep 7, 2011 at 15:16

wormsparty

2,51919 silver badges32 bronze badges

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

1 Comment

user466534 Over a year ago

yes @wormsparty you are right but problem is not this. thanks for reply

Robᵩ · Accepted Answer · 2011-09-07 15:13:42Z

1

Your problem as stated does not have a general solution. Specifically, there is no guarantee that all of the values less than the initial pivot value will fit to the left of the initial pivot point, nor that all of the values greater than the initial value will fit to the right of the initial pivot point.

You need to relax your requirements so that either the pivot value or the pivot location is allowed to change during the execution of the algorithm.

edited Sep 7, 2011 at 15:13

answered Sep 7, 2011 at 15:08

Robᵩ

170k20 gold badges251 silver badges323 bronze badges

2 Comments

user466534 Over a year ago

yes now i see it, maybe pivot element is 1 so it means that such partition will be impossible,why i wanted to solve such problem is that then if we sort it's rows i think whole array will be sorted so @Rob in case of i make allowance to move pivot element also when needed how my code will change it's form?

Robᵩ Over a year ago

If the end goal is to sort the array, try this: std::sort(&a[0][0], &a[3][0]); If the end goal is to learn how to sort an array, then treat the matrix as a linear array of 9 elements and run any sorting algorithm.

Collectives™ on Stack Overflow

partition of multidimensional array

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related