C++

Forum

 
Sorting in 2d array

Paul5 (41)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
#include<iostream>
using namespace std;
int main( )
{
 int i, j, k, temp, temp1,rows,cols ;
 int a[rows][cols];
    cout<<"Enter rows:"<<endl;
	cin>>rows;
	cout<<"Enter cols:"<<endl;
	cin>>cols;            
       for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            cout << "Enter array1" << "[" << i << "]" << "[" << j << "]"<<":" << endl;
            cin >> a[i][j]; // entering values for first array
        }
       
    }   
       cout<<"Array entered:"<<endl;
	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; 
        }
        cout<<"\n";
    }          
    

    

  for(j=0;j<cols;j++)
     {
          for(i=0; i<rows; i++)
          {
                if(a[j][i]>a[j+1][i])
                {
                    temp=a[j][i];
                    a[j][i]=a[j+1][i];    
                    a[j+1][i]=temp;
                }    
             
          }
     
    }
     cout<<"\n\nArray after sorting:\n"<<endl ;
   	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; //sorted array
        }
        cout<<"\n";
    }  
 }


I am writing a program to sort each row of a 2d array but It only reads the last input row don't know why Kindly guide me
Last edited on
salem c (3700)
> int a[rows][cols];
1. C++ doesn't do variable length arrays.

> cin>>rows;
Nor is the array automagically resized just because you updated the variable.

Use a std::vector if you want to have variable sized entities.
lastchance (6980)
You declared
int a[rows][cols];
BEFORE you input rows and cols!

(The statement is actually illegal at the moment in strict standard c++, since such arrays are supposed to have their size known at compile time).
Ganado (6810)
Also, your logic around lines 34 to 47 has some issues. The max value of j can be cols - 1. Adding 1 to this will make the value be equal to cols, which will go out of bounds. But you are also seem to be using i and j backwards (mixing up cols with rows).

Tutorial on vectors: https://www.programiz.com/cpp-programming/vectors
Last edited on
Paul5 (41)
So I have to use a pre-defined array that will be better? Because purpose of program is only to calculate time complexity
Paul5 (41)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include<iostream>
using namespace std;
int main( )
{
 int i, j, k, temp, temp1,rows,cols ;
 
    cout<<"Enter rows:"<<endl;
	cin>>rows;
	cout<<"Enter cols:"<<endl;
	cin>>cols;  
	int a[rows][cols];          
       for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            cout << "Enter array1" << "[" << i << "]" << "[" << j << "]"<<":" << endl;
            cin >> a[i][j]; // entering values for first array
        }
       
    }   
       cout<<"Array entered:"<<endl;
	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; 
        }
        cout<<"\n";
    }          
    
          for(i=0; i<rows; i++)
          {
          	 for(j=0;j<cols;j++)
            {
                if(a[i][j]>a[i][j+1])
                {
                    temp=a[i][j];
                    a[i][j]=a[i][j+1];    
                    a[i][j+1]=temp;
                }    
             
           }
      
    }
     cout<<"\n\nArray after sorting:\n"<<endl ;
   	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; //sorted array
        }
        cout<<"\n";
    }  
 }

I have made some changes and now output is like this
1
2
3
4
5
6
7
8
9
 
Array entered:
9 8 7
6 5 4


Array after sorting:

8 7 6
5 4 -581195018
Ganado (6810)
You're potentially going out of bounds on lines 36, 39, 40 because of the j + 1 where j = [0, cols - 1], thus j + 1 = [1, cols].
Last edited on
Paul5 (41)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include<iostream>
using namespace std;
int main( )
{
 int i, j, k, temp, temp1,rows,cols ;
 
    cout<<"Enter rows:"<<endl;
	cin>>rows;
	cout<<"Enter cols:"<<endl;
	cin>>cols;  
	int a[rows][cols];          
       for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            cout << "Enter array1" << "[" << i << "]" << "[" << j << "]"<<":" << endl;
            cin >> a[i][j]; // entering values for first array
        }
       
    }   
       cout<<"Array entered:"<<endl;
	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; 
        }
        cout<<"\n";
    }          
    
          for(i=0; i<rows; i++)
          {
          	 for(j=0;j< cols-1;j++)
            {
                if(a[i][j]>a[i][j+1])
                {
                    temp=a[i][j];
                    a[i][j]=a[i][j+1];    
                    a[i][j+1]=temp;
                }    
             
           }
      
    }
     cout<<"\n\nArray after sorting:\n"<<endl ;
   	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; //sorted array
        }
        cout<<"\n";
    }  
 }

