Algoritmi de Sortare

1 - INTRODUCERE

Ordonaț ia sau clasificarea datelor constă în aranjarea acestora conform

cu o anumită valoare sau caracteristică. De exemplu, fiecare element dintr-un carnet de adrese are
un câmp nume, un câmp adresă ș i un câmp număr de telefon. De obicei, ...
Datele din agendă sunt organizate în ordine de la A la Z. La fel
o listă sau un vector de date se spune:
care este ordonat în mod ascendent, dacă X [i] <= X [i + 1]
y, pe de altă parte, se spune:
care este ordonat în mod descrescător dacă X[i] >= X[i + 1].

Procesul de ordonare este unul dintre cele mai interesante mecanisme atunci când ajunge la
momentul de a arăta că există multiple soluț ii pentru aceeaș i problemă, ș i că fiecare
soluț ia algoritmică are propriile sale avantaje ș i dezavantaje.

Algoritmii de sortare ne permit, după cum spune ș i numele, să sortăm. În acest caz,
ne vor ajuta să ordonăm vectori sau matrice cu valori atribuite aleatoriu. Ne
ne vom concentra pe cele mai populare metode, analizând numărul de comparaț ii pe care le
suceden, timpul care durează ș i revizuind codul, scris în Java, fiecărui algoritm.

În această unitate vom cunoaș te mai în profunzime fiecare metodă de sortare, de la cea mai
simplu până la cel mai complex. Vor fi efectuate comparaț ii în timpul execuț iei, pre-
cerinț ele fiecărui algoritm, funcț ionalitate, domeniu de aplicare, etc.

Cum ar fi, de exemplu, următoarele metode:

ORDONARE BUBURLĂ (BUBBLE SORT)

SORTARE DIRECTĂ (SORTARE SELECȚ IE)
INSERARE DIRECTĂ (SORTARE PRIN INSERARE)
SORTARE SHELL
SORTARE PE MENSOANE
QUICK SORT

1.1 - Ordine Internă

Metodele de sortare internă lucrează în memoria principală ș i ale lor
implementările sunt foarte variate, astfel încât alegerea algoritmului potrivit
trebuie realizat cu criterii de eficienț ă (timp ș i execuț ie) ș i în funcț ie de memorie
disponibile. Vom împărț i metodele în două grupuri mari:
Directoare (burbuja, selecț ie ș i inserț ie).
Logaritmice (Shell sort, Merge sort, Heap sort, Quick sort, Radix).

În cazul listelor mici, metodele directe funcț ionează în mod

relativ eficiente, deoarece codificarea algoritmului corespunzător nu este
compleja. Utilizarea sa este foarte frecventă. Cu toate acestea, în aranjamente mari, ordonările
rezultatele directe sunt ineficiente ș i va fi necesar un metodă logaritmică pentru soluț ia sa.
2–TIPURI DE ALGORITMI

O modalitate de a măsura eficienț a unui algoritm de acest tip este de a verifica numărul de
comparatii intre valori cheie, in plus fata de numarul de miscari care trebuie sa se efectueze
realiza între elemente (schimburi) ale listei.

Metodele de sortare care lucrează cu structuri de date rezidente în memorie

principal se denominan Ordine Interne, în timp ce implementările care
utilizarea structurilor de date rezidente în fiș iere se cunoaș te sub numele de Sortări
externi.

Pentru a putea ordona o cantitate determinată de numere stocate într-un vector sau
matricea, există diferite metode (algoritmi) cu caracteristici ș i complexitate diferite.

Există de la metoda cea mai simplă, cum ar fi Bubblesort (sau Metoda Burbuja), care sunt
simples iteraciones, hasta elQuicksort(Método Rápido), que al estar optimizado usando
recursiune, timpul său de executie este mai scurt si este mai eficient.

2.1–METODE ITERATIVE

Aceste metode sunt simple de înț eles ș i de programat, deoarece sunt iterative, cicluri simple.
ș i sentinț e care fac ca vectorul să poată fi ordonat.

În cadrul algoritmilor iterativi găsim:

Bula
–Inserț ie
Selecț ie
Shellsort

2.2 - METODE RECURSIVE

Aceste metode sunt ș i mai complexe, necesită mai multă atenț ie ș i cunoș tinț e pentru
să fie înț eleș i. Sunt rapizi ș i eficienț i, folosesc în general tehnica Împarte ș i cucereș te,
ce constă în a împărț i o problemă mare în mai multe mai mici pentru a fi mai uș or
rezolvarea lor. Prin apeluri recursive la ei înș iș i, este posibil ca timpul de
executarea ș i ordonarea să fie mai optimă.

În cadrul algoritmilor recursivi găsim:

–Ordenare prin amestecuri (merge)
–Sortare Rapidă (quick)

3–METODO DE LA BURBUJA

