Lajittelualgoritmi - Sorting algorithm

Vuonna tietojenkäsittelytiede , eli lajittelualgoritmi on algoritmi , joka asettaa elementit listan osaksi järjestyksessä . Yleisimmin käytetyt järjestykset ovat numeerinen järjestys ja sanastojärjestys ja joko nouseva tai laskeva. Tehokas lajittelu on tärkeää muiden algoritmien (kuten haku- ja yhdistämisalgoritmien ) tehokkuuden optimoimiseksi, jotka edellyttävät syöttötietojen olevan lajiteltuissa luetteloissa. Lajittelu on myös usein hyödyllistä tietojen kanonisoimiseksi ja ihmisen luettavan tuloksen tuottamiseksi.

Muodollisesti minkä tahansa lajittelualgoritmin tuloksen on täytettävä kaksi ehtoa:

1. Lähtö on monotonisessa järjestyksessä (jokainen elementti ei ole pienempi/suurempi kuin edellinen elementti vaaditun järjestyksen mukaan).
2. Tulos on tulon permutaatio (uudelleenjärjestys, mutta säilyttäen kaikki alkuperäiset elementit).

Optimaalisen tehokkuuden saavuttamiseksi syöttötiedot on tallennettava tietorakenteeseen, joka sallii satunnaisen pääsyn, eikä sellaiseen, joka sallii vain peräkkäisen pääsyn .

Historia ja käsitteet

Tietojenkäsittelyn alusta lähtien lajitteluongelma on herättänyt paljon tutkimusta, ehkä siksi, että sen tehokas ratkaiseminen on monimutkaista yksinkertaisesta, tutusta lausunnosta huolimatta. Varhaisten lajittelualgoritmien kirjoittajia vuoden 1951 aikana oli Betty Holberton , joka työskenteli ENIACin ja UNIVACin parissa . Kuplan lajittelu analysoitiin jo vuonna 1956. Asymptoottisesti optimaaliset algoritmit ovat olleet tiedossa 1900 -luvun puolivälistä lähtien - uusia algoritmeja kehitetään edelleen, ja laajalti käytetty Timsort on vuodelta 2002 ja kirjastolajittelu julkaistiin ensimmäisen kerran vuonna 2006.

Vertailulajittelualgoritmeilla on perusvaatimus Ω ( n log n ) -vertailusta (jotkut syöttösekvenssit vaativat moninkertaisen n log n -vertailun, jossa n on lajiteltavan matriisin elementtien määrä). Algoritmeilla, jotka eivät perustu vertailuihin, kuten laskentatyypillä , voi olla parempi suorituskyky.

Lajittelualgoritmit ovat yleisiä tietojenkäsittelytieteen alkeiskursseilla, joissa ongelman algoritmien runsaus tarjoaa hellävaraisen johdannon erilaisiin ydinalgoritmikäsitteisiin, kuten iso O -merkintä , jakamis- ja valloitusalgoritmit , tietorakenteet , kuten kasat ja binaaripuut , satunnaistetut algoritmit , paras, huonoin ja keskimääräinen tapausanalyysi, aika -avaruuden kompromissit sekä ylä- ja alarajat .

Pienten matriisien lajittelu optimaalisesti (vähiten vertailuja ja vaihtoja) tai nopeasti (eli ottamalla huomioon konekohtaiset yksityiskohdat) on edelleen avoin tutkimusongelma, ja ratkaisut tunnetaan vain hyvin pienistä matriiseista (<20 elementtiä). Samoin optimaalinen (eri määritelmillä) lajittelu rinnakkaiskoneella on avoin tutkimusaihe.

Luokitus

Lajittelualgoritmit voidaan luokitella seuraavasti:

• Laskennallinen monimutkaisuus
  • Paras, huonoin ja keskimääräinen tapaus luettelon koon suhteen. Tyypillisillä sarjalajittelualgoritmeilla hyvä käyttäytyminen on O ( n  log  n ), rinnakkainen lajittelu O: ssa (log ²  n ) ja huono käyttäytyminen on O ( n ² ). Ihanteellinen käyttäytyminen sarjalajittelussa on O ( n ), mutta tämä ei ole mahdollista keskimääräisessä tapauksessa. Optimaalinen rinnakkainen lajittelu on O (log  n ).
  • Vaihtaa "paikan päällä" oleviin algoritmeihin.
• Muistin käyttö (ja muiden tietokoneresurssien käyttö). Erityisesti jotkut lajittelualgoritmit ovat " paikallaan ". Tarkasti ottaen paikan päällä oleva lajittelu tarvitsee vain O (1) -muistia lajiteltujen kohteiden lisäksi; joskus O (log  n ) lisämuistia pidetään "paikallaan".
• Rekursio: Jotkut algoritmit ovat joko rekursiivisia tai ei-rekursiivisia, kun taas toiset voivat olla molempia (esim. Yhdistämislajittelu).
• Vakaus: vakaat lajittelualgoritmit ylläpitävät tietueiden suhteellisen järjestyksen samoilla avaimilla (eli arvoilla).
• Ovatko ne vertailulajeja vai eivät . Vertailulaji tutkii tietoja vain vertaamalla kahta elementtiä vertailuoperaattoriin.
• Yleinen menetelmä: lisäys, vaihto, valinta, yhdistäminen jne. Vaihtolajit sisältävät kuplalajittelun ja pikalähetyksen. Valikoimalajit sisältävät syklilajittelun ja kasanlajittelun.
• Onko algoritmi sarja- vai rinnakkainen. Tämän keskustelun loppuosa keskittyy lähes yksinomaan sarjaalgoritmeihin ja olettaa sarjaliikenteen.
• Mukautuvuus: Vaikuttaako tulon esivalinta vai ei ajoaikaan. Algoritmien, jotka ottavat tämän huomioon, tiedetään olevan mukautuvia .
• Online: Online -algoritmi, kuten Insertion Sort, voi lajitella jatkuvan syöttövirran.

Vakaus

Esimerkki pelikorttien vakaasta lajittelusta. Kun kortit lajitellaan arvon mukaan vakaalla lajittelulla, kahden 5: n on pysyttävä samassa järjestyksessä lajitellussa tulostuksessa, jossa ne olivat alun perin. Kun ne lajitellaan epävakaalla lajittelulla, 5: t voivat päätyä päinvastaiseen järjestyksessä lajitellussa lähdössä.

