Ulkoinen lajittelu

Ulkoinen lajittelu - tietojen lajittelu , joka sijaitsee oheislaitteissa ja ei mahdu RAM -muistiin, eli kun on mahdotonta käyttää jotakin sisäistä lajittelua . On syytä huomata, että sisäinen lajittelu on paljon tehokkaampaa kuin ulkoinen lajittelu, koska RAM-muistiin pääsy vie paljon vähemmän aikaa kuin magneettilevyt , nauhat jne.

DBMS :ssä käytetään useimmiten ulkoista lajittelua . Ulkoista lajittelua käytettäessä pääkäsite on segmentin käsite. Pituussegmentti on merkkijono , ,…, jossa kaikki merkinnät on järjestetty jonkin avaimen mukaan. Tiedoston segmenttien enimmäismäärä (kaikkia elementtejä ei ole järjestetty). Segmenttien vähimmäismäärä on 1 (kaikki elementit on järjestetty).

Esimerkiksi jossain tiedostossa A on yksiulotteinen taulukko:

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

Jaetaan taulukko osiin:

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

Voimme sanoa, että tiedoston A matriisi koostuu 5 segmentistä.

Esimerkiksi jossain tiedostossa B on yksiulotteinen taulukko:

1 2 3 4 5 6 7 8 9 10

Jaetaan taulukko osiin:

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

Voimme sanoa, että tiedoston B matriisi koostuu yhdestä segmentistä.

Esimerkiksi jossain tiedostossa A on yksiulotteinen taulukko:

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

Jaetaan taulukko osiin:

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

Voimme sanoa, että tiedoston A matriisi koostuu 13 segmentistä.

Useimpien menetelmien ideana on jakaa tiedot sarjaan RAM-muistiin sopivia sekvenssejä. Seuraavaksi käytetään yhtä sisäisistä lajittelumenetelmistä, jonka jälkeen sekvenssit yhdistetään. Mitä suurempi RAM-muistin määrä, sitä pidempiä sekvenssit ovat ja siksi sitä pienempi niiden lukumäärä on, mikä lisää lajittelunopeutta.

Jos RAM-muistin määrä on pieni, voit jakaa lähdetiedot useisiin sarjoihin ja käyttää sitten suoraan yhdistämismenettelyä.

Peruslajittelumenetelmät:

1. Luonnollinen lajittelu (luonnollinen yhdistämismenetelmä)
2. Kaksisuuntainen tasapainoinen yhdistämislajittelu
   1. Lajittelu n-suuntaisen yhdistämisen mukaan.
3. Monivaiheinen lajittelu (Fibonacci)

Kirjallisuus

• Richard Forsyth. Pascal kaikille = Pascal at Work and Play. Johdatus tietokoneohjelmointiin Pascalissa. - M .: Mashinostroenie, 1986. - 288 s.
• Robert Sedgwick. C:n perusalgoritmit. Perusteet/Tietorakenteet/Lajittelu/Haku. - Pietari. : DiaSoftYUP, 2003. - 672 s. — ISBN 5-93772-081-4 .

• Niklaus Wirth. Algoritmit ja tietorakenteet. Uusi versio Oberonille. - M. : DMK Press, 2012. - 272 s. - ISBN 978-5-94074-734-5 .