Algoritmul sortării prin bule este una dintre cele mai cunoscute metode de sortare ș i una dintre
primii care învaț ă programatorii. Metoda bulei este una dintre cele mai
sencile ș i intuitive, este atât de uș or ca să compari toate elementele unei liste între ele
toate, si se îndeplineș te că unul este mai mare sau mai mic decât altul, atunci le schimbă poziț ia.

Se bazează pe sortarea prin schimbare ș i îș i primeș te numele de la asemănarea cu bulele.

de un depozit de apă unde fiecare bula îș i caută propriul nivel.

Paș ii de efectuat în cazul unei sortări ascendente (în cazul sortării

descenderte doar ar trebui să schimbi semnul de comparaț ie) sunt:
 1. Compară primul ș i al doilea element, schimbă-le dacă primul este mai mare decât
al doilea; apoi se compară primul cu al treilea, schimbându-se în caz
necesar, iar procesul se repetă până la ultimul element. În acest mod, după
în prima iteraț ie, caseta întâi va păstra cel mai mic element din acea
iterare.

2. Se repetă pasul anterior, dar acum cu al doilea ș i al treilea, în caz de a fi

necesare se schimbă, ș i astfel până la a ajunge să compare al doilea cu ultimul.

Consistă în compararea perechilor de elemente adiacente într-un array ș i dacă sunt dezordonate
intercambiarlos până când sunt toate ordonate.

Ș i A este array-ul de ordonat, se efectuează [Link]-1 treceri. Dacă variabila i este cea care numără
numărul de treceri, în fiecare trecere i se verifică elementele adiacente din
prima dată până la [Link]-i-1 deoarece restul până la sfârș itul array-ului este deja sortat. Dacă
elementele adiacente sunt dezordonate se schimbă.

Exemplu: Să ne imaginăm că avem următoarele valori: 50 26 7 9 15 27

Ceea ce ar face metoda bubble sort ar fi să înceapă să parcurgă valorile din stânga.
la dreapta, începând cu 50. O compară cu 26, cu 7, cu 9, cu 15 ș i cu
la 27, ș i este mai mare sau mai mic (în funcț ie de faptul dacă ordinea este ascendentă sau descendentă) se
intercambian de poziț ie.

Apoi continuă cu următorul, cu 26, ș i îl compară cu toate elementele din listă,

aș teptând să văd dacă se respectă sau nu aceeaș i condiț ie ca ș i cu primul element. Astfel,
succesiv, până la ultimul element al listei.

Exemplu de execuț ie:

Deja sunt ordonate, dar cele două bucle for vor continua să se execute până la final. Metoda
de ordonare a metodei buburuză în Java pentru a ordona un vector sau un tablou A este:
public static void Burbuja( int [ ] A ){
int temp;
pentru(int i=0;i<[Link]-1;i++)
pentru(int j=0;j<[Link]-i-1;j++)
dacă(A[ j ] > A[ j+1 ]){
temp=A[ j ];
A[ j ]=A[ j+1 ];
A[ j+1 ]=temp;
}
}
Observă cum se declară un vector A de tip întreg care va conț ine o cantitate n care
va fi [Link]-1 de casete, declarăm de asemenea variabilele i ș i j care ne vor ajuta să
ne deplasăm între casetă ș i casetă pentru a face comparaț iile. Ș i în cele din urmă variabila
temp, va stoca temporar valoarea de schimb între casetele care au nevoie.

Timpul de execuț ie al algoritmului de sortare prin burbubble este de ordinul O(n2)

3.1–BURBUJĂ SIMPLĂ

Aș a cum am descris în secț iunea anterioară, bula cea mai simplă dintre toate este cea care
compara pe toț i cu toț i, generând comparaț ii suplimentare, de exemplu, nu are sens
să se compare cu sinele său sau să se compare cu valorile anterioare lui, deoarece
presupus că, deja sunt ordonate.

Este unul dintre cele mai proaste algoritmi de sortare în ceea ce priveș te timpul de execuț ie, doar
este recomandat pentru a ordona liste cu un număr mic de elemente.

3.2 - BURBUJA ÎMBUNĂTĂȚITĂ

O nouă versiune a metodei buclei ar fi limitarea numărului de comparaț ii,

am spus că este inutil să se compare cu ea însăș i. Dacă avem o listă de 10.000
elemente, deci sunt 10.000 de comparaț ii care sunt în plus.

Imaginăm că avem 1.000.000 de elemente. Metoda ar fi mult mai optimă cu

„n” comparaț ii mai puț in (n = numărul total de elemente).

Această versiune îmbunătăț ită a algoritmului respectiv integrează o variabilă care funcț ionează ca declanș ator.
(steagul) care permite detectarea momentului în care nu mai au loc schimburi
deș i îmbunătăț irea sa nu este de obicei atât de importantă, deoarece algoritmul continuă să se comporte ca
o sortare pătratică O(n)2).

