infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Simoiu Robert din Februarie 25, 2010, 08:50:49



Titlul: Problema Sortare
Scris de: Simoiu Robert din Februarie 25, 2010, 08:50:49
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


Titlul: Răspuns: Problema Sortare
Scris de: alexandru din Februarie 25, 2010, 09:32:03
Adica, pur si simplu sa sorteze un input :-s
Cod:
vector< int > a;
//....
sort( a.begin(), a.end() ); //le sorteaza crescator
sau
Cod:
int N, a[Nmax];
//....
sort( a, a+N );


Titlul: Răspuns: Problema Sortare
Scris de: Simoiu Robert din Februarie 25, 2010, 09:35:25
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


Titlul: Răspuns: Problema Sortare
Scris de: George Popoiu din Februarie 25, 2010, 10:34:30
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


Titlul: Răspuns: Problema Sortare
Scris de: Simoiu Robert din Februarie 25, 2010, 10:38:01
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...


Titlul: Răspuns: Problema Sortare
Scris de: George Popoiu din Februarie 25, 2010, 10:41:14
Aha...nu imi dau seama cum ai putea cu sort-ul din STL  :-k , dar cu siguranta poti sa-ti implementezi tu o metoda care sa faca asta .  :ok:


Titlul: Răspuns: Problema Sortare
Scris de: Simoiu Robert din Februarie 25, 2010, 10:41:38
Ma poti ajuta, adica gen qsort sau .... ca nu am implementat ....


Titlul: Răspuns: Problema Sortare
Scris de: Paul-Dan Baltescu din Februarie 25, 2010, 10:57:04
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.


Titlul: Răspuns: Problema Sortare
Scris de: George Popoiu din Februarie 25, 2010, 10:59:23
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 );
}


Titlul: Răspuns: Problema Sortare
Scris de: CHERA Laurentiu din Februarie 25, 2010, 14:39:40
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!


Titlul: Răspuns: Problema Sortare
Scris de: Simoiu Robert din Februarie 25, 2010, 16:45:19
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 :D


Titlul: Răspuns: Problema Sortare
Scris de: CHERA Laurentiu din Februarie 25, 2010, 18:04:34
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.


Titlul: Răspuns: Problema Sortare
Scris de: Simoiu Robert din Februarie 25, 2010, 18:10:43
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 ?


Titlul: Răspuns: Problema Sortare
Scris de: CHERA Laurentiu din Februarie 25, 2010, 19:46:00
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.