Sorting 2d Arrays using std::sort (column based)

Question

I'm running a test showing the benefits of sorting a 2d array, by columns, by pulling the data off into an individual array and sorting that array, then copying it back to the column. I'm wanting to run std::sort as a the sorting algorithm for every run. I'm trying to figure out how to run the loop in place first, before moving into the copying on and off the 2D array. An example of the input / output would be this.

#include <iostream>
#include <algorithm>

int main() {
    int input[][5] =  { { 13, 27, 4 , 1 , 11 },
                        { 11, 19, 2 , 37, 1  },
                        { 32, 64, 11, 22, 41 },
                        { 71, 13, 27, -8, -2 },
                        { 0 , -9, 11, 99, 13 } };

    // std::sort something here.

    int output[][5] = { { 0 , -9, 2 , -8, -2 },
                        { 11, 13, 4 , 1 , 1  },
                        { 13, 19, 11, 22, 11 },
                        { 32, 27, 11, 37, 13 },
                        { 71, 64, 27, 99, 41 } };                      
    return 0;
}

Thanks for the help.

Do you want to sort each array separately or is the 2D array considered one big one? — Caesar
– Caesar, Commented Jan 8, 2014 at 4:41
I basically want to isolate each column and sort that column. — Kevin Melkowski
– Kevin Melkowski, Commented Jan 8, 2014 at 4:44
Maybe you should have a look into how to rotate the matrix you have there, sort each row, and rotate back. — Aesthete
– Aesthete, Commented Jan 8, 2014 at 4:49
Standard sort take iterators. You could define you own iterator that steps row-lenght spaces. — RichardPlunkett
– RichardPlunkett, Commented Jan 8, 2014 at 4:50

Jarod42 · Accepted Answer · 2014-01-08 09:27:35Z

You may write your own iterator, something like:

#include <iterator>

template<typename Container>
class column_iterator : public std::iterator<std::random_access_iterator_tag,
                                            typename std::decay<decltype(std::declval<Container>()[0][0])>::type>
{
    typedef typename Container::iterator iterator;
    typedef typename std::decay<decltype(std::declval<Container>()[0][0])>::type type;
public:

    column_iterator(iterator it, int n) : it(it), n(n) {}

    column_iterator& operator++() {++it; return *this;}
    column_iterator& operator++(int) { auto res(*this); ++*this; return res;}
    column_iterator& operator +=(std::ptrdiff_t offset) { it += offset; return *this;}
    column_iterator operator +(std::ptrdiff_t offset) const { auto res(*this); res += offset; return res;}

    column_iterator& operator--() {--it; return *this;}
    column_iterator& operator--(int) { auto res(*this); --*this; return res;}
    column_iterator& operator -=(std::ptrdiff_t offset) { it -= offset; return *this;}
    column_iterator operator -(std::ptrdiff_t offset) const { auto res(*this); res -= offset; return res;}

    type& operator*() { return (*it)[n];}
    type* operator->() { return &(it)[n];}

    bool operator == (const column_iterator& rhs) const { return it == rhs.it && n == rhs.n; }
    bool operator != (const column_iterator& rhs) const { return !(*this == rhs); }
    bool operator < (const column_iterator& rhs) const { return it < rhs.it; }

    std::ptrdiff_t operator -(const column_iterator& rhs) const { return it - rhs.it; }

private:
    iterator it;
    int n;
};

template<typename Container>
column_iterator<Container> begin(Container& cont, int n)
{
    return column_iterator<Container>(cont.begin(), n);
}

template<typename Container>
column_iterator<Container> end(Container& cont, int n)
{
    return column_iterator<Container>(cont.end(), n);
}

Now, let's test it:

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
#include <cassert>

void display(const std::vector<std::array<int, 5>>& v)
{
    for (auto rows : v) {
        for (auto elem : rows) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::array<int, 5>> input {
                        {{ 13, 27, 4 , 1 , 11 }},
                        {{ 11, 19, 2 , 37, 1  }},
                        {{ 32, 64, 11, 22, 41 }},
                        {{ 71, 13, 27, -8, -2 }},
                        {{ 0 , -9, 11, 99, 13 }} };

    for (int i = 0; i != 5; ++i) {
        std::sort(begin(input, i), end(input, i));
    }

    display(input);

    const std::vector<std::array<int, 5>> output {
                        {{ 0 , -9, 2 , -8, -2 }},
                        {{ 11, 13, 4 , 1 , 1  }},
                        {{ 13, 19, 11, 22, 11 }},
                        {{ 32, 27, 11, 37, 13 }},
                        {{ 71, 64, 27, 99, 41 }} };

    assert(input == output);
    return 0;
}

HaseebR7 · Accepted Answer · 2014-01-08 04:55:32Z

1

You can copy each column into a temp array,sort them and put them back into output array

for(j=0;j<5;++j)
{
 for(i=0;i<5;++i)
  {
    temp[i]=input[i][j];
  }
    //sort temp[i]
    //put it in output array
}

edited Jan 8, 2014 at 4:55

answered Jan 8, 2014 at 4:50

HaseebR7

4574 silver badges12 bronze badges

1 Comment

Kevin Melkowski Over a year ago

Planning on doing that later for a comparison, baseline is an inline sort.

Kevin Melkowski · Accepted Answer · 2014-01-08 06:02:22Z

I finally gave up and decided to write my own version to compare with. I think I'm just going to keep all versions of the sorting algorithm similar to this.

@RichardPlunkett I tried creating my own compare function but was worried about it swapping entire rows.

#include <iostream>
#include <vector>
#include <random>

void sort (std::vector<std::vector<int> >& array, int start, int stop, int pos) {
  if (stop - start < 2) return;

  int mid = (start + stop) / 2;
  int i = start, j = stop, pivot = array[mid][pos];
  while (true) {
    while (array[i][pos] < pivot) i++;
    while (array[j][pos] > pivot) j--;
    if (i > j) break;
    std::swap(array[i++][pos], array[j--][pos]);
  }

  sort (array, start, j, pos);
  sort (array, i, stop, pos);
}

int main() {
  const int size = 10;
  std::random_device rd;
  std::default_random_engine generator(rd());
  std::uniform_int_distribution<int> distribution(-10,10);
  std::vector<std::vector<int> > test(size, std::vector<int>(size));

  std::cout << "Unsorted array: \n";
  for (int i=0;i<(int) test.size();++i) {
    for (int j=0;j<(int) test[i].size();++j) {
      test[i][j] = distribution(generator);
      std::cout << test[i][j] << '\t';
    }
    std::cout << std::endl;
  }

  for (int i=0;i<size;++i)
    sort(test, 0, size-1, i);

  std::cout << "\nSorted array: \n";
  for (int i=0;i<(int) test.size();++i) {
    for (int j=0;j<(int) test[i].size();++j)
      std::cout << test[i][j] << '\t';
    std::cout << ' ' << std::endl;
  }
  return 0;
}

Collectives™ on Stack Overflow

Sorting 2d Arrays using std::sort (column based)

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related