public static void burbuja2(int[] v, int n) {

bool sw = adevărat;
int temp;
int li = 0;
fă {
li++;
sw = true;
pentru (int i = 0; i < n - li; i++) {
dacă ( v[i] > v[i+1] ) { // compară valorile
// schimbă datele
temp = v[i];
v[i] = v[i+1];
v[i+1] = temp;
sw = false;
}
}
} în timp ce(!sw);
}
3.3 - BURBUJA OPTIMIZATĂ

Si schimbării anterioare (cea a bulboanei îmbunătăț ite) îi adăugăm o altă schimbare, faptul că
elementele care sunt în spatele celui care este comparat, sunt deja ordonate,
comparatiile ar fi si mai putine si metoda ar fi si mai eficienta.

Dacă avem o listă de 10 elemente ș i analizăm al cincilea element, ce sens

trebuie ca al cincilea să fie comparat cu primul, al doilea sau al treilea, dacă, presupunând,
sunt deja ordonate? Atunci optimizăm ș i mai mult algoritmul, rămânând la noi
versiunea finală a algoritmului optimizat în următorul mod:

Public static void Bubblesort( int matriz[ ] ){

int temp;

pentru (int i = 0; i < [Link]-1; i++) {

pentru (int j = i + 1; j < [Link]; j++) {
dacă (matriz[ i ] > matriz[ j ]) {
temp = matriz[ i ];
matrice[ i ] = matrice[ j ];
matriz[ j ] = temp;
}
}
}
}

Exemplu: Se dispune de un vector de 6 poziț ii unde se începe o listă de numere

{ 7, 2, 8, 3, 5, 1 }, la cual será ordenada en forma ascendente { 1, 2, 3, 5, 7, 8 }, El
procesul ar fi după cum urmează:
4–INSERARE Ș I SELECȚIE

4.1. - Metodă de Selecț ie

Ideea de bază este de a găsi cel mai mic (mare) element, în ordine ascendentă a listei, și
intercambiați-l cu elementul care ocupă prima poziție în listă, apoi se caută
următorul element mai mic și se transferă în a doua poziție. Procesul se repetă până când
ultimul element a fost transferat în poziția sa corectă.

Algoritmul de sortare depinde la rândul său de algoritmul necesar pentru a localiza componenta
mai mare (mai mic) decât un array sau vector. Este un proces foarte similar cu metoda burbuiei, dar făcând
mai eficientă căutarea și evitând schimburile inutile.

Să luăm aceeași aranjare din exemplul anterior { 7, 2, 8, 3, 5, 1 }. Procesul ar fi următorul

manera

Acest metod de sortare a vectorilor constă în repetarea următoarelor paș i:

Se caută cel mai mic element din vector ș i este plasat în prima poziț ie.
Între cei rămaș i, se caută cel mai mic element ș i se plasează în a doua poziț ie.
Printre cei rămaș i se caută cel mai mic element ș i se aș ează în a treia poziț ie.
Acest proces se repetă până se plasează ultimul element.

În mod grafic, procesul ar fi următorul:

Metoda de sortare prin selecț ie în java pentru a ordona un vector sau array de întregi A
este este următorul:
//metoda java de sortare prin selecț ie
public static void seleccion(int A[]) {
int i, j, menor, pos, temp;
pentru (i = 0; i < [Link] - 1; i++) { // considerăm ca fiind cel mai mic primul
menor = A[i]; // de los elementos que quedan por ordenar
pos = i; // y păstrăm poziț ia sa
for (j = i + 1; j < [Link]; j++){ // buscamos en el resto
dacă (A[j] < menor) { // din array un element
menor = A[j]; // mai mic decât cel actual
pos = j;
}
}
dacă (pos != i){ // dacă există unul mai mic, se schimbă
temp = A[i];
A[i] = A[pos];
A[pos] = temp;
}
}
}

O altă metodă:
Public static void seleccion(int[] v) {
/* sortarea prin selecț ie */
int k=0;
pentru (int i = 0; i < [Link] - 1; i++) {
k = i;
pentru (int j = i+1; j < [Link]; j++)
dacă ( v[k] > v[j] ) k = j;
int temp = v[i];
v[i] = v[k];
v[k] = temp;
}
}

Timpul de execuț ie al algoritmului de sortare prin selecț ie este de ordinul O(n2)

4.2. - Metoda de Inserț ie

Această metodă este cunoscută ș i sub numele de "metoda jucătorului de cărț i", datorită asemănării cu
forma de clasifica cărț ile dintr-un pachet, introducând fiecare carte în locul potrivit.

Algoritmul ordonează primele două elemente ale listei, apoi al treilea

elementul se inserează în poziț ia care corespunde, al patrulea se inserează în lista de trei
elemente, ș i aș a mai departe.

