12. Mètodes d'ordenació
Objectius
Els objectius d'aquest mòdul són els següents:
- Tenir una idea consistent dels diferents grups d'algorismes d'ordenació en vectors.
- Valorar la complexitat dels diferents grups d'algorismes.
Introducció
En el mòdul anterior hem vist que les cerques dins de dades estructurades ordenades són força més eficients que si les dades no estan ordenades. En conjunts de dades que han de ser sotmesos freqüentment a cerques, l'estalvi de computació si es disposa de dades ordenades pot significar un important augment en el rendiment del sistema.
En aquests casos serà important generar directament les dades ordenades, és a dir, quan inserim una nova dada dins de l'estructura de dades, ja la situem en la posició que li correspon segon l'ordre establert. La dada estructurada neix i es manté sempre ordenada i les cerques sempre poden ser eficients.
Hi ha diverses situacions en què això no és possible:
- Les dades són complexes (tuples) i l'ordenament de les mateixes és diferent segons els diferents camps que sovint són base de cerques.
- Disposem ja de la col·lecció de dades però no està ordenada.
En aquests casos caldrà disposar de mecanismes d'ordenació de les dades que permetin reorganitzar-les d'una manera eficaç.
Al llarg d'aquest mòdul incidirem, sobretot, en els algorismes d'ordenació de vectors, atès que són les estructures de dades més freqüents susceptibles de mantenir un ordre i perquè es pot valorar d'una manera relativament simple la complexitat de cadascun dels algorismes.
L'exemplificació que farem dels mètodes suposarà sempre que volem aplicar un ordre ascendent, les modificacions dels algorismes per tractar l'ordre descendent són trivials.
A més, suposarem sempre que estem ordenant un vector de tuples pel valor del seu camp enter key.
Considereu la següent definició de tupla:
[Exemple 12_01]
type
tReg = record
key: integer;
{ ... }
end record
end type
typedef struct {
int key;
/* ... */
} tReg;
En alguns algorismes també serà necessari intercanviar tuples cosa que es farà amb l'ajut d'una acció swap.
[Exemple 12_02]
action swap(inout a: tReg, inout b: tReg)
var
auxiliar: tReg;
end var
auxiliar := a;
a := b;
b := auxiliar;
end action
void swap(tReg *a, tReg *b) {
tReg auxiliar:
memcpy(&auxiliar, a, sizeof(tReg));
memcpy(a, b, sizeof(tReg));
memcpy(b, &auxiliar, sizeof(tReg));
}
Classificació dels algorismes directes d'ordenació
Hi ha diversos algorismes genèrics d'ordenament en funció de l'estratègia bàsica amb què belluguen els elements dins del vector fins la localització definitiva que els toca segons l'ordre desitjat.
Tots els algorismes que mostrarem són dels nomenats directes perquè fan l'ordenació dins del mateix vector original, a diferència dels indirectes que empren un vector auxiliar per reordenar les dades i, per tant, són menys eficients pel que fa a l'ús de la memòria.
Ordenació per selecció
Els mecanismes de selecció suposen que en tot moment el vector que es vol ordenar està dividit en dos segments, una part ordenada i una altra encara per ordenar. L'algorisme és iteratiu i a cada iteració seleccionem un element de la part desordenada i el passem a l'ordenada. L'estat inicial de l'algorisme és que la part desordenada conté tots els elements i l'ordenada cap, mentre l'estat final és que la part desordenada no conté cap element i la part ordenada ja els té tots.
En un moment determinat de l'aplicació de l'algorisme l'estat del vector podria ser:
Figura: el senyal vermell indica la frontera entre la part ja ordenada i la que resta per ordenar
En llenguatge natural l'algorisme seria:
- Seleccionar de la part desordenada la tupla amb el valor de key més petit.
- Intercanviar aquesta tupla amb la primera tupla de la part desordenada.
- Repetir els passos 1 i 2 fins que només quedi una tupla a la part desordenada (que serà la de valor de key més gran).
Si es parteix del vector de valors de key [44, 55, 12, 42, 94, 18, 06, 67] l'evolució des de la situació inicial (iteració 0) fins la final seria:
Figura: Quan només queda un element a la part per ordenar, ja està ordenat tot el vector
Veiem l'algorisme codificat:
[Exemple 12_03]
const
N: integer = 8;
end const
type
tVec: vector[N] of tReg;
end type
action selectionSort(inout v: tVec, in n: integer)
var
i, j, min: integer;
end var
for i:=1 to n-1 do
min := i;
for j:=i+1 to n do
if v[j].key < v[min].key then
min := j;
end if
end for
if min ≠ i then
swap(v[i], v[min]);
end if
end for
end action
typedef tReg tVec[N];
void selectionSort(tVec v; int n) {
int i, j, min;
for (i=0; i < n-1; i++) {
min = i;
for ( j = i+1 ; j < n ; j++) {
if (v[j].key < v[min].key) {
min := j;
}
}
if (min != i) {
swap(&v[i], &v[min]);
}
}
}
Per tal d’analitzar la complexitat tractarem per separat les comparacions entre les claus i els moviments dels registres
- Es realitzen n - 1 passades.
- En cada passada el nombre de comparacions entre les claus decreix: n-1 la primera passada, n-2 la segona, ..., 2, 1. En total se'n fan n*(n-1)/2.
- El nombre d’intercanvis no és constant, depèn de la situació inicial del vector. En el millor dels casos seria 0 (el vector ja estava ordenat). En el pitjor dels casos n - 1 (a cada iteració hem de fer un intercanvi).
La quantitat de moviments (intercanvis) és lineal respecte la mida del vector. Per contra, la quantitat de comparacions és d’ordre quadràtic. La complexitat serà, doncs O(n2).
Ordenació per inserció
El mètode de ordenació per inserció suposa, com l’anterior que tenim el conjunt de registres dividit en dues subseqüències, una part esquerra ja ordenada i l’altre amb els registres que queden per ordenar:
[k0, k1, ... ,ki-1] [ki, ki+1, ..., kn-1]
El procés d'ordenació per inserció es fonamenta en inserir a la subseqüència de l’esquerra, la primera tupla de la subseqüència de la dreta. Inicialment es considera que el primer element forma la primera subseqüència ordenada.
Figura: suposem el primer element ordenat i l'ordenació finalitza quan hem incorporat el darrer element a la part esquerra
Per tal d’inserir una tupla a la posició que li correspon temporalment cal preveure que han de realitzar-se desplaçaments d’una posició cap a la dreta d’alguns elements que formaven part de la subseqüència ordenada (els que tenen un valor de clau superior a l'element que estem inserint). Pel cas d’haver d’inserir l’element v[i], podria descriure’s de la següent forma:
- Comparar v[i].key amb v[j].key (0 ≤ j ≤ i-1), començant per j = i-1.
- Si v[i].key < v[j].key, s’ha de moure v[j].key a la posició j + 1.
- Es repeteixen els passos 1 i 2 fins que v[i].key > v[j].key o bé arribem a la primera posició.
L'algorisme codificat seria:
[Exemple 12_04]
const
N: integer = 8;
end const
type
tVec: vector[N] of tReg;
end type
action insertionSort(inout v: tVec, in n: integer)
var
i, j: integer;
z: tReg;
end var
for i:=1 to n do
z := v[i];
j := i - 1;
while (j >= 1 and z.key < v[j].key) do
v[j+1] := v[j];
j := j-1;
end while
v[j+1] := z;
end for
end action
typedef tReg tVec[N];
void insertionSort (tVec v; int n) {
int i,j;
tReg z;
for (i = 1; i < n; i++) {
memcpy(&z, &v[i], sizeof(tReg));
j = i - 1;
while (j >= 0 && z.key < v[j].key) {
memcpy(&v[j+1], &v[j], sizeof(tReg));
j--;
}
memcpy(&v[j+1], &z, sizeof(tReg));
}
}
Aquest algorisme fa una sola passada sobre tota la seqüència. La quantitat de comparacions varia segons l’estat inicial del vector. En el millor dels casos (vector ordenat) fa n-1 comparacions. En el pitjor (vector ordenat en ordre invers) en fa (n2+n)/2–1.
També s’ha de considerar el nombre de moviment de tuples i de claus (se suposa el mateix cost per ambdós tipus de moviments). En el millor dels casos es fa una còpia de clau i dues de tupla per cada comparació 3(n-1). La situació més desfavorable comporta (n2 + 5n – 6)/2 trasllats d’informació. De totes maneres, la complexitat de l’algorisme és O(n2).
Ordenació per intercanvi
Existeix diversos algorismes basats en aquest mètode. El més simple és l'algorisme de la bombolla que també suposa que el vector està dividit en dues subseqüències, a l'esquerra la dels elements menors i encara no ordenats i a la dreta la dels elements majors ja ordenats. Cada passada es compara cadascun dels elements de la part desordenada amb el seu consecutiu i, si estan fora d'ordre, se'ls intercanvia. D'aquesta manera cada passada posa l'element més gran al final de la part desordenada del vector.
Figura: s'il·lustra només la primera passada. Es va comparant cada element amb el seu consecutiu i s'intercanvien si cal. Al final de la passada ha anat al final l'element de clau més gran i, per tant, augmenta en una posició la part ordenada.
La codificació seria:
[Exemple 12_05]
const
N: integer = 8;
end const
type
tVec: vector[N] of tReg;
end type
action bubbleSort(inout v: tVec, in n: integer)
var
i, j: integer;
end var
for i:=1 to n-1 do
for j:=1 to n-i do
if (v[j].key > v[j+1].key) then
swap(v[j],v[j+1]);
end if
end for
end for
end action
int i, j;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (v[j].key > v[j+1].key) {
swap(&v[j], &v[j+1], sizeof(tReg));
}
}
}
}
L’anàlisi de la complexitat és més simple. Es realitzen n-1 passades i en cada passada n - i comparacions de claus (1 ≤ i ≤ n-1). En total (n-1)n/2 comparacions.
Cada intercanvi comporta tres moviments. La quantitat de moviments serà 0 en el millor dels casos i com a màxim serà 3(n2–n)/2 si la seqüència està ordenada inversament. La complexitat és, en tot cas O(n2).
Pot millorar-se l’algorisme si, en detectar que ja està classificada la seqüència es para de fer comparacions. Per això cal tenir constància de quan es dóna aquesta situació. I no és complicat. Si en realitzar una passada no s’ha hagut de fer cap intercanvi, el vector ja té el seu ordre definitiu.
Per fer-ho, n’hi ha prou en afegir una condició sorted. A l’inici de cada passada se suposarà que el vector està ordenat (sorted es posa a true) i, en cas de que es faci un intercanvi, es posa la condició a 0 (false).
[Exemple 12_06]
const
N: integer = 8;
end const
type
tVec: vector[N] of tReg;
end type
action improvedBubbleSort (inout v: tVec, in n: integer)
var
i, j: integer;
sorted: boolean;
end var
sorted := false;
i := 1;
while i < n and not sorted do
sorted := true;
for j:=1 to n-i do
if v[j].key > v[j+1].key then
swap(v[j],v[j+1]);
sorted := false;
end if
end for
i := i + 1;
end while
end action
typedef tReg tVec[N];
typedef enum {FALSE, TRUE} boolean;
void improvedBubbleSort(tVec v; int n) {
int i, j;
boolean sorted;
sorted = FALSE;
for(i = 0; i < n-1 && !sorted; i++) {
sorted = TRUE;
for (j = 0; j < n - i; j++) {
if (v[j].clau > v[j+1].clau) {
swap(&v[j], &v[j+1], sizeof(tReg));
sorted = FALSE;
}
}
}
}
Algorisme QuickSort
El mètode QuickSort (ordenació ràpida) és l’algorisme d'ordenació més eficient dels coneguts fins ara.
El mecanisme és recursiu: es tracta de seleccionar un element k del vector (la clau del qual nomenarem pivot) i col·locar-lo al seu lloc definitiu de manera que tots els elements que quedin a la seva esquerra tinguin un valor de clau inferior al pivot i els que quedin a la seva dreta tinguin un valor superior. D’aquesta manera s’ha partit la seqüència inicial aleatòria en dues subseqüències també aleatòries però ordenades entre elles (qualsevol element de la seqüència esquerra és inferior a qualsevol de la dreta).
Per exemple, si es parteix del vector de valors de key [44, 55, 12, 42, 94, 18, 06, 67] i es tria com element de comparació, el primer element del vector. La evolució en la primera iteració seria:
Figura: el primer element té com valor key el 44 (pivot). Després de la primera partició del vector el 44 ha quedat al seu lloc precedir pels que tenen valors de key inferiors i seguit dels que tenen valors de key superiors.
Un cop partit el vector es torna a cridar l’algorisme perquè parteixi la part esquerra i, després la part dreta. Els vectors seran cada vegada més petits i, quan arribin a mida 1, el resultat serà haver ordenat totalment el vector inicial.
Figura: evolució completa de l'ordenació amb quickSort. Denominem pivot la clau que serveix per a fer cadascuna de les particions (l'indiquem amb les fletxes). Es marca en fons blanc el segment actiu del vector (que s'està particionant).
Veiem l'algorisme codificat:
[Exemple 12_07]
const
N: integer = 8;
end const
type
tVec: vector[N] of tReg;
end type
action quickSort(inout v: tVec, in begin: integer, in end: integer)
var
i, j, pivot: integer;
end var
if begin < end then
i := begin + 1;
j := end;
pivot := v[begin].key;
while i < j do
while (i < end) and (v[i].key <= pivot) do
i := i+1;
end while
while v[j].key > pivot do
j := j-1;
end while
if i < j then
swap(v[i], v[j]);
end if
end while
swap(v[begin], v[j]);
quickSort(v, begin, j-1);
quickSort(v, j+1, end);
end if
end action
typedef tReg tVec[N];
void quickSort(tVec v; int begin; int end) {
int i, j, pivot;
if (begin < end) {
i = begin + 1;
j = end;
pivot = v[begin].key; // es copia la clau a pivot
while (i < j) {
while (i < end && v[i].key <= pivot) {
i++;
}
while (v[j].key > pivot) {
j--;
}
if (i < j) {
swap(&v[i], &v[j]);
}
}
swap(&v[begin], &v[j]);
quickSort(v, begin, j-1);
quickSort(v, j+1, end);
}
}
La part crítica de l'algorisme és la selecció del pivot. Una bona selecció seria la que parteix el vector exactament per la meitat (estalviarà passades i minimitzarà la complexitat).
La crida inicial a l'acció seria en pseudocodi quickSort( v, 1, N ) o bé en C quickSort( v, 0, N-1 ) on s’indica que s’ha d'ordenar el vector de la primera a la darrera posició.
Es pot comprovar que cada partició comporta fer un recorregut de la taula completa (N elements). En acabar s’envia un altre cop a partir les dues subseqüències, que seran recorregudes i, entre les dues tenen N elements.
Com que cada cop la partició divideix el vector en dos, és fàcil veure que la quantitat de particions serà proporcional al log2(N). La complexitat de l’algorisme és doncs O(n log n).
Comparació d'algorismes
La velocitat d’un algorisme o un altre depèn de molts factors, entre ells, la disposició inicial més o menys favorable (aquesta condició varia segons els algorismes) i la quantitat d’elements a ordenar.
S’ha pogut comprovar que en algorítmica la simplicitat és generalment contrària a l’eficiència. Així, podem trobar-nos amb què algorismes molt eficients, per ser complicats, comporten més temps de còmput que algorismes més simples quan s’apliquen a classificacions de pocs elements. En canvi, mostren la seva potència quna la quantitat d'elements a ordenar creix.
Una anàlisi de l’eficiència global haurà de considerar com evoluciona aquest paràmetre a mida que fem créixer les dades.
Conclusions
Gaudir de col·leccions de dades ordenades permet grans avantatges en els processos de cerca, no obstant tant el procés d'ordenació com el de manteniment de dades ordenades (insercions de nous elements o eliminació d'elements) té un cost important en unitats de còmput que creix ràpidament amb el volum de les dades.
La millor estratègia serà aquella que valori el balanç entre la quantitat de cerques i la quantitat de modificacions que es pot fer a les dades:
- Si la dada estructurada amb què es treballa és molt volàtil (contínuament estem fent modificacions) i poques vegades es fan cerques, potser no és convenient esmerçar-hi esforços en ordenar i mantenir ordenades les dades.
- Si es tracta de conjunts de dades que sofreixen moltes consultes i rarament es modifiquen, l'esforç de còmput per fer l'ordenació i per mantenir les dades ordenades quan es fa alguna inserció o eliminació significarà una petita inversió comparat amb el temps estalviat en el conjunt de les cerques.
Resum
En aquest mòdul hem vist diversos algorismes generals d'ordenació de tuples disposades en vectors, i seria extensiu directament a taules. Amb petites modificacions els codis d'exemple es poden adaptar a fer ordenacions d'elements simples (ordenar números, caràcters) i també a fer ordenacions descendents.
Les grans famílies descrites corresponen a algorismes:
- De selecció: on donada una posició del vector, seleccionem la dada que s'ha de posar d'entre les que no estan ordenades.
- D'inserció: on donat un element fora d'ordre, el posem en la seva posició relativa entre els elements que ja tenim ordenats.
- D'intercanvi: on anem comparant cada element amb el seu veí per deixar-los en l'ordre relatiu desitjat.
- Quick Sort: on l'ordenació és el resultat final del fet de fer particions recursives de les dades segons el seu valor.
També hem vist un petit análisi de com calcular la complexitat de cadascun dels algorismes i com, a mida que el volum de dades a ordenar és més gran, és crítica la selecció de l'algorisme a emprar.