1

Let's say I have a 2D array and I want to pass it's i th column to a sort function that takes in a 1D array and sorts it. Can it be done without copying the column to another array in C/C++ language. I am concerned about reducing time and space used. (Ofcourse the complexity remains same)

Rahul
  • 3,479
  • 3
  • 16
  • 28
kamalbanga
  • 1,881
  • 5
  • 27
  • 46
  • I think you should be able to. Just pass the 2D array to the function. But likely you will need to write your own sort function, rather than using the generic `sort` or `qsort`. – rcs Feb 26 '14 at 09:12
  • @rcs The actual problem is quite simple to solve. In my case I just want to discover whether it can be done in the setting I have given rather than just solving the problem. – kamalbanga Feb 26 '14 at 09:17
  • Well, if you interpret you first index as column index (a[m][n] - n-th column from m-th row), then you can just pass a[m]. If talking about C++ you can use vector of vectors and don't worry about having to pass length of a column. – zoska Feb 26 '14 at 09:23

3 Answers3

4

I suppose that by sort you mean std::sort from STL, which takes random access iterators. So all you need to do is provide column iterators.

You can either implement one by yourself (example), use some iterator library (ie. Boost.Iterator) or use some matrix implementation which provides row/column iterators.

Johny
  • 1,947
  • 13
  • 23
2

If you can write your own sort function, it's rather easy; you just make the interface like this:

void Sort (T a [], size_t n,  size_t stride);

The key is in the stride parameter, which is the distance between the elements of this "virtual" array. For example, if you have a float x [10][20]; and you want to send its column #2, you'd do this: (some casts omitted for clarity)

Sort (x[0] + 2, 10, 20); // Usually, stride is the width of the 2D array

Inside the Sort function, you access the ith element of an array that has a stride like this:

a[i * stride] = 42;

That's it.

You can use the same principle to write your own MatrixColumnView class that wraps up this concept and can be passed into templated functions that take arrays.

If you want to work with STL or STL-like libraries, you can simply write your own MatrixColumnIterator iterator class that essentially uses an stride internally and gives iteration over a column of a 2D array.

yzt
  • 8,873
  • 1
  • 35
  • 44
0

As far as i know, the multidimensional array storage in C/C++ is actually a 1D-arrary,

which you can refer a very good explanation in this post : How to get column of a multidimensional array in C/C++?

Therefore I do not think there's any default / easy method to extract a particular column of a 2D array and pass it to another function.

Community
  • 1
  • 1
shole
  • 4,046
  • 2
  • 29
  • 69
  • Ok, so I discover that it cannot be done as explained in the post you referred. – kamalbanga Feb 26 '14 at 09:22
  • 1
    as Johny wrote - providing proper iterators would suffice. Iterators in C++ world is a most common structure, so I wouldn't say there is no 'easy' way – zoska Feb 26 '14 at 09:25
  • I agree with you and I upvote @Johny 's answer as well :) What I was thinking is that it is quite hard for me to pass a column directly to a his_own_sort(), without using external library or preprocessing... – shole Feb 26 '14 at 09:36