Acest proces continuă până când lista este complet sortată.

Fie o listă A[1], A[2], ... A[n]. Paș ii de urmat pentru o sortare ascendentă sunt:

1. Ordona ț i A[1] ș i A[2].

 2. Compară A[3] cu A[2], ș i dacă A[3] este mai mare sau egal cu A[2], continuă cu următorul
elemento si nu se compară A[3] cu A[1]; dacă A[3] este mai mare sau egal cu A[1], inserează
A[3] între A[1] ș i A[2]. Dacă A[3] este mai mic decât A[1], atunci transferaț i A[3] la A[1],
A[1] a A[2] ș i A[2] a A[3].

3. Se presupune că primele n-1 elemente sunt ordonate ș i trebuie să inserăm al n-lea

element. Dacă A[m] este mai mare decât A[k] (cu K = 1, 2, ..., m-1), trebuie să se mute o
poziț ia A[k+1], ... A[m-1] ș i stocarea A[m] în poziț ia k+1.

Considerăm aceeaș i aranjare ca în exemplul anterior { 7, 2, 8, 3, 5, 1 }. Procesul ar fi de

în următoarea manieră:

Public static void insercion( int[] v){

/* sortare prin inserț ie */
int j=0,temp;
pentru (int i = 1; i < [Link]; i++) {
temp = v[i];
j = i - 1;
în timp ce ( j >= 0 && temp < v[j]) {
v[j+1] = v[j];
j--;
}
v[j+1] = temp;
}
}
4.3. - Metoda Inserț ie ș i Selecț ie

Public static void Insercion (int[] matrice){

int temp, j;
pentru (int i = 1; i < [Link]; i++) {
temp = matrice[i];
j = i - 1;
while ( (matrix[j] > temp) && (j >= 0) ) {
matrix[j + 1] = matrix[j];
j--;
}
matrix[j + 1] = temp;
}
}

Public static void Seleccion (int[] matrice){

int j, p, buffer, limit = [Link]-1;

pentru (int k = 0; k < limit; k++){

p = k;
pentru (int i = k+1; i <= limit; i++)
dacă (matricea[i] < matricea[p]) p = i;
dacă (p != k){
buffer = matrice[p];
matrice[p] = matrice[k];
matrix[k] = buffer;
}
}
}

Bucle principal al ordonării prin inserț ie analizează succesiv toate

elementele matricei de la al doilea până la al n-lea, ș i introduce fiecare în locul
adecvat între predecesorii săi din matrice.

Sortarea prin selecț ie funcț ionează selectând cel mai mic element din matrice ș i
ducându-l la început; apoi selectează următorul mai mic ș i îl pune în
a doua poziț ie a matricei ș i aș a mai departe.
5–ORDONARE PRIN AMESTEC

A fost dezvoltat în 1945 de John Von Neumann. Conceptual, sortarea prin

mezcla funcț ionează în felul următor:

1. Dacă lungimea listei este 0 sau 1, atunci este deja sortată. În alt caz:
2. Împărț iț i lista dezordonată în două subliste de aproximativ jumătate din dimensiune.
3. Aș ezaț i fiecare sublistă recursiv folosind sortarea prin interclasare.
4. Amesteca cele doua subliste intr-o singura lista ordonata.

Sortarea prin amestec încorporează două idei principale pentru a îmbunătăț i timpul său de
ejecución:
O listă mică va avea nevoie de mai puț ini paș i pentru a se ordona decât o listă mare.

Sunt necesari mai puț ini paș i pentru a construi o listă ordonată din două liste
de asemenea ordonate, care pornesc de la două liste dezordonate.

De exemplu, va fi necesar să împletiț i fiecare listă doar după ce sunt ordonate.

În continuare se descrie algoritmul în pseudocod (se avertizează că nu sunt incluse)

cazuri speciale pentru vectori goi, o implementare într-un limbaj de programare
real ar trebui să ț ină cont de aceste detalii):

funcț ia merge_sort( list m )

dacă lungimea(m)≤1
return m
var list left, right, result
var integer mijloc = length(m) / 2

pentru fiecare x în m până la mijloc

adu x la stânga

pentru fiecare x în m după mijloc

adaugă x la dreapta
stânga = sortare_fuziune(stânga)
dreapta = sortare_interclasata(dreapta)

result = merge(left, right)

returnaț i rezultatul

funcț ia merge (listă stânga, dreapta)

var list rezultat
în timp ce lungimea(stânga) > 0 sau lungimea(dreapta) > 0
dacă lungimea(stânga) > 0 ș i lungimea(dreapta) > 0
dacă primul(stânga) ≤ primul(dreapta)
adaugă primul (stânga) la rezultat
stânga = rest(stânga)
altfel
ataș ează primul (dreapta) la rezultat
dreptul = rest(dreptul)
altfel dacă lungimea(stânga) > 0
adaugă primul (stâng) la rezultat
stânga = restul(stânga)
altfel dacă lungimea(dreapta) > 0
adaugă primul(dreapta) la rezultat
dreapta = rest(dreapta)
sfârș it în timp ce
returnează rezultat
Acest algoritm constă în esenț ă în a împărț i lista de numere în părț i egale ș i apoi
mezclându-le comparându-le ș i lăsându-le ordonate.