The output now looks like this 
1
2
3
4
5
6
7
8
9
 
Array entered:
9 8 7
6 5 4


Array after sorting:

8 7 9
5 4 6
lastchance (6980)
If you are trying to use bubble sort on each individual row ... then you are only doing a single pass (which simply gets the largest to the end of the row). You aren't completing the sort with multiple passes.

(And you are still illegally defining VLAs, but that's a pointless issue to worry about here.)
jonnin (11437)
is that what you want?
its not sorted across each row, but you have glued the columns together? I can't tell if you are happy or want more help :)
Paul5 (41)
can anyone suggest me which type of sorting technique is easy for sorting 2d arrays because my main concern is to calculate time complexity
seeplus (6591)
Do you mean something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <iostream>
#include <vector>
#include <algorithm>

std::ostream& operator<<(std::ostream& os, std::vector<std::vector<int>> a) {
    for (const auto& r : a) {
        for (const auto& e : r)
            os << e << ' ';

        os << '\n';
    }
    return os;
}

int main() {
    size_t rows {}, cols {};

    std::cout << "Enter rows: ";
    std::cin >> rows;

    std::cout << "Enter cols: ";
    std::cin >> cols;

    std::vector<std::vector<int>> a(rows, std::vector<int>(cols));

    for (size_t i {}; i < rows; ++i)
        for (size_t j {}; j < cols; ++j) {
            std::cout << "Enter array " << "[" << i << "] [" << j << "]: ";
            std::cin >> a[i][j];
        }

    std::cout << "\nArray entered:\n" << a << '\n';

    for (auto& r : a)
        std::sort(r.begin(), r.end());

    std::cout << "Array after sorting:\n" << a << '\n';
}



Enter rows: 2
Enter cols: 3
Enter array [0] [0]: 9
Enter array [0] [1]: 8
Enter array [0] [2]: 7
Enter array [1] [0]: 6
Enter array [1] [1]: 5
Enter array [1] [2]: 4

Array entered:
9 8 7
6 5 4

Array after sorting:
7 8 9
4 5 6


If you don't want to use std::sort(), but your own, then just replace L35 with your own sort code.

This will sort separately each row. Is this what you want - or do you want to sort the entire data?
jonnin (11437)
you don't even need to do any code for time complexity.
a normal sort for typical data is N*lg(N) where N is the number of items being sorted.
you can re-arrange N, eg say N = # of columns.
in that case you get N*lg(N) for each row, times the number of rows (call it R) or
R*N*lg(N)

ok, now plug in some numbers.
say you have 1000 rows and 5000 columns.
the above becomes 1000*(5000*12) or 60 million operations.
as expected, because a row is smaller than all the data, its less (about half, but depends on the input values) than sorting the same values as a 1-d array, which is
1000*5000 (5 million) * 22 (lg of 5m) is 110M.

I am not sure what the big-O notation is for R*N*lg(N) formally, though.
Paul5 (41)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include<iostream>
using namespace std;
int main( )
{
 int i, j, k, temp, temp1,rows,cols ;
 
    cout<<"Enter rows:"<<endl;
	cin>>rows;
	cout<<"Enter cols:"<<endl;
	cin>>cols;  
	int a[rows][cols]; 
	         
       for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            cout << "Enter array1" << "[" << i << "]" << "[" << j << "]"<<":" << endl;
            cin >> a[i][j]; // entering values for first array
        }
       
    }   
    
       cout<<"Array entered:"<<endl;
	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; 
        }
        cout<<"\n";
    }     
    
	for(i=0; i<rows; i++)                    
    { 		        
    for(j=0;j< cols;j++)
       {
	      for (int k = 0; k < cols - j - 1; k++)
	       {
		        if (a[i][k] > a[i][k + 1])
		        {
		          // swapping of elements
		          swap(a[i][k], a[i][k + 1]);
		        }
	       }
	   }
      
    }
    
     cout<<"\n\nArray after sorting:\n"<<endl ;
   	    for (i = 0;i < rows;i++) //row of a
    {
        for (j = 0;j < cols;j++) // col of a
        {
            
            cout << a[i][j]<<" "; //sorted array
        }
        cout<<"\n";
    }  
 }


