使用std::sort（基于列）对2d数组进行排序

Question

我正在进行一项测试，展示按列对2D数组排序的好处，方法是将数据拆分到单独的数组中进行排序，然后将其复制回列中。我想要每次运行时使用std :: sort作为排序算法。在执行复制操作之前，我正试图先在原地运行循环。以下是输入/输出的示例。

#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;
}

感谢您的帮助。

- Kevin Melkowski

---

你想单独对每个数组进行排序，还是将2D数组视为一个大数组？ - Caesar

如果给定向量，我该如何做？ - Kevin Melkowski

抱歉，已撤回。 - RichardPlunkett

也许你应该看一下如何旋转你那里的矩阵，对每行进行排序，然后再旋转回来。 - Aesthete

标准排序使用迭代器。您可以定义自己的迭代器，以步长为行长度。 - RichardPlunkett

Answer 1

您可以编写自己的迭代器，例如：

#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);
}

现在，我们来测试一下：

#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;
}

- Jarod42

---

终于找到了一个依赖于 Boost 的适配器，太棒了。 - MORTAL

Answer 2

你可以将每列复制到一个临时数组中，对其进行排序，然后放回输出数组。

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
}

- HaseebR7

---

计划稍后进行比较，基准是内联排序。 - Kevin Melkowski

Answer 3

我最终放弃了并决定写自己的版本进行比较。我想我会将所有排序算法的版本都保持类似于这个。

@RichardPlunkett 我尝试创建自己的比较函数，但担心它会交换整行。

#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;
}

- Kevin Melkowski