Ș i dacă ne gândim la acest algoritm recursiv, putem imagina că va împărț i lista până
a avea un element în fiecare listă, apoi îl compară cu cel de lângă el ș i în funcț ie de
coresponde, îl situează unde trebuie.

În figura următoare putem vedea cum funcț ionează:

Exemplu: Avem o listă { 5, 2, 4, 6, 1, 3, 2, 6 }, lista este împărț ită în prima de

cele două apeluri la merge cu { 5, 2, 4, 6 }, apoi din nou este împărț ită în { 5, 2 }
se intercala obț inând { 2, 5 }, a doua apelare recuperează { 4, 6 } ș i se intercalează pentru
obț ine { 2, 4, 5, 6 }. Cu jumătatea { 1, 3, 2, 6 } se întâmplă aceeaș i reducere de elemente
tras după apeluri intercalând în cele din urmă ieș irea pentru a obț ine { 1, 2, 2, 3, 4, 5, 6, 6 }.
Algoritmul de sortare prin fuziune (Mergesort) se împarte în două procese, mai întâi se
împarte lista în părț i egale:

public static void mergesort (int[ ] matrice, int init, int n){
int n1, n2;
dacă (n > 1){
n1 = n / 2;
n2 = n - n1;
mergesort(matrice, init, n1);
mergesort(matrice, init + n1, n2);
combină(matrice, iniț ial, n1, n2);
}
}

Ș i algoritmul care ne permite să amestecăm elementele după cum este necesar:

private static void merge(int[] matrice, int init, int n1, int n2) {
int[ ] buffer = new int[n1+n2];
int temp = 0;
int temp1 = 0;
int temp2 = 0;
int i;
în timp ce ((temp1 < n1) && (temp2 < n2)) {
dacă (matrice[iniț + temp1] < matrice[iniț + n1 + temp2])
buffer[temp++] = matrix[init + (temp1++)];
altfel
buffer[temp++] = matrix[init + n1 + (temp2++)];
}
în timp ce (temp1 < n1) buffer[temp++] = matrice[init + (temp1++)];

în timp ce (temp2 < n2) buffer[temp++] = matrice[init + n1 + (temp2++)];

pentru (i = 0; i < n1+n2; i++) matricea[init + i] = buffer[i];

}

6–METODA SHELLSORT

Shellsort poartă acest nume în onoarea inventorului său, Donald Shell, care l-a publicat în 1959. La
ideea de bază a acestei metode este de a distribui aranjamentul într-un mod care să genereze o matrice de
valori unde fiecare element este comparat în mod adiacent folosind un
mecanism de inserț ie directă simplă, acest interval care generează grupuri într-o manieră matricială
care este redus treptat până se stabilizează într-o valoare uniformă de 1.

În metoda de sortare prin inserț ie directă, se foloseș te în fiecare subgrup în modul

fiecare element este comparat pentru a-ș i găsi poziț ia corectă în aranjament cu elementele
care se află în partea stângă. Dacă elementul de inserat este mai mic decât
grup de elemente care se află în stânga sa, va fi necesar să se efectueze mai multe
comparatii înainte de locaț ia sa.

Shell propune ca comparaț iile între elemente să se efectueze cu salturi mai mari.
dimensiune, dar cu creș teri descrescătoare; astfel, elementele vor rămâne ordonate mai
rapid

Algoritmul pentru Shellsort ar fi următorul. Anumiț i autori presupun o secvenț ă

geometrica de decremento (2.2) care permite o distribuț ie presumabil mai
raț ional pentru aranjarea grupurilor de elemente de comparat.
Algoritmul foloseș te un aranjament de la 0 la n-1:

inc = rotunjit(n/2)
în timp ce inc > 0 {
pentru i = inc până la n–1 {
temp = a[i]
j=i
în timp ce j = inc && a[j - inc] > temp {
a[j] = a[j - inc]
j = j–inc
}
a[j] = temp
}
inc = rotunjit(inc / 2.2)
}

Exemplu: avem o listă de numere precum 13 14 94 33 82 25 59 94 65 23 45 27 73 25

39 10. Ș i dacă începem cu o dimensiune a pasului de 5, am putea vizualiza asta împărț ind
lista de numere într-un tabel cu 5 coloane. Asta ar rămâne:

Această metodă este o îmbunătăț ire a algoritmului de sortare prin inserț ie (Insertsort).
avem în vedere că sortarea prin inserț ie este mult mai eficientă dacă a noastră
lista de numere este semi-ordonată ș i mută o valoare o singură poziț ie deodată.