Vakaat lajittelualgoritmit lajittelevat yhtä suuret elementit samassa järjestyksessä kuin ne näkyvät syötteessä. Esimerkiksi oikealla olevassa korttien lajitteluesimerkissä kortit lajitellaan niiden sijoituksen mukaan ja niiden puku jätetään huomiotta. Tämä mahdollistaa alkuperäisen luettelon useita eri oikein lajiteltuja versioita. Vakaat lajittelualgoritmit valitsevat yhden seuraavista säännöistä: jos kahta kohdetta verrataan yhtä suureksi (kuten kaksi 5 korttia), niiden suhteellinen järjestys säilyy, eli jos yksi tulee syötteessä ennen toista, se tulee ennen toista tulostuksessa.

Vakaus on tärkeää järjestyksen säilyttämiseksi useissa eri lajeissa samassa tietojoukossa . Oletetaan esimerkiksi, että oppilastietueet, jotka koostuvat nimestä ja luokan osasta, lajitellaan dynaamisesti ensin nimen, sitten luokan osion mukaan. Jos molemmissa tapauksissa käytetään vakaata lajittelualgoritmia, lajittelu luokan mukaan -toiminto ei muuta nimijärjestystä; epävakaalla lajittelulla voi olla, että osion mukainen lajittelu sekoittaa nimijärjestyksen, jolloin tuloksena on ei -aakkosellinen oppilasluettelo.

Muodollisemmin lajiteltavat tiedot voidaan esittää tietueena tai arvopaperina, ja sitä osaa datasta, jota käytetään lajitteluun, kutsutaan avaimeksi . Korttiesimerkissä kortit esitetään ennätyksenä (sijoitus, puku), ja avain on sijoitus. Lajittelualgoritmi on vakaa, jos aina kun on kaksi tietuetta R ja S, joilla on sama avain, ja R näkyy alkuperäisen luettelon edessä S, niin R näkyy aina ennen lajiteltavaa luetteloa.

Kun tasa -arvoisia elementtejä ei voida erottaa toisistaan, kuten kokonaislukuja, tai yleisemmin mitä tahansa dataa, jossa koko elementti on avain, vakaus ei ole ongelma. Vakaus ei myöskään ole ongelma, jos kaikki avaimet ovat erilaisia.

Epävakaat lajittelualgoritmit voidaan erityisesti toteuttaa vakaiksi. Yksi tapa tehdä tämä on laajentaa keinotekoisesti avainvertailua siten, että kahden objektin väliset vertailut, joilla on muuten samanlaiset avaimet, päätetään käyttämällä alkuperäisen syöttölistan merkintöjen järjestystä tie-breakerina. Tämän järjestyksen muistaminen voi kuitenkin vaatia lisäaikaa ja tilaa.

Yksi vakaan lajittelualgoritmin sovellus on luettelon lajittelu ensisijaisen ja toissijaisen avaimen avulla. Oletetaan esimerkiksi, että haluamme lajitella korttien käden siten, että puvut ovat järjestyksessä (♣), timantit ( ♦ ), sydämet ( ♥ ), pata (♠) ja kortit lajitellaan jokaisen puvun mukaan sijoitus. Tämä voidaan tehdä lajittelemalla kortit ensin luokituksen mukaan (käyttämällä mitä tahansa lajia) ja tekemällä sitten vakaa lajittelu puvun mukaan:

Jokaisen puvun sisällä vakaa lajittelu säilyttää järjestyksen paremmuuden mukaan. Tätä ajatusta voidaan laajentaa mihin tahansa määrään avaimia, ja sitä käyttää radix -lajittelu . Sama vaikutus voidaan saavuttaa epävakaalla lajittelulla käyttämällä leksikografista avainvertailua, joka esimerkiksi vertaa ensin puvun mukaan ja sitten vertaa sijoituksen mukaan, jos puvut ovat samat.

Algoritmien vertailu

Näissä taulukoissa n on lajiteltavien tietueiden määrä. Sarakkeet "Paras", "Keskimääräinen" ja "Huonoin" antavat ajan monimutkaisuuden kussakin tapauksessa olettaen, että kunkin avaimen pituus on vakio ja siksi kaikki vertailut, vaihtotavat ja muut toiminnot voivat edetä vakioaikana. "Muisti" tarkoittaa lisämuistin määrää, jota tarvitaan luettelon itse käyttämän lisäksi samalla oletuksella. Suoritusajat ja luetellut muistivaatimukset ovat O -merkinnän sisällä , joten logaritmien pohjalla ei ole väliä. Merkintä log ² n avulla (log n ) ² .

Vertailu järjestyy

Alla on taulukko vertailulajeista . Vertailulaji ei voi toimia keskimäärin paremmin kuin O ( n log n ) .

Vertailu järjestyy

Nimi	Parhaat	Keskiverto	Huonoin	Muisti	Vakaa	Menetelmä	Muut muistiinpanot
Pikavalinta	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	${\ displaystyle \ log n}$	Ei	Osiointi	Pikavalinta tehdään yleensä paikallaan O (log n ) -pinotilalla .
Yhdistä lajittelu	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Joo	Yhdistäminen	Erittäin rinnastettavissa (enintään O (log n ) kolmen unkarilaisen algoritmin avulla).
Yhdistäminen paikan päällä	-	-	${\ displaystyle n \ log ^{2} n}$	1	Joo	Yhdistäminen	Voidaan toteuttaa vakaana lajikkeena, joka perustuu vakaaseen sulautumiseen.
Introsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle \ log n}$	Ei	Osiointi ja valinta	Käytetään useissa STL -toteutuksissa.
Heapsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ei	Valinta
Lisäyslajittelu	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Joo	Lisäys	O ( n + d ) , pahimmassa tapauksessa niiden sekvenssien yli, joilla on d -inversio .
Estä lajittelu	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Joo	Lisäys ja yhdistäminen	Yhdistä lohkopohjainen paikalla oleva yhdistämisalgoritmi alhaalta ylöspäin yhdistämisen lajittelun kanssa . ${\ displaystyle O (n)}$
Timsort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Joo	Lisäys ja yhdistäminen	Muihin n-1 vertailuja, kun data on jo järjestetty tai käänteinen lajitellaan.
Valinnan lajittelu	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ei	Valinta	Vakaa ja lisää tilaa, kun käytät linkitettyjä luetteloita tai kun se on lisäyslajittelun muunnelma kahden kohteen vaihtamisen sijaan. ${\ displaystyle O (n)}$
Cubesort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Joo	Lisäys	Muihin n-1 vertailuja, kun data on jo järjestetty tai käänteinen lajitellaan.
Shellsort	${\ displaystyle n \ log n}$	${\ displaystyle n^{4/3}}$	${\ displaystyle n^{3/2}}$	1	Ei	Lisäys	Pieni koodikoko.
Kuplan lajittelu	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Joo	Vaihto	Pieni koodikoko.
Vaihda lajittelu	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Joo	Vaihto	Pieni koodikoko.
Puulaji	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$(tasapainoinen)	n	Joo	Lisäys	Käytettäessä itsetasapainoista binaarista hakupuuta .
Kierrä lajittelu	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ei	Valinta	Paikan päällä teoreettisesti optimaalinen kirjoitusmäärä.
Kirjaston lajittelu	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	n	Ei	Lisäys	Samanlainen kuin aukollinen lisäyslaji. Se vaatii tulon satunnaisen permutoinnin, jotta se takaa erittäin todennäköiset aikarajat, mikä tekee siitä epävakaan.
Kärsivällisyyden lajittelu	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ei	Lisäys ja valinta	Löydöt kaikki pisin kasvava osasekvenssit on O ( n log n ) .
Tasainen	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ei	Valinta	Adaptiivista variantti Kekojärjestäminen perustuu Leonardo sekvenssin mieluummin kuin perinteisen binaarinen kasaan .
Lajitelma	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	n	Joo	Valinta
Turnauksen laji	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ei	Valinta	Heapsortin muunnelma.
Cocktail -ravistin	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Joo	Vaihto	Muunnelma Bubblesortista, joka käsittelee hyvin pieniä arvoja luettelon lopussa
Kampa lajitella	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ei	Vaihto	Nopeampi kuin kuplalajittelu keskimäärin.
Gnome -tyyppinen	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Joo	Vaihto	Pieni koodikoko.
Pariton - parillinen	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Joo	Vaihto	Voidaan ajaa rinnakkaisprosessoreilla helposti.