Now this is my program for sorting 2d array And I have used bubble sort for sorting Now I have a question that this program will have same time complexity for best and worst case as bubble sort? or different due to sorting of 2d array
Last edited on
jonnin (11437)
so now its cols*cols * number of rows, since bubble is O(n*n)
doing the same things...
say you have 10 columns and 20 rows.
to bubble sort that as a 1-d, just square it, 10*20 is 200 items, 40k operations.
doing only the rows,
10*10 is 100 operations per row, * 20 rows, is 2000 operations.

but it depends on the input, same as last time. one row and 40k items is the same as 1-d.
40k rows of 1 item is virtually instant. The more columns you have, the slower it gets, because you are sorting across columns.

technically, its the SAME time complexity, but the shape of the data changes the N in the big-O notation, usually by decreasing it, apart from the 1 row example. However, as you can see above, 40k vs 2k is a huge difference and that is for a small input really. Most of the time, again depending on # of columns, the 2d sort is going to run a lot faster than 1-d (and it did above with standard sort too, the type of sort does not change this fact, just changes how much work is done either way).
Last edited on
Paul5 (41)
@jonnin So time complexity will be O(n^3) or O(n^2)
because in 1d array bubble sort has two loops but for 2d array bubble sort has three loops
lastchance (6980)
Your time complexity is O(N^3) - three nested loops each doing O(N) operations (presuming that the number of rows and columns are both O(N) ).
Last edited on
salem c (3700)
Code is a visual mess.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include<iostream>
using namespace std;
int main()
{
  int i, j, k, temp, temp1, rows, cols;

  cout << "Enter rows:" << endl;
  cin >> rows;
  cout << "Enter cols:" << endl;
  cin >> cols;
  int a[rows][cols];

  for (i = 0; i < rows; i++)    //row of a
  {
    for (j = 0; j < cols; j++)  // col of a
    {
      cout << "Enter array1" << "[" << i << "]" << "[" << j << "]" << ":" << endl;
      cin >> a[i][j];           // entering values for first array
    }
  }

  cout << "Array entered:" << endl;
  for (i = 0; i < rows; i++)    //row of a
  {
    for (j = 0; j < cols; j++)  // col of a
    {
      cout << a[i][j] << " ";
    }
    cout << "\n";
  }

  for (i = 0; i < rows; i++) {
    for (j = 0; j < cols; j++) {
      for (int k = 0; k < cols - j - 1; k++) {
        if (a[i][k] > a[i][k + 1]) {
          // swapping of elements
          swap(a[i][k], a[i][k + 1]);
        }
      }
    }
  }

  cout << "\n\nArray after sorting:\n" << endl;
  for (i = 0; i < rows; i++)    //row of a
  {
    for (j = 0; j < cols; j++)  // col of a
    {
      cout << a[i][j] << " ";   //sorted array
    }
    cout << "\n";
  }
}

Find your IDE tab setting option and set it to always use spaces.

> So time complexity will be O(n^3) or O(n^2)
Somewhere between the two.

> for (int k = 0; k < cols - j - 1; k++)
This would seem to be a factor of N/2 rather than N.
But asymptotically, we only care about the biggest term, which generally means it's O(N3).

jonnin (11437)
BUT you must take care what N represents!
Its N^3 (very roughly, keep reading) where N is # of columns, not the whole matrix. You do an N^2 bubble sort on each row, where N is the number of columns, that for each row (I guess you can call this N, but it could be 1 or a billion, just as # columns can be 1 to a billion).
if its a 1 x 1billion it will be just one N*N bubble sort of a billion items. This will take a while on any computer, many seconds at best, probably a min or two. I am using a billion here for whatever huge value you want to talk about. It can be 2^63 or whatever -- the value is an example...
if its a billion x 1 it will be a no-sort (one item already sorted, O(1) operations done). This will finish near instantly.
So I don't see how you can call that N^3 and quit, since its a 2 variable determination?
Its R * N^2 where R is a variable, not a constant, for # rows and N is # of columns. I don't, again, recall the formal way to state that, but it doesn't look like a pure N*N*N to me.

I guess the average case is a square matrix where R == N and that I guess you could fudge around and say N^3 where N == the dimension. Calling square the 'average case' is some fast and loose analysis, though, unless you have more info on potential inputs.

Remember that talking N*N for bubble sort is all the items being sorted, which usually means all the data, so this is a little different from that, its easy to forget what N means if you are comparing such things...
Last edited on
Topic archived. No new replies allowed.