În timpul executării acestui algoritm, numerele din listă sunt aproape sortate ș i
în final, ultimul pas sau funcț ia acestui algoritm este un simplu metodă prin inserț ie
deoarece, fiind numere aproape ordonate, este mai eficient.
public void shellSort(int[] matrice){
pentru (int increment = [Link] / 2; increment > 0; increment =
(increment == 2 ? 1 : (int) [Link](increment / 2.2))
pentru (int i = increment; i < [Link]; i++) {
pentru (int j = i; j >= increment ș i matrice[j - increment] >
matrix[j]; j -= increment){
Int temp = matrice[j];
matrix[j] = matrix[j - increment];
matrix[j - increment] = temp;
}
}
}
}

O altă metodă:

void shell_sort(int[] A){

int j, temp;
int incremnt = [Link]/2;
while (incremnt > 0) {
pentru (int i = incremnt; i < dimensiune; i++) {
j = i;
temp = A[i];
în timp ce ((j >= incremnt) && (A[j-incremnt] > temp)) {
A[j] = A[j - increment];
j = j - increment;
}
A[j] = temp;
}
incremnt /= 2;
}
}

7 - METODĂ RAPIDĂ (quicksort)

Metoda de sortare Quicksort a fost dezvoltată de Hoare în anul 1960.

Este este algoritmul de sortare cel mai rapid. Se bazează pe tehnica divide ș i cucereș te, care
constă în a împărț i array-ul în array-uri mai mici ș i a le sorta. Pentru a face
în această diviziune, se ia o valoare din array ca pivot ș i se mută toate elementele
mai mici decât acest pivot la stânga lui, iar cei mai mari la dreapta lui. Apoi se
aplică aceeaș i metodă la fiecare dintre cele două părț i în care este împărț it array-ul.

După alegerea pivotului se efectuează două căutări:

Una de la stânga la dreapta, căutând un element mai mare decât pivotul
Alta de dreapta la stânga, căutând un element mai mic decât pivotul.

Cuando se han encontrado los dos elementos anteriores, se intercambian, y se sigue

realizând căutarea până când cele două căutări se întâlnesc.

Implementarea metodei de sortare Quicksort este în mod clar recursivă.

Presupunând că luăm ca pivot primul element, metoda Java Quicksort care
implementează acest algoritm de sortare pentru a ordona un array de întregi care este prezentat la
continuare. Odată ce este împărț it, ceea ce face este să lase toț i mai mari decât pivotul la al său
dreapta ș i toț i cei mai mici la stânga ei. La finalizarea algoritmului, elementele noastre sunt
ordonate.
Este un algoritm relativ eficient ș i reprezintă o îmbunătăț ire substanț ială faț ă de metoda de
schimb direct.

Algoritmul este următorul:

1. Alege ț i un element din lista de elemente de ordonat (pivot).

2. Resituarea celorlalte elemente ale listei de fiecare parte a pivotului, astfel încât la un
să rămână toț i cei care sunt mai mici decât el, iar la celălalt cei mai mari. Elementele egale
pivotele pot fi plasate atât la dreapta cât ș i la stânga lor, în funcț ie de
de la implementare dorită. În acest moment, pivotul ocupă exact
locul care îi va corespunde în lista ordonată.

3. Lista este separată în două sub-lista, una formată din elementele la

la stânga pivotului, ș i alta pentru elementele de partea sa dreaptă.

4. Repeta ț i acest proces în mod recursiv pentru fiecare sub-listă cât timp acestea
să conț ină mai mult de un element. Odată ce acest proces este finalizat, toate
elementele vor fi ordonate.

După cum se poate presupune, eficienț a algoritmului depinde de poziț ia în care

termenul pivot ales. În cel mai bun caz, pivotul se termină în centrul listei,
divizând-o în două subliste de dimensiuni egale. În acest caz, ordinea de complexitate a
algoritmul este O(n log n).

În cel mai rău caz, pivotul ajunge la un capăt al listei. Ordinea de complexitate a
algoritmul este atunci de O(n²). Cazul cel mai rău va depinde de implementarea
algoritm, deș i se întâmplă de obicei în liste care sunt ordonate sau aproape
ordonate. Dar în principal depinde de pivot, de exemplu algoritmul implementat
toma ca pivot întotdeauna primul element al aranjamentului, iar aranjamentul pe care îl trecem este
ordonat, va genera întotdeauna la stânga un aranjament gol, ceea ce este ineficient.

Alegerea pivotului va determina eficienț a acestui algoritm, deoarece determină

