Problema Sortare

[•SpiderMan]

Buna. Cum as putea sa sortez cu sortul din STL dupa coloane? adica daca am avea asa:

Cod:

5412
5121
1245
7532

Sa le sorteze asa :

Cod:

1245
5121
5412
7532

[•alexandru92]

Adica, pur si simplu sa sorteze un input

Cod:

vector< int > a;
//....
sort( a.begin(), a.end() ); //le sorteaza crescator

sau

Cod:

int N, a[Nmax];
//....
sort( a, a+N );

[•SpiderMan]

Nunu, eu am o matrice, si vreau sa sorteze doar coloanele, adica uite asa :

Cod:

mat[1][1]=5;mat[1][2]=3;
mat[2][1]=3;mat[2][2]=4;

Adica numerele 53 si 34. Dupa sortarea vreau sa arate asa:

Cod:

mat[1][1]=3;mat[1][2]=4;
mat[2][1]=5;mat[2][2]=3;

Adica sa nu sorteze pe linii,doar pe coloana

[•popoiu.george]

ai putea sa faci ceva de genu :

Cod:

vector < int > a[Max];

Un truc ar fi ca atunci cand te referi la a[ i ][ j ] , tu defapt sa te referi la coloana i si linia j, adica sa "schimbi" semnificatia indexilor daca ma pot exprima asa. Si ca sa sortezi o coloana apelezi sort ca de obicei.

Cod:

sort( a[i].begin() ; a[i].end() ) ; //sortezi coloana i

[•SpiderMan]

Pai eu am ca default asa : int x[100][100]; Eu am sortat odata dupa linii, dar imi trebuie si dupa coloane.... Pentru ca mai apoi sa parcurg acea matrice si sa verific daca are vecini egali...

[•popoiu.george]

Aha...nu imi dau seama cum ai putea cu sort-ul din STL  , dar cu siguranta poti sa-ti implementezi tu o metoda care sa faca asta . 

[•SpiderMan]

Ma poti ajuta, adica gen qsort sau .... ca nu am implementat ....

[•pauldb]

Poti face asa:

Cod:

#include <algorithm>

using namespace std;

...

int cmp(int x, int y) {
   for (int i = 1; i <= N; ++i)
      if (A[i][x] != A[i][y]) return A[i][x] < A[i][y];

   return 0;
}
...
int main() {
...
for (int i = 1; i <= M; ++i) ind[i] = i;

sort(ind+1, ind+M+1, cmp);

for (int i = 1; i <= N; ++i) {
  for (int j = 1; j <= M ;++j) cout << A[i][ind[j]] << " ";
  cout << endl;
}
...
return 0;
}

Ideea e sa folosesti un vector auxiliar (ind) pentru a tine ordinea coloanelor. Functia cmp sorteaza vectorul ind dupa criteriul ales de tine. In acest fel, nu modifici nici matricea A in cazul in care doresti sa o mai folosesti in varianta initiala.

[•popoiu.george]

Ma refer ca poti sorta tu o coloana usor. Sa folosesti BubbleSort, MergeSort, etc ...

Uite un exemplu cu BubbleSort :

Cod:

void SortColumn(int column, int rows)
{
int ok;
do
   {
   ok=0;
   for( int i=1; i<rows ; ++i )
      if( a[i][column] > a[i+1][column] ) swap( a[i][column], a[i+1][column] ) , ok=1 ;
   }
while( ok );
}

[•chera_lary]

Aplica qsort.
Ex:

Cod:

int A[100][100];

int cmp(const void *a, const void *b)
{
   return ((int*)a)[nr_coloanei] - ((int*)b)[nr_coloanei];
}
. . .
int main()
{
  qsort(a, nr_linii, sizeof(a[0]), cmp);
  return 0;
}

Sper ca n-am gresit. Nu l-am verificat!

[•SpiderMan]

Deci eu vreau teoretic sa am in matricea mea vectorul gata sortat dupa ambele criterii, adica linii si coloane. Eu am dupa coloane, doar liniile mai trebuie

[•chera_lary]

Pai sortezi o data dupa coloane si apoi dupa linii.
Dupa linii poti sa faci cu sort din stl: sort(a[0], a[0]+m, cmp), unde a[0] reprezinta prima linie, m - numarul de elemente de pe linie iar cmp functia de comparare. Daca nu pui nimic la parametrul final, atunci o sa sorteze crescator.

[•SpiderMan]

Asta am facut, doar mai trebuie sa sortez dupa coloane.
[LE] Nu merge qsort-ul tau ...
[LE] Merge, dar am o intrebare totusi: cum fac daca numerele au 2 indici in comun, gen 123 si 124 ?

[•chera_lary]

Terbuie sa iti alegi un criteriu de comparatie. Depinde cum vrei sa sortezi. Poti avea 128 si 119 si in acest caz conteaza coloana dupa care sortezi.