Extern sortering

Extern sortering - sorteringsdata som finns på kringutrustning och passar inte i RAM , det vill säga när det är omöjligt att tillämpa en av de interna sorteringarna . Det är värt att notera att intern sortering är mycket effektivare än extern sortering, eftersom det tar mycket kortare tid att komma åt RAM än magnetiska skivor , band , etc.

Oftast används extern sortering i DBMS . Huvudkonceptet när man använder extern sortering är konceptet med ett segment. Ett längdsegment är en sekvens av poster , ,..., där alla poster är ordnade efter någon nyckel. Det maximala antalet segment i filen (alla element är inte ordnade). Minsta antal segment är 1 (alla element är ordnade).

Till exempel, i en del fil A finns en endimensionell array:

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

Låt oss dela upp arrayen i segment:

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

Vi kan säga att arrayen i fil A består av 5 segment.

Till exempel, i någon fil B finns det en endimensionell array:

1 2 3 4 5 6 7 8 9 10

Låt oss dela upp arrayen i segment:

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

Vi kan säga att arrayen i fil B består av 1 segment.

Till exempel, i en del fil A finns en endimensionell array:

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

Låt oss dela upp arrayen i segment:

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

Vi kan säga att arrayen i fil A består av 13 segment.

Tanken med de flesta metoder är att dela upp data i en serie sekvenser som passar in i RAM-minnet. Därefter tillämpas en av de interna sorteringsmetoderna, varefter sekvenserna slås samman. Ju större mängd RAM-minne är, desto längre blir sekvenserna, och därför blir antalet mindre, vilket kommer att öka sorteringshastigheten.

Om mängden RAM är liten kan du dela upp källdata i flera sekvenser och sedan direkt använda sammanfogningsproceduren.

Grundläggande sorteringsmetoder:

1. Naturlig sortering (naturlig sammanfogningsmetod)
2. Tvåvägs balanserad sammanslagning
   1. Sortering efter n-vägs sammanslagning.
3. Flerfasig sortering (Fibonacci)

Litteratur

• Richard Forsyth. Pascal för alla = Pascal at Work and Play. En introduktion till datorprogrammering i Pascal. - M . : Mashinostroenie, 1986. - 288 sid.
• Robert Sedgwick. Grundläggande algoritmer i C. Grundläggande/Datastrukturer/Sortering/Sökning. - St Petersburg. : DiaSoftYUP, 2003. - 672 sid. — ISBN 5-93772-081-4 .

• Niklaus Wirth. Algoritmer och datastrukturer. Ny version för Oberon. - M. : DMK Press, 2012. - 272 sid. - ISBN 978-5-94074-734-5 .