partiț ia array-ului. Dacă considerăm că array-ul este dezordonat, putem alege în mod
primul element ș i algoritmul ar funcț iona eficient. Dar dacă array-ul este aproape
ordonat, alegerea primului element ca pivoti ar fi o soluț ie proastă deoarece
am obț ine un subarray foarte mic ș i unul foarte mare. Din acelaș i motiv, alegeț i
ultimul element al array ca pivot este, de asemenea, o idee proastă. Ne propunem să obț inem
ca dimensiunea subarreglo să fie cât mai asemănătoare posibil.

O alternativă la alegerea primului element este alegerea ca pivot a unui element ales la întâmplare din
între toț i cei din array.

O altă strategie este să calculăm mediana valorilor din stânga, centru ș i dreapta
vector.

Ejemplo1:Para el vector: 9 8 1 6 10 2 3, se calcula la mediana de los elementos que

ocupă primul loc, ultimul ș i centrul adică 9 3 6. Mediana este 6 care ar determina
partiț iile {1 3 2} {6} {8 10 9}.

Exemplu2: Dacă avem 3 5 4 8, practic, ceea ce face algoritmul este să împartă lista de 4
elemente în părț i egale, pe o parte 3, pe cealaltă parte 4 8 ș i ca comodin sau pivot 5.
Apoi întreabă, 3 este mai mare sau mai mic decât jokerul? Este mai mic, aș a că îl lasă deoparte.
izq. Ș i cum s-au terminat elementele de acel lado, mergem pe cealaltă parte. 4 Este mai mare sau mai mic
ce este pivotul? Mai mic, atunci îl aruncă la stânga. Apoi întreabă de 8, fiind mai mare îl
deja unde este, rămânând ceva astfel: 3 4 5 8
Exemplu3: Se marchează pivotul ș i indicii i ș i j cu literele p, i ș i j respectiv:
De forma grafică, procesul ar fi următorul:

Algoritmul este următorul:

public void Quicksort(int matrice[], int a, int b){
[Link] = new int[[Link]];
int buf;
int de la = a;
int to = b;
int pivot = matrix[(from+to)/2];
do{
în timp ce (matricea[din] < pivot) {
de la++;
}
în timp ce (matricea[to] > pivot) {
la--;
}
dacă(from <= to){
buf = matrice[from];
matrice[from] = matrice[to];
matrix[to] = buf;
de++;
către--;
}
}în timp ce (de la <= la);

dacă(a < to){

Quicksort(matrice, a, la)
}
dacă(from < b){
Quicksort(matrice, de la, b);
}
[Link] = matrix;
}

Metoda ordonează un array A de întregi de la poziț ia stânga până la poziț ia dreapta. În

prima apelare va primi valorile izq = 0, der = ELEMENTOS-1.
O altă metodă:

public static void quicksort(int A[], int izq, int der) {

int pivote=A[izq]; // luăm primul element ca pivote

int i=izq; // i realizează căutarea de la stânga la dreapta
int j=der; // j realizează căutarea de la dreapta la stânga
int aux;

while(i<j){ // atâta timp cât căutările nu se intersectează

while(A[i]<=pivote && i<j) i++; // busca elemento mayor que pivote
în timp ce(A[j]>pivote) j--; // caută element mai mic decât pivotul
dacă (i<j) { // ș i nu s-au întâlnit
aux = A[i]; îi schimbă
A[i]=A[j];
A[j]=aux;
}
}
A[izq]=A[j]; // se plasează pivotul în locul său astfel încât vom avea
A[j]=pivote; // cei mai mici la stânga lui ș i cei mai mari la dreapta lui
dacă(izq<j-1)
quicksort(A,izq,j-1); // ordonăm subarray-ul stâng
dacă(j+1 <der)
quicksort(A,j+1,der); // ordonăm subarray-ul drept
}

8–COMPLEXITATE
Fiecare algoritm de sortare are prin definiț ie operaț iuni ș i calcule minime ș i
maxime pe care le realizează (complexitate), urmează o tabelă care indică cantitatea de
calculele care corespund fiecărui metodă de sortare:
9–COMPARAREA TIMPURILOR
S-a ordonat o cantitate determinată de elemente aleatorii într-o listă prin
metode diferite de sortare. (în secunde)

Aș a cum putem analiza, algoritmul care se întârzie din ce în ce mai mult timp este cel al
bule, apoi selecț ia ș i în cele din urmă inserț ia. Algoritmii care le urmează sunt Shell
ș i cel de sortare prin amestec, dar cel mai optim este „Rapid sau Quicksort”.

10–ORDONARE BAZATĂ PE COMPARAȚII (HeapSort)

Sortarea prin grămadă (Heapsort) este o variantă a algoritmului de selecț ie,

care este un algoritm de sortare non-recursiv, instabil, cu complexitate computaț ională
O(n log n).

Acest algoritm constă în stocarea tuturor elementelor vectorului de ordonat într-un

