Una primera idea seria recórrer el vector, de manera que, sempre que trobem dos elements adjacents en ordre erroni, els intercanviem. Podem anar fent això repetidament fins que el vector estigui ordenat. Aquest algorisme és conegut com Ordenació per Bombolla, o Bubblesort
Ordenació per Bombolla - Bubblesort
void bubblesort(vector<int>& v) {
int n=v.size();
bool intercanviat=true;
for (int i=0;i<n-1 and intercanviat;++i) {
intercanviat=false;
for (int j=0;j<n-i-1;++j) {
if (v[j]>v[j+1]) {
swap(v[j],v[j+1]);
intercanviat=true;
}
}
}
}
És a dir, farem n-1 passades pel vector. A cada passada arribarem fins a n-i-1. Això és perquè a la primera passada, per com està fet l'algorisme, el número més gran acabarà l'últim. A la segona, el segon més gran acabarà el penúltim.
Afegim una variable booleana que es diu intercanviat, que la posem a true si hem fet un intercanvi. Això és perquè si en una passada sencera no fem cap intercanvi, vol dir que ja està ordenat, i ens podem aturar aquí.
Es diu ordenació per bombolla, perquè hi ha una mena de bombolla que es va desplaçant, que és la que senyalitza quines dos posicions comparem. És a dir, donat un vector mal ordenat com el següent:
10 4 5 1 7 8 6 9 2 3
Si fem una execució pas a pas del bucle intern, quedaria
(10 4) 5 1 7 8 6 9 2 3
4 (10 5) 1 7 8 6 9 2 3
4 5 (10 1) 7 8 6 9 2 3
4 5 1 (10 7) 8 6 9 2 3
4 5 1 7 (10 8) 6 9 2 3
4 5 1 7 8 (10 6) 9 2 3
4 5 1 7 8 6 (10 9) 2 3
4 5 1 7 8 6 9 (10 2) 3
4 5 1 7 8 6 9 2 (10 3)
4 5 1 7 8 6 9 2 3 10
Això comporta un problema, conegut com "la llebre i la tortuga". Què passa quan hi ha un número gran al principi? El 10 estava al principi, i en un moment ja està al final. La llebre. Què passa quan hi ha un número petit al final? (el 2, o el 3). S'han mogut una sola posició. Són la tortuga. Per això neix una petita variació
Cocktail shacker:
Aquest algorisme el que fa és, enlloc de recórrer el vector sempre en el mateix sentit, va canviant. La gràcia és que les tortugues es converteixen en llebres, i les llebres en tortugues. Seguint des del vector d'abans:
4 5 1 7 8 6 9 2 (3 10)
4 5 1 7 8 6 9 (2 3) 10
4 5 1 7 8 6 (9 2) 3 10
4 5 1 7 8 (6 2) 9 3 10
4 5 1 7 (8 2) 6 9 3 10
4 5 1 (7 2) 8 6 9 3 10
4 5 (1 2) 7 8 6 9 3 10
4 (5 1) 2 7 8 6 9 3 10
(4 1) 5 2 7 8 6 9 3 10
1 4 5 2 7 8 6 9 3 10
Com podem veure, el 2 s'ha desplaçat des de la posició 7 a la posició 4, bastant més del que ho hauria fet amb un bubblesort normal. No obstant, aquest canvi no modifica el cost de l'algorisme
Anàlisi del cost del Bubblesort:
Analitzarem el cost en el cas pitjor. Aquest cas pitjor és quan haguem de fer totes les iteracions del bucle.
Això fa que haguem de fer (n-1)+(n-2)+...+1 iteracions del bucle interior. Com que el bucle interior té cost constant, el cost serà Θ((n-1)+(n-2)+...+1), que és Θ(n^2)
Ordenació per selecció (Selection Sort):
Enlloc d'anar intercanviant de manera que l'element més gran es vagi desplaçant cap a la dreta, per què no buscar l'element més gran (o el més petit), i posar-lo? Aleshores el segon, el tercer, fins que arribem al final. Per exemple, donat el següent vector, i ordenant de manera que busquem el menor
10 4 5 1 7 8 6 9 2 3
El menor és l'1. El posem a davant de tot (fem un swap amb el primer element)
1 4 5 10 7 8 6 9 2 3
El següent és el 2.
1 2 5 10 7 8 6 9 4 3
I seguim
1 2 3 10 7 8 6 9 4 5
1 2 3 4 7 8 6 9 10 5
1 2 3 4 5 8 6 9 10 7
1 2 3 4 5 6 8 9 10 7
1 2 3 4 5 6 7 9 10 8
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10
I ja està ordenat.
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10
A programar
Per programar, com que la versió que us donen a PRO1 és començant pel final, i posant màxims, jo també ho faré així. També té avantatges, bàsicament ens facilita la vida.
int pos_maxim(const vector<int> v, int d) {
int pos=0;
for (int i=1;i<=d;++i) {
if (v[i]>v[pos]) pos=i;
}
return pos;
}
void ordena(vector<int>& v, int d) {
if (d>0) {
int max=pos_maxim(v,d);
swap(v[max],v[d]);
ordena(v,d-1);
}
}
L'algorisme es diu ordenació per selecció perquè per cada posició, seleccionem quin va allà, i el posem. Senzill. Si fem l'execució pas a pas de l'algorisme, veiem com queda (l'espaiat gran és per separar el que ja tenim ordenat del que encara no)
10 4 5 1 7 8 6 9 2 3
3 4 5 1 7 8 6 9 2 10
3 4 5 1 7 8 6 2 9 10
3 4 5 1 7 2 6 8 9 10
3 4 5 1 6 2 7 8 9 10
3 4 5 1 2 6 7 8 9 10
3 4 2 1 5 6 7 8 9 10
3 1 2 4 5 6 7 8 9 10
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Podem mirar quin cost té. Per un vector de mida n, farem n+1 crides recursives. A cada una farem una crida a pos_maxim, que té cost Θ(d). Com que a cada crida recursiva d decreix en 1, tindrem que el cost serà
Θ(n+(n-1)+(n-2)+...+3+2+1). Si fem el càlcul, sabem que el sumatori de 1 a n és (n*(n-1))/2, cosa que ens fa tenir un cost que creix en funció de Θ(n^2). És a dir, creix quadràticament
int pos_maxim(const vector<int> v, int d) {
int pos=0;
for (int i=1;i<=d;++i) {
if (v[i]>v[pos]) pos=i;
}
return pos;
}
void ordena(vector<int>& v, int d) {
if (d>0) {
int max=pos_maxim(v,d);
swap(v[max],v[d]);
ordena(v,d-1);
}
}
10 4 5 1 7 8 6 9 2 3
3 4 5 1 7 8 6 9 2 10
3 4 5 1 7 8 6 2 9 10
3 4 5 1 7 2 6 8 9 10
3 4 5 1 6 2 7 8 9 10
3 4 5 1 2 6 7 8 9 10
3 4 2 1 5 6 7 8 9 10
3 1 2 4 5 6 7 8 9 10
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Ordenació per inserció (Insertion Sort):
Aquest algorisme és molt similar a l'ordenació per selecció, i també a l'ordenació per bombolla. El que fem és tenir 2 índexs (i, j), i anem recorrent el vector. Quan trobem una posició i tal que v[0...i ] no està ordenat, el que fem és anar fent swaps fins que quedi ordenat. Una cosa així:
void insertionsort(vector<int>& v) {
int j;
int n=v.size();
for (int i=1;i<n;++i) {
j=i;
while (j>0 and v[j]<v[j-1]) {
swap(v[j],v[j-1]);
--j;
}
}
}
Segueix tenint cost Θ(n^2), però és bastant més ràpid que els anteriors.
Ordenació per fusió (Merge Sort/Mergesort):
L'ordenació per fusió parteix d'una cosa molt simple. Si tenim un vector de mida n, el podem dividir en dos subvectors de mida n/2, ordenar-los, i fusionar-los BÉ (és a dir, fusionar-los ordenats). Perquè ens fem una idea, agafant el vector d'abans
10 4 5 1 7 8 6 9 2 3
Aquest es pot dividir en dos subvectors
(10 4 5 1 7) (8 6 9 2 3)
Si ordenem aquests dos subvectors, ens quedaria
(1 4 5 7 10) (2 3 6 8 9)
I ara els podem fusionar. Per fer això, el que farem és recórrer els dos vectors, i anar col·locant el més petit primer. Subratllo l'element que consultem en cada subvector, i a sota com queda la fusió
(1 4 5 7 10) (2 3 6 8 9)
1
(1 4 5 7 10) (2 3 6 8 9)
1 2
(1 4 5 7 10) (2 3 6 8 9)
1 2 3
(1 4 5 7 10) (2 3 6 8 9)
1 2 3 4
I ja s'entén com segueix, suposo.
A poc a poc, com coi ordenem?
Senzill. Per ordenar per fusió un vector v, de la posició l a al posició r, el que fem és
mig=(l+r)/2
ordenar(v,l,mig)
ordenar(v,mig+1,r)
fusionar(v,l,r)
Aleshores, aplicant això pas a pas
10 4 5 1 7 8 6 9 2 3
10 4 5 1 7 - 8 6 9 2 3
10 4 5 - 1 7 - 8 6 9 - 2 3
10 4 - 5 - 1 - 7 - 8 6 - 9 - 2 - 3
10 - 4 - 5 - 1 - 7 - 8 - 6 - 9 - 2 - 3
Ara ja tenim els 10 subvectors ordenats, no? Al cap i a la fi, un vector de mida 1, per definició, està ordenat. A fusionar!
4 10 - 5 - 1 - 7 - 6 8 - 9 - 2 - 3
4 5 10 - 1 7 - 6 8 9 - 2 3
1 4 5 7 10 - 2 3 6 8 9
1 2 3 4 5 6 7 8 9 10
El codi:
void merge(vector<int>& v, int l, int m, int r) {
int n=r-l+1;
vector<int> vec(n);
int i=l,j=m+1,k=0;
while (i<=m and j<=r) {
if (v[i]>v[j]) {
vec[k]=v[j];
++j;
}
else {
vec[k]=v[i];
++i;
}
++k;
}
while (i<=m) {
vec[k]=v[i];
++i;
++k;
}
while (j<=r) {
vec[k]=v[j];
++j;
++k;
}
for (int i=0;i<n;++i) v[i+l]=vec[i];
}
void mergesort(vector<int>& v, int l, int r) {
if (l<r) {
int mig=(l+r)/2;
mergesort(v,l,mig);
mergesort(v,mig+1,r);
merge(v,l,mig,r);
}
}
Merge el que fa és fusionar els dos vectors, en temps Θ(n), sent n la suma de les mides dels subvectors. Farem Θ(n) crides a aquesta funció (si ens fixem, fem Θ(2^log2(n)) crides, que dóna Θ(n)). En una de les crides, la mida dels subvectors serà n. En dues serà n/2. En quatre serà n/4. En total, farem log2(n) divisions, cosa que farà que el cost sigui Θ(n log n). Si a algú li interessa entendre per què, aquí hi ha un article
Com podem veure, el Mergesort és molt millor que el Bubble Sort, Selection Sort o Insertion Sort. Per una n=100.000, n*log2(n) dóna aproximadament 1.660.964. n^2 dóna 10.000.000.000
std::sort:
Ara ja hem après a programar algorismes per ordenar. No obstant, normalment quan necessitem ordenar un vector, no ens posem a programar-ho. La llibreria algorithm ens dóna ja una funció per ordenar un vector. Aquesta funció rep dos iteradors (no cal saber què són, a PRO1 no es fa), i ordena tot el que hi ha en el rang [primer,ultim). Aleshores, si volguéssim ordenar un vector v, del principi al final, faríem
sort(v.begin(),v.end());
I el tindríem ja ordenat.
Per ordenar en un ordre diferent
Imaginem que volem ordenar el vector decreixentment. Com ho fem?
La funció sort pot rebre dos o tres paràmetres. Quan en rep dos, és la versió anterior. Quan en rep tres, rep també el comparador. Aquest pot ser una classe (de fet, un functor) o una funció. A PRO1 en general el que fem és el següent:
bool cmp(int a, int b) {
return a>b;
}
...
sort(v.begin(),v.end(),cmp);
I ja tindríem el vector ordenat decreixentment. En essència, el que farà és que quedi ordenat de manera que cmp retorni true per tots els elements adjacents. No obstant, ordenar decreixentment és una cosa tan típica, que segur que algú ho ha programat abans, no?
Efectivament, no cal programar aquesta funció. Podem utilitzar greater<T>, una classe ja definida, que l'únic que té és una funció que retorna cert si el primer element és més gran que l'altre. Així podríem fer simplement
sort(v.begin(),v.end(),greater<int>());
Per ordenar un vector de structs:
Què passa si no tenim definits operadors de comparació? Aleshores com els ordenem? Aquí tenim dues opcions. La primera és definir l'operador de comparació (amb l'operador < ja faríem). La segona, crear una funció de comparació, i utilitzar la funció que rep 3 paràmetres. Aquesta segona opció és la que s'utilitza a PRO1. Un exemple seria:
struct Punt {
double x, y;
};
void llegir_punt(Punt& p);//Suposem que està definida
void llegir_vector(vector<Punt>& vp);//També definida
void mostrar_vector(const vector<Punt>& vp);//Ídem
bool cmp(const Punt& p1, const Punt& p2) {
if (p1.first!=p2.first) return p1.first<p2.first;
return p1.second<p2.second;
}
int main() {
int n;
cin >>n;
vector<Punt> v(n);
llegir_vector(v);
sort(v.begin(),v.end(),cmp);
mostrar_vector(v);
}
L'altra opció és definir l'operador de comparació
struct Punt {
double x, y;
bool operator<(const Punt& p2) {
if (x!=p2.x) return x<p2.x;
return y<p2.y;
}
};
Tal qual. Una struct pot tenir definides funcions i operadors propis. A partir d'aquest moment, podem comparar dos punts amb l'operador <. Podríem definir-ne d'altres, però amb aquest ja fem
Quan convé ordenar?
Imaginem que tenim un problema que ens demana "donat un vector, digues quin és l'element més gran". Podríem estar temptats de fer una cosa així:
vector<int> v(n);
llegir_vector(v);
sort(v.begin(),v.end());
cout<<v[v.size()-1]<<endl;
Però hem de posar-nos sempre en el pitjor. I el pitjor és un cas on el vector estigui molt desordenat, i sigui molt gran. Sabem que el sort té, en general, cost linearítmic (és a dir, n*log(n)). Per tant, el nostre programa tindrà aquest cost. Però, no es pot fer més eficient? Doncs sí
vector<int> v(n);
llegir_vector(v);
int maxim=v[0];
for(int i=1;i<n;++i) maxim=max(maxim,v[i]);
cout<<maxim<<endl;
Aquí ens recorrerem el vector, per buscar el màxim. Recórrer un vector té cost lineal, cosa que fa que el nostre programa el tingui. En aquest cas, era millor no ordenar
Ara imaginem que ens demanen un programa que doni la mediana. Aquí sí que necessitaríem un vector ordenat, perquè sense ordenar-lo, ens costaria massa, i segurament seria encara més ineficient.
I ara, la frikada
Ho sento, però aquest vídeo, per mi, és droga pura. I només és una petita mostra dels algorismes d'ordenació existents
void merge(vector<int>& v, int l, int m, int r) {
int n=r-l+1;
vector<int> vec(n);
int i=l,j=m+1,k=0;
while (i<=m and j<=r) {
if (v[i]>v[j]) {
vec[k]=v[j];
++j;
}
else {
vec[k]=v[i];
++i;
}
++k;
}
while (i<=m) {
vec[k]=v[i];
++i;
++k;
}
while (j<=r) {
vec[k]=v[j];
++j;
++k;
}
for (int i=0;i<n;++i) v[i+l]=vec[i];
}
void mergesort(vector<int>& v, int l, int r) {
if (l<r) {
int mig=(l+r)/2;
mergesort(v,l,mig);
mergesort(v,mig+1,r);
merge(v,l,mig,r);
}
}
Com podem veure, el Mergesort és molt millor que el Bubble Sort, Selection Sort o Insertion Sort. Per una n=100.000, n*log2(n) dóna aproximadament 1.660.964. n^2 dóna 10.000.000.000
std::sort:
Ara ja hem après a programar algorismes per ordenar. No obstant, normalment quan necessitem ordenar un vector, no ens posem a programar-ho. La llibreria algorithm ens dóna ja una funció per ordenar un vector. Aquesta funció rep dos iteradors (no cal saber què són, a PRO1 no es fa), i ordena tot el que hi ha en el rang [primer,ultim). Aleshores, si volguéssim ordenar un vector v, del principi al final, faríem
sort(v.begin(),v.end());
I el tindríem ja ordenat.
Per ordenar en un ordre diferent
Imaginem que volem ordenar el vector decreixentment. Com ho fem?
La funció sort pot rebre dos o tres paràmetres. Quan en rep dos, és la versió anterior. Quan en rep tres, rep també el comparador. Aquest pot ser una classe (de fet, un functor) o una funció. A PRO1 en general el que fem és el següent:
bool cmp(int a, int b) {
return a>b;
}
...
sort(v.begin(),v.end(),cmp);
I ja tindríem el vector ordenat decreixentment. En essència, el que farà és que quedi ordenat de manera que cmp retorni true per tots els elements adjacents. No obstant, ordenar decreixentment és una cosa tan típica, que segur que algú ho ha programat abans, no?
Efectivament, no cal programar aquesta funció. Podem utilitzar greater<T>, una classe ja definida, que l'únic que té és una funció que retorna cert si el primer element és més gran que l'altre. Així podríem fer simplement
sort(v.begin(),v.end(),greater<int>());
Per ordenar un vector de structs:
Què passa si no tenim definits operadors de comparació? Aleshores com els ordenem? Aquí tenim dues opcions. La primera és definir l'operador de comparació (amb l'operador < ja faríem). La segona, crear una funció de comparació, i utilitzar la funció que rep 3 paràmetres. Aquesta segona opció és la que s'utilitza a PRO1. Un exemple seria:
struct Punt {
double x, y;
};
void llegir_punt(Punt& p);//Suposem que està definida
void llegir_vector(vector<Punt>& vp);//També definida
void mostrar_vector(const vector<Punt>& vp);//Ídem
bool cmp(const Punt& p1, const Punt& p2) {
if (p1.first!=p2.first) return p1.first<p2.first;
return p1.second<p2.second;
}
int main() {
int n;
cin >>n;
vector<Punt> v(n);
llegir_vector(v);
sort(v.begin(),v.end(),cmp);
mostrar_vector(v);
}
L'altra opció és definir l'operador de comparació
struct Punt {
double x, y;
bool operator<(const Punt& p2) {
if (x!=p2.x) return x<p2.x;
return y<p2.y;
}
};
Tal qual. Una struct pot tenir definides funcions i operadors propis. A partir d'aquest moment, podem comparar dos punts amb l'operador <. Podríem definir-ne d'altres, però amb aquest ja fem
Quan convé ordenar?
Imaginem que tenim un problema que ens demana "donat un vector, digues quin és l'element més gran". Podríem estar temptats de fer una cosa així:
vector<int> v(n);
llegir_vector(v);
sort(v.begin(),v.end());
cout<<v[v.size()-1]<<endl;
Però hem de posar-nos sempre en el pitjor. I el pitjor és un cas on el vector estigui molt desordenat, i sigui molt gran. Sabem que el sort té, en general, cost linearítmic (és a dir, n*log(n)). Per tant, el nostre programa tindrà aquest cost. Però, no es pot fer més eficient? Doncs sí
vector<int> v(n);
llegir_vector(v);
int maxim=v[0];
for(int i=1;i<n;++i) maxim=max(maxim,v[i]);
cout<<maxim<<endl;
Aquí ens recorrerem el vector, per buscar el màxim. Recórrer un vector té cost lineal, cosa que fa que el nostre programa el tingui. En aquest cas, era millor no ordenar
Ara imaginem que ens demanen un programa que doni la mediana. Aquí sí que necessitaríem un vector ordenat, perquè sense ordenar-lo, ens costaria massa, i segurament seria encara més ineficient.
Cap comentari:
Publica un comentari a l'entrada