Ei vertailua

Seuraava taulukko kuvaa kokonaislukulajittelualgoritmeja ja muita lajittelualgoritmeja, jotka eivät ole vertailulajeja . Sellaisina ne eivät rajoitu Ω: iin ( n log n ) . Alla olevat monimutkaisuudet edellyttävät n lajiteltavaa kohdetta, joiden avaimet ovat koon k , numerokoko d ja r lajiteltava numeroalue. Monet niistä perustuvat oletukseen, että avaimen koko on riittävän suuri, jotta kaikilla merkinnöillä on yksilölliset avainarvot, ja siksi n ≪ 2 ^k , missä ≪ tarkoittaa "paljon vähemmän kuin". Yksikkökustannuksellisessa hajautetussa konemallissa algoritmit, joiden käyntiaika on , kuten radix-lajittelu, vievät silti aikaa, joka on verrannollinen Θ: een ( n log n ) , koska n on rajoitettu olemaan enintään ja enemmän elementtejä lajittelu vaatisi isomman k : n niiden tallentamiseksi muistiin. ${\ displaystyle \ scriptstyle n \ cdot {\ frac {k} {d}}}$${\ displaystyle 2^{\ frac {k} {d}}}$

Ei vertailua

Nimi	Parhaat	Keskiverto	Huonoin	Muisti	Vakaa	n ≪ 2 k	Huomautuksia
Pigeonhole lajitella	-	${\ displaystyle n+2^{k}}$	${\ displaystyle n+2^{k}}$	${\ displaystyle 2^{k}}$	Joo	Joo	Ei-kokonaislukuja ei voi lajitella.
Kauhan lajittelu (yhtenäiset avaimet)	-	${\ displaystyle n+k}$	${\ displaystyle n^{2} \ cdot k}$	${\ displaystyle n \ cdot k}$	Joo	Ei	Oletetaan elementtien tasaista jakautumista alueen verkkotunnuksesta. Ei voi myöskään lajitella ei-kokonaislukuja
Ryhmän lajittelu (kokonaislukunäppäimet)	-	${\ displaystyle n+r}$	${\ displaystyle n+r}$	${\ displaystyle n+r}$	Joo	Joo	Jos r on , niin keskimääräinen ajan monimutkaisuus on . ${\ displaystyle O (n)}$${\ displaystyle O (n)}$
Laskeminen	-	${\ displaystyle n+r}$	${\ displaystyle n+r}$	${\ displaystyle n+r}$	Joo	Joo	Jos r on , niin keskimääräinen ajan monimutkaisuus on . ${\ displaystyle O (n)}$${\ displaystyle O (n)}$
LSD Radix Lajittele	${\ displaystyle n}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	Joo	Ei	${\ displaystyle {\ frac {k} {d}}}$rekursiotasot, 2 d laskentataulukolle. Toisin kuin useimmat jakelulajit, tämä voi lajitella liukulukuluvut , negatiiviset luvut ja paljon muuta.
MSD Radix Lajittele	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	Joo	Ei	Vakaa versio käyttää ulkoista n -kokoluokkaa kaikkien lokeroiden säilyttämiseen. Sama kuin LSD-muunnelma, se voi lajitella ei-kokonaislukuja.
MSD Radix Sort (paikallaan)	-	${\ displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle 2^{1}}$	Ei	Ei	d = 1 paikan päällä, rekursiotasot, ei laskutaulukkoa. ${\ displaystyle k/1}$
Levitä	n	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot \ vasen ({{\ frac {k} {s}}+d} \ oikea)}$	${\ displaystyle {\ frac {k} {d}} \ cdot 2^{d}}$	Ei	Ei	Asymptoottiset perustuvat oletukseen, että n ≪ 2 k , mutta algoritmi ei vaadi tätä.
Burstsort	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	Ei	Ei	On parempi vakio tekijä kuin radix -lajittelu merkkijonoille. Vaikka se riippuu hieman yleisesti esiintyvien merkkijonojen erityispiirteistä.
Flashsort	n	${\ displaystyle n+r}$	${\ displaystyle n^{2}}$	n	Ei	Ei	Edellyttää lineaarisessa ajassa elementtien tasaista jakautumista alueen verkkotunnuksesta. Jos jakelu on erittäin vinossa, se voi mennä toisen asteen, jos taustalla oleva lajittelu on neliöllinen (se on yleensä lisäyslajittelu). Paikan päällä oleva versio ei ole vakaa.
Postimies	-	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	-	Ei	Muunnos kauhan lajittelusta, joka toimii hyvin samalla tavalla kuin MSD Radix Sort. Erityisesti postin palvelutarpeisiin.

Näytesorttia voidaan käyttää rinnastamaan minkä tahansa vertailun ulkopuolisen tyypin jakamalla tiedot tehokkaasti useisiin ämpäriin ja siirtämällä sitten lajittelun useille prosessoreille ilman tarvetta yhdistää, koska kauhat on jo lajiteltu keskenään.

Muut

