Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > сортировать двумерный вектор

Автор: Rockie 20.8.2006, 04:39

Можно или нельзя как-то вызвать sort чтобы отсортировать двумерный вектор? Вот пример: компилируется, то ничего не сортирует.

Код

#include<iostream>
#include<iterator>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
 const int rows = 3, cols = 3;

 vector < vector <int> > arr;
 vector < int > ar;

 for(int i=0;i<rows;i++)       // filling vector
  { for(int j=0;j<cols;j++)
      ar.push_back(j);
      arr.push_back(ar);
  }

  sort(arr.begin(),arr.end()); // no result

 cout<<'\n';
 system("pause");
 return 0;
}

Автор: nikitao 20.8.2006, 06:23

Что значит отсортеровать двумерный массив????Ведь двумерный массив - это всеволиш массив массивов. smile

Можно отсоритеровать каждый из массивовов двумерного массива по отдеьности smile

Автор: Oleg_Ci 20.8.2006, 10:18

Может так надо.

Код


for( int i=0; i<arr.size(); i++ )
   sort(arr[i].begin(),arr[i].end()); // Сортировка

Автор: Rockie 21.8.2006, 00:26

Это построчная сортировка, а мне нужно весь массив. К примеру у меня массив

Цитата

0 21 2
10 1 4
0 3 2

а нужно от меньшего к большему (от левого верхнего угла к правому нижнему)

Цитата

0 0 1
2 2 3
4 10 21

так вот можно ли это сделать с помощью встроенных функций сортировки. Ведь массивы распределяются впамяти линейно?

вот сделал эту сортировку массива массивов:

Код

   int temp = 0;

   for(int i=0;i<rows;i++)             // SORT ARRAY
     for(int j=0;j<cols;j++)            // для каждого элемента
      {
        for(int k=0;k<rows;k++)     // бежим по массиву
         for(int s=0;s<cols;s++)
          if(arr[i][j]<arr[k][s])          // сравниваем элементы
            { temp = arr[i][j];           // и если надо, меняем
              arr[i][j] = arr[k][s];   
              arr[k][s] = temp;
            }
       }

но оно мне как-то кажется коряво.. может все же можно с помощью встроенняых алгоритмов? либо как-то покороче?

Автор: MAKCim 21.8.2006, 10:37

сделай адаптор к одномерному вектору для представления матрицы
и сортируй обычным образом, либо просто используй просто вектор для представления матрицы

Автор: Oleg_Ci 21.8.2006, 15:36

Проверил, вроде массивы не распределяются впамяти линейно. Хотя я сам в векторах ещё несилен, могу ошибаться.

Код


for ( vector<int>::iterator  i = arr[0].begin();  i < arr[2].end();  i++ )
        cout<< *i << endl;

Автор: Rockie 21.8.2006, 18:01

Олег4, BCB 6, не компилится

Цитата

[C++ Error] shablon.cpp(34): E2294 Structure required on left side of . or .*
[C++ Error] shablon.cpp(34): E2294 Structure required on left side of . or .*

Цитата(MAKCim @ 21.8.2006, 10:37

)

сделай адаптор к одномерному вектору для представления матрицы

MAKCim то есть я смогу применить алгоритм sort к этому массиву массивов? а можно пример, или где почитать.

Автор: Fixin 21.8.2006, 18:06

Цитата(Rockie @ 21.8.2006, 18:01

)

или где почитать.

А что читать-то?

Цитата

0 21 2
10 1 4
0 3 2

Представляем вот так:

Цитата

0 21 2 10 1 4 0 3 2

Так понятно?

Автор: MAKCim 21.8.2006, 18:56

Цитата

то есть я смогу применить алгоритм sort к этому массиву массивов? а можно пример, или где почитать.

Это не массив массивов а просто массив
то есть если есть матрица MxN, то вектор, представляющий эту матрицу будет размера M*N
причем элемент [i][j] матрицы соответствует элементу [i*N+j] вектора

Код


10 9 8                 
7  6 5        ->      10 9 8 7 6 5 4 3 2  
4  3 2

Код


template<class Vector, class Matrix>
    void matrix2vector(const Matrix& matrix_, Vector& vector_)
{
    for (size_t i=0; i<matrix_.size(); ++i)
        for (size_t j=0; j<matrix_[i].size(); ++j) vector_.push_back(matrix_[i][j]);
}

int main()
{
    vector<vector<int> > matrix_;
    vector<int> vector_;
    matrix2vector(matrix_,vector_);
    sort(vector_.begin(),vector_.end(),greater<int>());
    vector2matrix(vector_,matrix_);
}

Автор: Rockie 22.8.2006, 10:15

Fixin, ну про саму реализацию адаптора матрица -> вектор. Теперь разобрался.
MAKCim, спасибо, то что надо! Обратное преобразование сделал так:

Код

template<class Matrix, class Vector>
    void vector2matrix(Vector& vector_, Matrix& matrix_ ,int rows, int cols)
{
    int i = 0;
    for(int j=0; j<rows; j++)
      for(int k=0; k<cols; k++)
         matrix_[j][k] = vector_[i++];
    vector_.clear();
}

Возможно, есть какой-то лучший вариант..

Автор: MAKCim 22.8.2006, 10:45

Цитата

Возможно, есть какой-то лучший вариант..

по ассимптотике
у этого в общем случае O( MN*(2+log(MN)) )
в твоем первонячальном O( M^2N^2 )

Автор: Adjusly 24.1.2023, 02:53

Модератор: Сообщение скрыто.