Sortare externă

Sortare externă - sortare date situate pe dispozitive periferice și nu se potrivesc în RAM , adică atunci când este imposibil să se aplice unul dintre sortările interne . Este de remarcat faptul că sortarea internă este mult mai eficientă decât sortarea externă, deoarece este nevoie de mult mai puțin timp pentru a accesa RAM decât discurile magnetice , benzile etc.

Cel mai adesea sortarea externă este utilizată în SGBD . Conceptul principal atunci când se utilizează sortarea externă este conceptul de segment. Un segment de lungime este o succesiune de intrări , ,…, în care toate intrările sunt ordonate după o cheie. Numărul maxim de segmente din fișier (toate elementele nu sunt ordonate). Numărul minim de segmente este 1 (toate elementele sunt ordonate).

De exemplu, într-un fișier A există o matrice unidimensională:

12 35 65 0 24 36 3 5 84 90 6 2 30

Să împărțim matricea în segmente:

12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30

Putem spune că tabloul din fișierul A este format din 5 segmente.

De exemplu, într-un fișier B există o matrice unidimensională:

1 2 3 4 5 6 7 8 9 10

Să împărțim matricea în segmente:

| 1 2 3 4 5 6 7 8 9 10 |

Putem spune că tabloul din fișierul B este format din 1 segment.

De exemplu, într-un fișier A există o matrice unidimensională:

20 17 16 14 13 10 9 8 6 4 3 2 0

Să împărțim matricea în segmente:

| 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |

Putem spune că tabloul din fișierul A este format din 13 segmente.

Ideea majorității metodelor este de a împărți datele într-o serie de secvențe care se potrivesc în memoria RAM. În continuare, se aplică una dintre metodele de sortare internă, după care secvențele sunt îmbinate. Cu cât cantitatea de RAM este mai mare, cu atât secvențele vor fi mai lungi și, prin urmare, cu atât numărul lor va fi mai mic, ceea ce va crește viteza de sortare.

Dacă cantitatea de RAM este mică, atunci puteți împărți datele sursă în mai multe secvențe și apoi utilizați direct procedura de îmbinare.

Metode de sortare de bază:

1. Sortare naturală (metoda de îmbinare naturală)
2. Sortare de îmbinare echilibrată în două sensuri
   1. Sortare în funcție de îmbinare în n-cai.
3. Sortare în mai multe faze (Fibonacci)

Literatură

• Richard Forsyth. Pascal pentru toți = Pascal at Work and Play. O introducere în programarea computerelor în Pascal. - M . : Mashinostroenie, 1986. - 288 p.
• Robert Sedgwick. Algoritmi fundamentali în C. Fundamente/Structuri de date/Sortare/Căutare. - Sankt Petersburg. : DiaSoftYUP, 2003. - 672 p. — ISBN 5-93772-081-4 .

• Niklaus Wirth. Algoritmi și structuri de date. Noua versiune pentru Oberon. - M. : DMK Press, 2012. - 272 p. - ISBN 978-5-94074-734-5 .