Jotkut algoritmeja hidas verrattuna kuin edellä, kuten bogosort rajatonta ajoaika ja juoksupoika lajitella , jossa on O ( n ^2,7 ) ajoaika. Näitä lajikkeita kuvataan yleensä opetustarkoituksissa, jotta voidaan osoittaa, miten algoritmien käyttöaika arvioidaan. Seuraavassa taulukossa kuvataan joitain lajittelualgoritmeja, jotka ovat epäkäytännöllisiä tosielämän käyttöön perinteisissä ohjelmistokäytännöissä erittäin huonon suorituskyvyn tai erikoislaitteistovaatimusten vuoksi.

Nimi	Parhaat	Keskiverto	Huonoin	Muisti	Vakaa	Vertailu	Muut muistiinpanot
Helmi lajitella	n	S	S	${\ displaystyle n^{2}}$	Ei käytössä	Ei	Toimii vain positiivisten kokonaislukujen kanssa. Vaatii erikoislaitteiston toimiakseen taatussa ajassa. Ohjelmistototeutus on mahdollista, mutta käyntiaika on silloin , kun S on kaikkien lajiteltavien kokonaislukujen summa, ja pienten kokonaislukujen tapauksessa sen voidaan katsoa olevan lineaarinen. ${\ displaystyle O (n)}$${\ displaystyle O (S)}$
Yksinkertainen pannukakku	-	n	n	${\ displaystyle \ log n}$	Ei	Joo	Luku on käännösten määrä.
Spagetti (kysely) lajitella	n	n	n	${\ displaystyle n^{2}}$	Joo	Kysely	Tämä on lineaarinen analoginen algoritmi alkioiden sarjan lajittelemiseksi, mikä vaatii O ( n ) -pinoa ja lajittelu on vakaa. Tämä vaatii n rinnakkaista prosessoria. Katso spagettilajittelu#Analyysi .
Lajitteluverkosto	Vaihtelee	Vaihtelee	Vaihtelee	Vaihtelee	Vaihtelee (vakaat lajitteluverkot vaativat enemmän vertailuja)	Joo	Vertailujärjestys asetetaan etukäteen kiinteän verkon koon perusteella.
Bitoninen lajittelija	${\ displaystyle \ log ^{2} n}$ rinnakkain	${\ displaystyle \ log ^{2} n}$ rinnakkain	${\ displaystyle n \ log ^{2} n}$ ei rinnakkaisia	1	Ei	Joo	Tehokas muunnelma lajitteluverkoista.
Bogosort	n	${\ displaystyle (n \ kertaa n!)}$	rajaton (tietty), (odotettu)${\ displaystyle (n \ kertaa n!)}$	1	Ei	Joo	Satunnainen sekoitus. Käytetään vain esimerkkitarkoituksiin, koska jopa odotettu paras tapausaika on kauhea.
Tyhmä lajittelu	${\ displaystyle n^{\ log 3/\ log 1.5}}$	${\ displaystyle n^{\ log 3/\ log 1.5}}$	${\ displaystyle n^{\ log 3/\ log 1.5}}$	n	Ei	Joo	Hitaampi kuin useimmat lajittelualgoritmit (jopa naiivit), joiden aikakompleksi on O ( n log 3 / log 1,5 ) = O ( n 2,7095 ... ) Voidaan tehdä vakaaksi, ja se on myös lajitteluverkko .
Hidas	${\ displaystyle n^{\ log n}}$	${\ displaystyle n^{\ log n}}$	${\ displaystyle n^{\ log n}}$	n	Ei	Joo	Kertoamis- ja antautumisalgoritmi, joka on vastakohta jakamis- ja valloitusalgoritmille .

Teoreettiset tietojenkäsittelytieteilijät ovat laatineet yksityiskohtaisia ​​muita lajittelualgoritmeja, jotka tarjoavat parempaa kuin O ( n log n ) -ajan monimutkaisuutta olettaen lisärajoituksia, mukaan lukien:

• Thorupin algoritmi , satunnaistettu algoritmi avainten lajittelemiseksi rajallisen kokoiselta alueelta ottaen O ( n log log n ) aikaa ja O ( n ) tilaa.
• Satunnaistettu kokonaislukujen lajittelualgoritmi, joka vie odotettua aikaa ja O ( n ) -tilaa.${\ displaystyle O \ vasen (n {\ sqrt {\ log \ log n}} \ oikea)}$

Suositut lajittelualgoritmit

Vaikka lajittelualgoritmeja on suuri määrä, käytännön toteutuksissa muutama algoritmi on hallitseva. Lisäyslajittelua käytetään laajalti pienissä tietojoukoissa, kun taas suurissa tietojoukoissa käytetään asymptoottisesti tehokasta lajittelua, pääasiassa kasanlajittelua, yhdistämislajittelua tai pikalähetystä. Tehokkaissa toteutuksissa käytetään yleensä hybridialgoritmia , joka yhdistää asymptoottisesti tehokkaan algoritmin yleiseen lajitteluun ja lisäyslajittelun pienille luetteloille rekursion alareunassa. Hyvin viritetyt toteutukset käyttävät kehittyneempiä muunnelmia, kuten Timsort (yhdistämis-, lisäys- ja lisälogiikka), joita käytetään Androidissa, Javassa ja Pythonissa, ja introsort (pikavalinta ja heapsort), joita käytetään (muunnelmissa) joissakin C ++ -lajikkeissa toteutukset ja .NET.

Rajoitetumpaan dataan, kuten lukuihin tietyllä aikavälillä, käytetään laajasti jakelulajeja , kuten laskenta- tai radix -lajittelu. Kuplan lajittelua ja muunnelmia käytetään harvoin käytännössä, mutta niitä esiintyy yleisesti opetuksessa ja teoreettisissa keskusteluissa.

Kun fyysisesti lajitellaan esineitä (kuten aakkosjärjestyksessä olevia papereita, testejä tai kirjoja), ihmiset käyttävät intuitiivisesti yleensä lisäyslajeja pienille sarjoille. Suuremmissa sarjoissa ihmiset käyttävät usein ensimmäistä ämpäriä, kuten alkukirjaimella, ja useat kauhat mahdollistavat erittäin suurten sarjojen käytännöllisen lajittelun. Usein tila on suhteellisen halpa, esimerkiksi levittämällä esineitä lattialle tai suurelle alueelle, mutta toiminnot ovat kalliita, etenkin kohteen siirtäminen kauas - vertailukohde on tärkeä. Yhdistämislajit ovat käytännöllisiä myös fyysisille kohteille, varsinkin kun voidaan käyttää kahta kättä, yksi kutakin luetteloa varten yhdistettäväksi, kun taas muut algoritmit, kuten kasa- tai pikalähetys, sopivat huonosti ihmisille. Muut algoritmit, kuten kirjastolajittelu , lisäyslajittelun variantti, joka jättää välilyöntejä, ovat myös käytännöllisiä fyysiseen käyttöön.

