 |
|
 |  |
|
|
| |
 | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
| Istorie | Literatura | Matematica | Psihologie |
In situatia in care tablourile de sortat au elemente de mari dimensiuni, regia mutarii acestor elemente in procesul sortarii este mare.
De aceea este mult mai convenabil ca algoritmul de sortare sa opereze indirect asupra tabloului original prin intermediul unui tablou de indici, urmand ca tabloul original sa fie sortat ulterior intr-o singura trecere.
o Astfel, unui tablou a[1..n] cu elemente de mari dimensiuni,
o I se asociaza un tablou de indici (indicatori) p[1..n];
o Initial se defineste p[i]:=i pentru i=1,n;
o Algoritmul utilizat in sortare se modifica astfel incat sa se acceseze elementele tabloului a prin constructia a[p[i]] in loc de a[i].
o Accesul la a[i] prin p[i] se va realiza numai pentru comparatii, mutarile efectuandu-se in tabloul p[i].
o Cu alte cuvinte algoritmul va sorta tabloul de indici astfel incat p[1] va contine indicele celui mai mic element al tabloului a, p[2] indicele elementului urmator, etc.
In acest mod se evita regia mutarii unor elemente de mari dimensiuni. Se realizeaza de fapt o sortare indirecta a tabloului a.
Principial o astfel de sortare este prezentata in figura 3.2.10.
Tabloul a inainte de sortare:
12 34 5678910
|
32 |
22 |
0 |
1 |
5 |
16 |
99 |
4 |
3 |
50 |
Tabloul de indici p inainte de sortare:
12 3 45 6 78910
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Tabloul a dupa sortare:
1234 5678910
|
32 |
22 |
0 |
1 |
5 |
16 |
99 |
4 |
3 |
50 |
Tabloul de indici p dupa sortare:
12 34 5678910
|
3 |
4 |
9 |
8 |
5 |
6 |
2 |
1 |
10 |
7 |
Fig. 3.2.10. Exemplu de sortare indirecta
Aceasta idee poate fi aplicata practic oricarui algoritm de sortare.
Copyright © 2024 - Toate drepturile rezervate
