Ekstern sortering

Ekstern sortering - sorteringsdata placeret på perifere enheder og passer ikke i RAM , det vil sige når det er umuligt at anvende en af ​​de interne sorteringer . Det er værd at bemærke, at intern sortering er meget mere effektiv end ekstern sortering, da det tager meget kortere tid at få adgang til RAM end magnetiske diske , bånd osv.

Oftest bruges ekstern sortering i DBMS . Hovedkonceptet ved brug af ekstern sortering er begrebet et segment. Et længdesegment er en sekvens af indtastninger , ,..., hvor alle indtastninger er ordnet efter en eller anden nøgle. Det maksimale antal segmenter i filen (alle elementer er ikke ordnet). Minimumsantallet af segmenter er 1 (alle elementer er ordnet).

For eksempel er der i nogle fil A et endimensionelt array:

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

Lad os opdele arrayet i segmenter:

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

Vi kan sige, at arrayet i fil A består af 5 segmenter.

For eksempel er der i en fil B et endimensionelt array:

1 2 3 4 5 6 7 8 9 10

Lad os opdele arrayet i segmenter:

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

Vi kan sige, at arrayet i fil B består af 1 segment.

For eksempel er der i nogle fil A et endimensionelt array:

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

Lad os opdele arrayet i segmenter:

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

Vi kan sige, at arrayet i fil A består af 13 segmenter.

Ideen med de fleste metoder er at opdele dataene i en række sekvenser, der passer ind i RAM. Dernæst anvendes en af ​​de interne sorteringsmetoder, hvorefter sekvenserne slås sammen. Jo større mængden af ​​RAM er, jo længere vil sekvenserne være, og derfor vil deres antal være mindre, hvilket vil øge sorteringshastigheden.

Hvis mængden af ​​RAM er lille, kan du opdele kildedataene i flere sekvenser og derefter bruge fletteproceduren direkte.

Grundlæggende sorteringsmetoder:

1. Naturlig sortering (naturlig flettemetode)
2. To-vejs balanceret flette sortering
   1. Sortering efter n-vejs fletning.
3. Multifase sortering (Fibonacci)

Litteratur

• Richard Forsyth. Pascal for alle = Pascal på arbejde og leg. En introduktion til computerprogrammering i Pascal. - M . : Mashinostroenie, 1986. - 288 s.
• Robert Sedgwick. Fundamentale algoritmer i C. Fundamentals/Datastrukturer/Sortering/Søgning. - Sankt Petersborg. : DiaSoftYUP, 2003. - 672 s. — ISBN 5-93772-081-4 .

• Niklaus Wirth. Algoritmer og datastrukturer. Ny version til Oberon. - M. : DMK Press, 2012. - 272 s. - ISBN 978-5-94074-734-5 .