Yksinkertaisia ​​lajikkeita

Kaksi yksinkertaisinta lajiketta ovat lisäyslajittelu ja valintatyyppi, jotka molemmat ovat tehokkaita pienissä tiedoissa alhaisen yleiskustannuksen vuoksi, mutta eivät tehokkaita suurissa tiedoissa. Lisäyslajittelu on yleensä käytännössä nopeampaa kuin valinnan lajittelu, koska vertailut ovat vähäisempiä ja lähes lajiteltujen tietojen hyvä suorituskyky, ja siksi se on käytännössä edullista, mutta valintalajittelu käyttää vähemmän kirjoituksia, joten sitä käytetään silloin, kun kirjoitusteho on rajoittava tekijä.

Lisäyslajittelu

Lisäyslajittelu on yksinkertainen lajittelualgoritmi, joka on suhteellisen tehokas pienille ja enimmäkseen lajiteltuille luetteloille ja jota käytetään usein osana kehittyneempiä algoritmeja. Se toimii ottamalla elementit luettelosta yksi kerrallaan ja lisäämällä ne oikeaan paikkaan uuteen lajiteltuun luetteloon, joka on samanlainen kuin laitamme rahaa lompakkoomme. Taulukoissa uusi luettelo ja muut elementit voivat jakaa taulukon tilan, mutta lisäys on kallista, mikä edellyttää kaikkien seuraavien elementtien siirtämistä yksi kerrallaan. Shellsort (katso alla) on lisäyslajittelun muunnelma, joka on tehokkaampi suurille luetteloille.

Valinnan lajittelu

Valintatyyppi on paikan vertailulaji . Siinä on O ( n ² ) monimutkaisuutta, mikä tekee siitä tehottoman suurissa luetteloissa, ja se toimii yleensä huonommin kuin vastaava lisäyslaji . Valinnan lajittelu on tunnettu yksinkertaisuudestaan, ja sillä on myös suorituskykyetuja monimutkaisempiin algoritmeihin verrattuna tietyissä tilanteissa.

Algoritmi löytää vähimmäisarvon, vaihtaa sen ensimmäisen sijainnin arvoon ja toistaa nämä vaiheet luettelon loppuosassa. Se tekee enintään n vaihtosopimusta, joten se on hyödyllinen silloin, kun vaihtaminen on erittäin kallista.

Tehokkaita lajikkeita

Käytännölliset yleiset lajittelualgoritmit perustuvat lähes aina algoritmiin, jolla on keskimääräinen aika monimutkaisuus (ja yleensä pahimmassa tapauksessa monimutkaisuus) O ( n log n ), joista yleisimpiä ovat kasa-, yhdistämis- ja pikalähteet. Jokaisella on etuja ja haittoja, joista merkittävin on se, että yhdistämisen yksinkertainen toteutus käyttää O ( n ) lisätilaa, ja yksinkertaisen pikalähtöisen toteutuksen monimutkaisuus on O ( n ² ). Nämä ongelmat voidaan ratkaista tai parantaa monimutkaisemman algoritmin hinnalla.

Vaikka nämä algoritmit ovat asymptoottisesti tehokkaita satunnaisdatassa, käytännön tehokkuuden saavuttamiseksi reaalimaailman tiedoissa käytetään erilaisia ​​muutoksia. Ensinnäkin näiden algoritmien yleiskustannuksista tulee merkittäviä pienemmillä tiedoilla, joten usein käytetään hybridialgoritmia, joka yleensä siirtyy lisäyslajitteluun, kun tiedot ovat riittävän pieniä. Toiseksi algoritmit toimivat usein huonosti jo lajitellulla tai lähes lajitellulla datalla-nämä ovat yleisiä reaalimaailman tiedoissa, ja ne voidaan lajitella O ( n ) aikaan sopivilla algoritmeilla. Lopuksi ne voivat myös olla epävakaita , ja vakaus on usein haluttu ominaisuus. Näin ollen usein käytetään kehittyneempiä algoritmeja, kuten Timsort (perustuu yhdistämislajitteluun) tai introsort (joka perustuu pikalähteeseen, joka palaa takaisin kasaan).

Yhdistä lajittelu

Yhdistä lajittelu hyödyntää jo lajiteltujen luettelojen yhdistämisen helppoutta uuteen lajiteltuun luetteloon. Se alkaa vertaamalla jokaista kahta elementtiä (eli 1 ja 2, sitten 3 ja 4 ...) ja vaihtamalla ne, jos ensimmäinen tulee toisen jälkeen. Sitten se yhdistää jokaisen tuloksena olevan kahden luettelon neljään luetteloon, sitten yhdistää nämä neljän luettelot ja niin edelleen; kunnes viimein kaksi luetteloa yhdistetään lopulliseen lajiteltuun luetteloon. Tässä kuvatuista algoritmeista tämä on ensimmäinen, joka skaalautuu hyvin suuriin luetteloihin, koska sen pahin käyttöaika on O ( n log n ). Sitä voidaan myös helposti soveltaa luetteloihin, ei vain matriiseihin, koska se vaatii vain peräkkäisen pääsyn, ei satunnaista pääsyä. Sillä on kuitenkin lisää O ( n ) -tilan monimutkaisuutta, ja se sisältää suuren määrän kopioita yksinkertaisissa toteutuksissa.

Yhdistämisen lajittelu on saavuttanut suhteellisen hiljattain suosion käytännön toteutuksissa, koska se on käytetty kehittyneessä Timsort -algoritmissa , jota käytetään tavanomaisessa lajittelurutiinissa ohjelmointikielillä Python ja Java ( JDK7 ). Yhdistämislajittelu itsessään on muun muassa Perlin vakiorutiini , ja sitä on käytetty Javassa ainakin vuodesta 2000 lähtien JDK1.3: ssa .

Heapsort

Heapsort on paljon tehokkaampi versio valintalajikkeesta . Se toimii myös määrittämällä luettelon suurimman (tai pienimmän) elementin, sijoittamalla sen luettelon loppuun (tai alkuun) ja jatkamalla sitten muiden luettelon osien kanssa, mutta suorittaa tämän tehtävän tehokkaasti käyttämällä tietorakennetta, jota kutsutaan kasa , erityinen binaaripuu . Kun tietoluettelosta on tehty kasa, juurisolmu on taatusti suurin (tai pienin) elementti. Kun se poistetaan ja sijoitetaan luettelon loppuun, kasa järjestetään uudelleen niin, että suurin jäljellä oleva elementti siirtyy juureen. Kasan avulla seuraavan suurimman elementin löytäminen kestää O (log n ) aikaa O ( n ): n sijasta lineaarisessa skannauksessa, kuten yksinkertaisessa valintalajittelussa. Tämä mahdollistaa Heapsortin suorittamisen O ( n log n ): n aikana, ja tämä on myös pahin tapaus.

