1. METODE DE SORTARE

Sortarea valorilor unei matrice, fie de la cea mai mica la cea mai mare valoare (ordine ascendenta) sau de la cea mai mare la cea mai mica valoare (ordine descendenta) se poate face prin urmatoarele metode:

• Metoda bulelor (bubble);
• Metoda selectiva;
• Metoda Shell;
• Metoda de sortare rapida.

1.1. Metoda bulelor

Aceasta metoda se aplica tablourilor de mici dimensiuni (cu mai putin de 30 de elemente), fiind cea mai lenta metoda de sortare. in cazul acestei metode, prin comparari si deplasari, valorile cele mai mari se deplaseaza in partea de sus a tabloului (cum ies bulele la suprafata apei).

in fig. 1.1, se ilustreaza iteratii ale sortarii prin metoda bulelor.

Fig. 1.1. Ilustrarea sortarii prin metoda bulelor.

/* Metoda bulelor */

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void bubble_sort(int t[], int dim)

}

void main(void)

1.2. Metoda selectiva

Ca si metoda bulelor, metoda selectiva se utilizeaza pentru matrici de cel mult 30 de elemente.

in acest caz, sortarea consta in urmatorii pasi:

• se selecteaza primul element al matricei;
• se cauta in intreaga matrice pana se gaseste valoarea minima
• se plaseaza valoarea minima in primul element;
• se selecteaza al doilea element;
• se cauta cea de-a doua valoare minima din cele ramase etc.

Fig. 1.2 ilustreaza iteratii ale sortarii selective.

Fig. 1.2. Ilustrarea sortarii prin metoda selectiva.

/* Metoda selectiva */

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void selection_sort(int t[], int dim)

}

void main(void)

1.3. Metoda Shell

Sortarea Shell este numita asa dupa creatorul sau Donald Shell. Metoda Shell de sortare compara elementele matricei separate printr-o distanta specifica (gap=interval) pana cand elementele pe care le compara in interval sunt ordonate. Se imparte apoi intervalul la doi si se continua procesul. Cand intervalul devine unu si nu mai apare nici o modificare, sortarea se ncheie.

in cele ce urmeaza, se ilustreaza sortarea unei matrice prin metoda Shell.

gap=4

gap=2

gap=1

i=0

i=0

i=0

i=0

i=0

i=0

i=0

i=1

i=1

i=1

i=1

i=1

i=1

i=1

i=2

i=2

i=2

i=2

i=2

i=2

i=2

i=3

i=3

i=3

i=3

i=3

i=3

i=3

i=4

i=4

i=4

i=4

i=4

i=4

i=4

i=5

i=5

i=5

i=5

i=5

i=5

i=5

i=6

i=6

i=6

i=6

i=6

i=6

i=6

i=7

i=7

i=7

i=7

i=7

i=7

i=7

Cum nu au mai aparut modificari, sortarea se incheie.

/* Metoda Shell */

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void shell_sort(int t[], int dim)

}

while (modificari);

gap = gap / 2;

}

while (gap);

}

void main(void)

1.4. Metoda de sortare rapida

In cazul acestei metode, matricea de valori este considerata ca o lista. Cand incepe sortarea, metoda selecteaza valoarea de mijloc a listei ca separator de lista. Lista este apoi impartita in doua: una cu valorile mai mici decat separatorul de lista si una cu valorile mai mari sau egale cu separatorul de lista. Sortarea se continua apoi recursiv in ambele liste care sunt impartite, fiecare, in cate doua liste mai mici etc.

In fig. 1.3, se ilustreaza metoda de sortare rapida, in cazul a 10 valori.

Fig. 1.3. Ilustrarea metodei de sortatre rapida.

Algoritmul metodei de sortare rapida consta din urmatoarele:

Pasul 1: Se determina separator_lista, -elementul situat la mijlocul tabloului.

Pasul 2: Se pleaca de la de la primul element al listei catre elementul separator, pana cand se gaseste un element mai mare decat elementul separator. Fie i_min indicele acestui element.

Pasul 3: Se pleaca de la de la ultimul element al listei catre elementul separator, pana cand se gaseste un element mai mic decat elementul separator. Fie i_max indicele acestui element.

Pasul 4: Daca i_min < i_max, se schimba locul elementelor gasite si se continua cu pasul 2. In caz contrar, se continua cu pasul 5.

Pasul 5: Daca i_min > i_max, se repeta procedeul, incepand cu pasul 1, pentru listele determinate de primul si i_max, respectiv i_min si ultimul, daca nu s-au atins capetele.

/* Metoda rapida */

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void quick_sort(int t[], int primul, int ultimul)

}

while ( i_min <= i_max );

if ( primul < i_max )

quick_sort(t, primul, i_max );

if ( i_min < ultimul)

quick_sort(t, i_min, ultimul);

}

void main(void)