monticul (heap), ș i apoi extrage nodul care rămâne ca nod rădăcină al monticului (vârf)
în iteratii succesive, obț inând setul ordonat. Se bazează pe un
proprietatea mounds-urilor, prin care, vârful conț ine întotdeauna elementul cel mai mic (sau
mai mare, în funcț ie de modul în care a fost definit mormanul) dintre toate cele stocate în el.

Semnificaț ia lui heap în computaț ie este aceea a unei cozi de priorităț i.

Are următoarele caracteristici:
Un heap este un aranjament de n poziț ii ocupate de elementele cozii.

Se mapa un arbore binar de aș a manieră în aranjament încât nodul din poziț ia i este
părintele nodurilor în poziț iile (2*i) ș i (2*i+1).

Valoarea dintr-un nod este mai mare sau egală cu valorile copiilor săi. Prin urmare,
nodo părinte are cea mai mare valoare din întregul său subarbore.

Heap Sort constă în esenț ă în:

•converti aranjamentul într-un heap.

•construieș te un aranjament ordonat de la spate spre înainte (de la mare la mic) repetând
paș ii următori:
a scoate valoarea maximă din heap (cea de la poziț ia 1)
a pune acea valoare în aranjamentul ordonat
o reconstruir el heap con un elemento menos

•utiliza aceeaș i aranjare pentru heap ș i aranjarea ordonată.

11–ORDONARE EXTERNĂ

Ordonarea fiș ierelor are loc atunci când volumul datelor de procesat este
prea mare ș i aceleaș i nu încap în memoria principală a computerului.

În momentul în care apare această situaț ie, metodele de sortare internă nu pot fi aplicate, astfel încât
ce ar trebui să fie considerat în alte tipuri de algoritmi pentru sortarea datelor stocate în fiș iere.

Prin ordonarea fiș ierelor se înț elege, aș adar, ordonarea sau clasificarea acestora,
ascendent sau descendent, în funcț ie de un câmp determinat la care se
denumirea va fi câmp cheie. Principalul dezavantaj al acestei ordonări este timpul de
execuț ie, din cauza operaț iunilor succesive de intrare ș i ieș ire.

Cele mai importante două metode de ordonare externă sunt cele bazate pe amestecare.
direct ș i în amestecul echilibrat.
11.1.–ORDONARE PRIN AMESTEC DIRECT

Metoda de sortare prin amestecare directă este probabil cea mai utilizată datorită uș urinț ei sale
comprehensiune.

Ideea centrală a acestui algoritm constă în realizarea succesivă a unei partiț ii ș i a unei
fuzionare care produce secvenț e ordonate de lungime din ce în ce mai mare. În prima trecere
participarea are lungimea de 1 iar fuzionarea sau amestecul produce secvenț e ordonate de
longitudine 4.

Acest proces se repetă până când lungimea secvenț ei pentru partiț ie devine mai mare sau
la fel ca lungimea secvenț ei pentru partiț ie să fie mai mare sau egală cu numărul de
elementele arhivei originale.

Exemplu: Să presupunem că se doreș te să se sorteze cheile din fiș ierul F. Pentru a realiza aș a ceva
Activitatea foloseș te două fiș iere auxiliare denumite F1 ș i F2.

F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61

PRIMA TRECE
Partiț ie în secvenț e de lungime 1.
F1: 09 14 29 31 04 13 72 61
F2: 75 68 17 25 05 18 46
Fuzionare în secvenț e de lungime 2.
F1: 09 75 14 68 17 29 25 31 04 05 13 18 46 72 61

A doua trecută
Partiț ie în secvenț e de lungime 2.
F1: 09 75 17 29 04 05 46 72
F2: 14 68 25 31 13 18 61
Fuzionare în secvenț e de lungime 4.
F1: 09 14 68 75 17 25 29 31 04 05 13 18 46 61 72

TERCERA PASADA
Partiț ie în secvenț e de lungime 4.
F1: 09 14 68 75 04 05 13 18
F2: 17 25 29 31 46 61 72
Fuzionare în secvenț e de lungime 8.
F1: 09 14 75 25 29 31 68 75 04 05 13 18 46 61 72

SĂPTĂMÂNA ANTERIOARĂ
Partiț ie în secvenț e de lungime 8.
F1: 09 14 17 25 29 31 68 75
F2: 04 05 13 18 46 61 72
Fuziune în secvenț e de lungime 16.
F1: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75
12–EXEMPLE ÎN FLASH
Aplicatii Flash de exemplu pentru aceste metode de sortare:

SELECȚ IE DIRECTĂ (SORTARE SELECTIVĂ)

[Link]

[Link]

INSERARE DIRECTĂ (SORTARE PRIN INSERARE)

[Link]

[Link]

SORTARE RAPIDĂ

[Link]

SORTARE SHELL

[Link]

ORDONARE BUBULĂ (BUBBLE SORT)

[Link]