Pikavalinta

Quicksort on hajota ja hallitse algoritmi , joka nojautuu osion toiminta: osio array, elementti kutsutaan tappi valitaan. Kaikki saranaa pienemmät elementit siirretään ennen sitä ja kaikki suuret elementit siirretään sen jälkeen. Tämä voidaan tehdä tehokkaasti lineaarisessa ajassa ja paikallaan . Pienemmät ja suuret alaluettelot lajitellaan sitten rekursiivisesti. Tämä tuottaa O: n ( n log n ) keskimääräisen ajan monimutkaisuuden alhaisilla yleiskustannuksilla, joten tämä on suosittu algoritmi. Pikavalinnan tehokkaat toteutukset (joissa on osiointi paikan päällä) ovat tyypillisesti epävakaita ja hieman monimutkaisia, mutta ne ovat nopeimpia lajittelualgoritmeja käytännössä. Quicksort on yhdessä vaatimattoman O (log n ) -tilankäytön kanssa yksi suosituimmista lajittelualgoritmeista, ja se on saatavana monissa standardiohjelmointikirjastoissa.

Tärkeä varoitus pikavalinnasta on, että sen huonoin suorituskyky on O ( n ² ); Vaikka tämä on harvinaista, naiiveissa toteutuksissa (ensimmäisen tai viimeisen elementin valitseminen pivotiksi) tämä tapahtuu lajiteltujen tietojen osalta, mikä on yleinen tapaus. Pikavalinnan monimutkaisin ongelma on siten hyvän pivot -elementin valitseminen, koska jatkuvasti huonot pivot -valinnat voivat johtaa huomattavasti hitaampaan O ( n ² ) -suorituskykyyn, mutta hyvä pivot -valinta tuottaa O ( n log n ) -suorituskyvyn, joka on asymptoottisesti optimaalinen . Esimerkiksi, jos jokaisessa vaiheessa mediaani valitaan kääntöpisteeksi, algoritmi toimii kohdassa O ( n  log  n ). Mediaanin löytäminen, kuten mediaanien valintaalgoritmin mediaani, on kuitenkin O ( n ) -toiminto lajittelemattomilla luetteloilla ja vaatii siksi merkittäviä yleiskustannuksia lajittelulla. Käytännössä satunnaisnivelen valinta tuottaa lähes varmasti O ( n  log  n ) -suorituskyvyn.

Shellsort

Shellsort, eroaa kupla lajitella siitä, että se liikkuu elementtejä lukuisia vaihtamalla kantoja .

Shellsortin keksi Donald Shell vuonna 1959. Se parantaa lisäyslajittelua siirtämällä järjestyksessä olevia elementtejä pois useammasta kuin yhdestä paikasta kerrallaan. Shellsortin taustalla on ajatus, että lisäyslajittelu toimii ajassa, jolloin k on suurin etäisyys kahden ulkopuolisen elementin välillä. Tämä tarkoittaa, että yleensä ne toimivat muodossa O ( n ² ), mutta useimmiten lajiteltuihin tietoihin, joissa vain muutama elementti on paikoillaan, ne toimivat nopeammin. Joten lajittelemalla elementit ensin kaukana ja pienentämällä asteittain lajiteltujen elementtien välistä eroa, lopullinen lajittelu laskee paljon nopeammin. Yksi toteutus voidaan kuvata siten, että datasekvenssi järjestetään kaksiulotteiseen taulukkoon ja sitten lajitellaan taulukon sarakkeet käyttämällä lisäyslajittelua. ${\ displaystyle O (kn)}$

Shellsortin pahimman ajan monimutkaisuus on avoin ongelma ja riippuu käytetystä aukkosekvenssistä , jonka tunnetut monimutkaisuudet vaihtelevat O ( n ² ) -O ( n ^4/3 ) ja Θ ( n log ² n ). Tämä yhdistettynä siihen, että Shellsort on paikallaan , tarvitsee vain suhteellisen pieni määrä koodia, ja ei vaadi käyttöä kutsupino , tekee se on hyödyllinen tilanteissa, joissa muisti on arvossaan, kuten sulautettujen järjestelmien ja käyttöjärjestelmän ytimet .

Kuplan lajittelu ja muunnelmat

Kuplan lajittelu ja muunnokset, kuten Shellsort ja cocktail -lajittelu , ovat yksinkertaisia, erittäin tehottomia lajittelualgoritmeja. Ne näkyvät usein johdantokappaleissa analyysin helpottamisen vuoksi, mutta niitä käytetään harvoin käytännössä.

Kuplan lajittelu

Kuplan lajittelu, lajittelualgoritmi, joka seuraa jatkuvasti luetteloa ja vaihtaa kohteita, kunnes ne näkyvät oikeassa järjestyksessä.

Kuplan lajittelu on yksinkertainen lajittelualgoritmi. Algoritmi alkaa tietojoukon alusta. Se vertaa kahta ensimmäistä elementtiä, ja jos ensimmäinen on suurempi kuin toinen, se vaihtaa ne. Se jatkaa tämän tekemistä kullekin vierekkäisten elementtien parille tietojoukon loppuun asti. Sitten se alkaa uudelleen kahdella ensimmäisellä elementillä ja toistuu, kunnes viimeisen kierroksen aikana ei ole tapahtunut vaihtosopimuksia. Tämän algoritmin keskimääräinen aika ja huonoin tapaus on O ( n ² ), joten sitä käytetään harvoin suurten, järjestämättömien tietojoukkojen lajitteluun. Kuplan lajittelua voidaan käyttää pienen määrän kohteiden lajitteluun (jos sen asymptoottinen tehottomuus ei ole korkea rangaistus). Kuplan lajittelua voidaan käyttää tehokkaasti myös lähes lajiteltujen pituuksien luettelossa (eli elementit eivät ole merkittävästi paikoillaan). Esimerkiksi jos mikä tahansa määrä elementtejä on paikallaan vain yhdellä sijainnilla (esim. 0123546789 ja 1032547698), kuplalajin vaihto saa ne järjestykseen ensimmäisellä kerralla, toinen siirto löytää kaikki elementit järjestyksessä, joten lajittelu kestää vain 2 n aikaa.

Kampa lajitella

Kampa sort on suhteellisen yksinkertainen lajittelu algoritmi perustuu kupla lajitella ja alun perin suunnitellut Włodzimierz Dobosiewicz vuonna 1980. Myöhemmin uudestaan ja suosituksi Stephen Lacey ja Richard laatikko Byte lehden artikkeli julkaistiin huhtikuussa 1991. Perusajatuksena on poistaa kilpikonnia tai pieniä arvoja lähellä luettelon loppua, koska kuplalajittelussa nämä hidastavat lajittelua valtavasti. ( Kanit , suuret arvot luettelon alussa, eivät aiheuta ongelmia kuplien lajittelussa) Se saavuttaa tämän vaihtamalla aluksi elementtejä, jotka ovat tietyn etäisyyden päässä toisistaan ​​taulukossa, eikä vain vaihtamalla elementtejä, jos ne ovat vierekkäin toisiaan ja kutistetaan sitten valittua etäisyyttä, kunnes se toimii normaalina kuplalajikkeena. Jos siis Shellsortia voidaan pitää lisäyslajittelun yleisenä versiona, jossa elementit vaihdetaan tietyn etäisyyden päässä toisistaan, kampalajittelua voidaan ajatella samalla yleistyksellä, jota sovelletaan kuplalajitteluun.

Vaihda lajittelu

Exchange -lajittelu sekoitetaan joskus kuplalajitteluun, vaikka algoritmit ovat itse asiassa erilaisia. Vaihtolajittelu toimii vertaamalla ensimmäistä elementtiä kaikkiin sen yläpuolella oleviin elementteihin ja vaihtamalla tarvittaessa, mikä takaa, että ensimmäinen elementti on oikea lopulliseen lajittelujärjestykseen; sitten se tekee saman toisen elementin suhteen ja niin edelleen. Siitä puuttuu se etu, joka kuplalajittelulla on havaita yhdellä kertaa, jos luettelo on jo lajiteltu, mutta se voi olla nopeampi kuin kuplalajittelu vakiokertoimen (yksi siirto vähemmän lajiteltavien tietojen yli; puolet enemmän vertailuja) pahimmista tilanteista. Kuten mikä tahansa yksinkertainen O ( n ² ) -lajittelu, se voi olla kohtuullisen nopea hyvin pienillä tietojoukoilla, vaikka yleensä lisäyslajittelu on nopeampaa.

Jakelulaji

Jakelu lajitella viittaa mihin tahansa lajittelualgoritmi jossa data jaetaan niiden panos useita väli- rakenteita, jotka sitten kerätään ja sijoitetaan lähtö. Esimerkiksi sekä kauhan lajittelu että flashsort ovat jakelupohjaisia ​​lajittelualgoritmeja. Jakauman lajittelualgoritmeja voidaan käyttää yhdessä prosessorissa tai ne voivat olla hajautettuja algoritmeja , joissa yksittäiset osajoukot lajitellaan erikseen eri prosessoreilla ja yhdistetään sitten. Tämä mahdollistaa tietojen ulkoisen lajittelun, joka on liian suuri mahtuakseen yhden tietokoneen muistiin.

Laskeminen

Laskentalajittelu on sovellettavissa silloin, kun kunkin tulon tiedetään kuuluvan tietyn joukon, S , mahdollisuuksia. Algoritmi toimii O (| S | + n ) -ajalla ja O (| S |) -muistissa, jossa n on tulon pituus. Se toimii luomalla kokonaislukutaulukko | S | ja käyttäen i : nnen bin laskea esiintymät i : nnen jäsen S input. Jokainen tulo lasketaan lisäämällä vastaavan lokeron arvoa. Jälkeenpäin laskentataulukko silmukataan läpi kaikkien tulojen järjestämiseksi järjestyksessä. Tätä lajittelualgoritmia ei usein voida käyttää, koska S: n on oltava kohtuullisen pieni, jotta algoritmi olisi tehokas, mutta se on erittäin nopea ja osoittaa suurta asymptoottista käyttäytymistä n: n kasvaessa. Sitä voidaan myös muuttaa vakaan käyttäytymisen aikaansaamiseksi.

Kauhan lajittelu

Säiliölajittelu on jakamis- ja valloituslajittelualgoritmi, joka yleistää laskennallisen lajittelun jakamalla taulukon äärelliseen määrään ryhmiä. Kukin kauha lajitellaan sitten erikseen, joko käyttämällä eri lajittelualgoritmia tai käyttämällä rekursiivisesti kauhan lajittelualgoritmia.

Ryhmälajittelu toimii parhaiten, kun tietojoukon elementit on jaettu tasaisesti kaikkiin ryhmiin.

Radix -lajittelu

Radix -lajittelu on algoritmi, joka lajittelee numerot käsittelemällä yksittäisiä numeroita. n numeroa, jotka koostuvat k numerosta, lajitellaan O ( n · k ) aikaan. Radix -lajittelu voi käsitellä jokaisen numeron numeroita joko vähiten merkitsevästä numerosta (LSD) tai merkittävimmästä numerosta (MSD) alkaen. LSD -algoritmi lajittelee luettelon ensin vähiten merkitsevän numeron mukaan säilyttäen niiden suhteellisen järjestyksen käyttämällä vakaata lajittelua. Sitten se lajittelee ne seuraavan numeron mukaan ja niin edelleen vähiten merkitsevästä merkittävimpään, päätyen lajiteltuun luetteloon. Vaikka LSD -radiksilajittelu vaatii vakaan lajittelun, MSD -radiksilajittelualgoritmi ei (ellei haluta vakaata lajittelua). Paikan päällä oleva MSD-radix-lajittelu ei ole vakaa. Radix -lajittelu käyttää tavallisesti laskentalajittelualgoritmia sisäisesti. Hybridi lajittelu lähestymistapa, esimerkiksi käyttämällä lisäyslajittelun Pienten siilojen, parantaa suorituskykyä kantalukulajittelu merkittävästi.

Muistin käyttötavat ja hakemistojen lajittelu

Kun lajiteltavan taulukon koko lähestyy tai ylittää käytettävissä olevan ensisijaisen muistin, joten (paljon hitaampaa) levy- tai vaihtotilaa on käytettävä, lajittelualgoritmin muistin käyttömallista tulee tärkeä ja algoritmi, joka on saattanut olla kohtuullinen tehokas, kun matriisi mahtuu helposti RAM -muistiin, voi tulla epäkäytännölliseksi. Tässä skenaariossa vertailujen kokonaismäärä muuttuu (suhteellisen) vähemmän tärkeäksi, ja kuinka monta kertaa muistin osat on kopioitava tai vaihdettava levylle ja levyltä, voivat hallita algoritmin suorituskykyominaisuuksia. Siten siirtojen määrä ja vertailujen lokalisointi voivat olla tärkeämpiä kuin vertailujen raaka määrä, koska lähellä olevien elementtien vertailut toisiinsa tapahtuvat järjestelmäväylän nopeudella (tai välimuistilla jopa suorittimen nopeudella). levyn nopeuteen, on lähes hetkellinen.

Esimerkiksi suosittu rekursiivinen pikanäppäinalgoritmi tarjoaa kohtuullisen suorituskyvyn riittävällä RAM -muistilla, mutta koska rekursiivinen tapa kopioi taulukon osia, siitä tulee paljon vähemmän käytännöllinen, kun ryhmä ei sovi RAM -muistiin, koska se voi aiheuttaa useita hidas kopiointi- tai siirtotoiminto levylle ja levyltä. Tässä skenaariossa toinen algoritmi voi olla parempi, vaikka se vaatisi enemmän kokonaisvertailuja.

Yksi tapa kiertää tämä ongelma, joka toimii hyvin, kun monimutkaiset tietueet (kuten relaatiotietokanta ) lajitellaan suhteellisen pienellä avainkentällä, on luoda indeksi taulukkoon ja lajitella sitten indeksi koko matriisi. (Koko taulukon lajiteltu versio voidaan sitten tuottaa yhdellä kerralla indeksin lukemalla, mutta usein sekin on tarpeetonta, koska lajiteltu indeksi on riittävä.) Koska indeksi on paljon pienempi kuin koko taulukko, se voi mahtuu helposti muistiin, missä koko ryhmä ei, ja poistaa tehokkaasti levynvaihto-ongelman. Tätä menettelyä kutsutaan joskus "tunnistelajitteluksi".

Toinen tekniikka muistin kokoongelman ratkaisemiseksi on ulkoisen lajittelun käyttäminen , esimerkiksi yksi tapa on yhdistää kaksi algoritmia tavalla, joka hyödyntää kunkin vahvuuksia parantaakseen yleistä suorituskykyä. Taulukko voidaan esimerkiksi jakaa osiin, joiden koko vastaa RAM -muistia, kunkin palan sisältö lajitellaan tehokkaalla algoritmilla (kuten pikalähetys ) ja tulokset yhdistetään käyttämällä k -way -yhdistämistä, joka on samanlainen kuin yhdistä lajittelu . Tämä on nopeampaa kuin yhdistää tai lajitella koko luettelo.

Tekniikoita voi myös yhdistää. Jotta voidaan lajitella erittäin suuria tietomääriä, jotka ylittävät huomattavasti järjestelmämuistin, jopa indeksi on ehkä lajiteltava käyttämällä algoritmia tai algoritmien yhdistelmää, joka on suunniteltu toimimaan kohtuullisesti virtuaalimuistin kanssa , eli vähentämään tarvittavaa vaihtamista.

Aiheeseen liittyvät algoritmit

Aiheeseen liittyviä ongelmia ovat osittainen lajittelu (vain luettelon k pienimmän elementin lajittelu tai vaihtoehtoisesti k pienimmän, mutta järjestämättömän elementin laskeminen) ja valinta ( k : n pienimmän elementin laskeminen ). Nämä voidaan ratkaista tehottomasti kokonaislajittelulla, mutta on olemassa tehokkaampia algoritmeja, jotka usein johdetaan yleistämällä lajittelualgoritmi. Merkittävin esimerkki on QuickSelect- , joka liittyy quicksort . Päinvastoin, jotkut lajittelualgoritmit voidaan johtaa soveltamalla valintaalgoritmia toistuvasti; quicksort ja quickselect voidaan nähdä samalla kääntyvällä liikkeellä, ja ne eroavat toisistaan ​​vain sen suhteen, toistetaanko molemmin puolin (pikanäkymä, jaa ja valloita ) vai toisella puolella (pikavalinta, vähennys ja valloitus ).

Eräänlainen lajittelualgoritmin vastakohta on sekoitusalgoritmi . Nämä ovat pohjimmiltaan erilaisia, koska ne edellyttävät satunnaislukujen lähdettä. Sekoitus voidaan toteuttaa myös lajittelualgoritmilla, nimittäin satunnaisella lajittelulla: määrittämällä satunnaisluku jokaiselle luettelon elementille ja lajittelemalla sitten satunnaislukujen perusteella. Tätä ei kuitenkaan yleensä tehdä käytännössä, ja sekoittamiseen on tunnettu yksinkertainen ja tehokas algoritmi: Fisher-Yates-sekoitus .

Katso myös

• Lajittelu  - Kirjallisten tietojen kokoaminen vakiotilaukseen
• Schwartzian muutos
• Hakualgoritmi  - Mikä tahansa algoritmi, joka ratkaisee hakuongelman
• Quantum sort  - Lajittelualgoritmit kvanttitietokoneille

Viitteet

Lue lisää

• Knuth, Donald E. (1998), Sorting and Searching , The Art of Computer Programming, 3 (2. painos), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), "Efficient Sorting by Computer: An Introduction", Computational Probability , New York: Academic Press, s.  101–130 , ISBN 0-12-394680-8

Ulkoiset linkit

• Lajittelualgoritmi Animaatiot klo Wayback Machine (arkistoitu 03 maaliskuu 2015).
• Peräkkäiset ja rinnakkaislajittelualgoritmit - Selitykset ja analyysit monista lajittelualgoritmeista.
• Algoritmien, tietorakenteiden ja ongelmien sanakirja - Algoritmien, tekniikoiden, yhteisten toimintojen ja ongelmien sanakirja.
• Hieman skeptinen näkemys lajittelualgoritmeista - Keskustelee useista klassisista algoritmeista ja suosittelee vaihtoehtoja pikalähetysalgoritmille .
• 15 lajittelualgoritmia 6 minuutissa (Youtube) - 15 lajittelualgoritmin visualisointi ja "audibilisaatio" 6 minuutissa.
• A036604 -sekvenssi OEIS -tietokannassa otsikolla "Lajittelunumerot: minimaalinen määrä vertailuja, joita tarvitaan n elementin lajitteluun" - Suorittaa Ford -Johnsonin algoritmi .
• Kuuluisissa maalauksissa käytetyt lajittelualgoritmit (Youtube) - Lajittelualgoritmien visualisointi monissa kuuluisissa maalauksissa.
• A Lajittelualgoritmien vertailu - Suorittaa yhdeksän tärkeimmän lajittelualgoritmin testisarjan Python timeitin ja Google Colabin avulla.