Radix lajitella

radix lajitella
Tekijä	Hollerith, Herman
tarkoitus	Lajittelualgoritmi
Tietorakenne	joukko
pahin aika	, jossa w on kunkin avaimen tallentamiseen tarvittavien bittien määrä.
Muistin hinta
Mediatiedostot Wikimedia Commonsissa

Bittikohtainen lajittelu ( eng.  radix sort ) on lajittelualgoritmi, joka toimii lineaarisessa ajassa. On olemassa vakaita vaihtoehtoja.

Algoritmi

Aluksi tarkoitettu numeroiksi kirjoitettujen kokonaislukujen lajitteluun. Mutta koska tietokoneiden muistiin kaikki tiedot tallennetaan kokonaislukuina, algoritmi soveltuu lajittelemaan kaikki objektit, joiden tietue voidaan jakaa vertailukelpoisia arvoja sisältäviin "numeroihin". Esimerkiksi tällä tavalla voit lajitella paitsi numerosarjana kirjoitettuja numeroita, myös merkkijonoja, jotka ovat merkkijoukkoa, ja yleensä mielivaltaisia ​​arvoja muistissa, jotka esitetään tavujoukona.

Vertailu suoritetaan bitti kerrallaan: ensin verrataan yhden äärinumeron arvoja ja elementit ryhmitellään tämän vertailun tulosten mukaan, sitten verrataan seuraavan viereisen numeron arvoja ja elementit järjestetään joko tämän numeron arvojen vertailun tulosten perusteella edellisessä läpimenossa muodostettujen ryhmien sisällä tai ne järjestetään uudelleen kokonaisuutena, mutta säilytetään edellisellä lajittelulla saavutettu suhteellinen järjestys. Sitten sama tehdään seuraavalle purkamiselle ja niin edelleen loppuun asti.

Koska vertailtuja tietueita on mahdollista kohdistaa toisiinsa nähden eri suuntiin, on käytännössä kaksi vaihtoehtoa tälle lajittelulle. Numeroille niitä kutsutaan luvun numeroiden merkityksen perusteella, ja se käy näin: voit kohdistaa numeroiden syötteet vähemmän merkitseviin numeroihin (oikealla puolella kohti ykkösiä, pienin merkitsevä numero, LSD ) tai useampia merkitseviä numeroita (vasemmalla, merkitsevistä numeroista, merkittävin numero, MSD).

LSD-lajittelulla (lajittelu tasataan pienimmän merkitsevän numeron mukaan, oikealle, ykkösiin) saadaan numeroille sopiva järjestys. Esimerkiksi: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Eli tässä arvot lajitellaan ensin ykkösten mukaan, sitten lajitellaan kymmenien mukaan, jolloin lajittelu ykkösten mukaan pidetään sisällä kymmeniä, sitten satoja, pitäen lajittelun kymmenien ja yksiköiden sadoissa jne.

MSD-lajittelu (korkea järjestys, vasemmalle tasattu) johtaa aakkosjärjestykseen, joka sopii tekstirivien lajitteluun. Esimerkiksi "b, c, d, e, f, g, h, i, j, ba" lajitellaan muodossa "b, ba, c, d, e, f, g, h, i, j". Jos MSD:tä käytetään esimerkissä annettuihin lukuihin, saadaan sekvenssi 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Voit kerätä tietoa ryhmistä kussakin passissa eri tavoilla - esimerkiksi listoihin, puihin, taulukoihin kirjoittamalla joko itse elementit tai niiden indeksit jne.

Rekursiivisesta bittikohtaisesta lajittelusta on epävakaa versio, joka suoritetaan suoraan lajiteltuun taulukkoon: ensimmäisellä kerralla liike menee toisiaan kohti, taulukon alussa haetaan elementtiä, jonka ensimmäisessä bittinumerossa on 1, taulukon lopussa etsitään elementtiä, jossa on 0 samassa numerossa. Löydetyt elementit vaihdetaan ja niin edelleen, kunnes kyseiset indeksit kohtaavat. Siten taulukon alkuun, ennen indeksien kohtaamispistettä kerätään kaikki alkiot, joiden bitti on yhtä suuri kuin 0, ja tämän indeksin jälkeen kaikki alkiot, joiden bitti on yhtä suuri kuin 1. Sitten voit rekursiivisesti täysin samalla tavalla iteroi taulukon tuloksena olevat alialueet, vertaa toisen ja sitä seuraavien bittien arvoja ja järjestä elementtien paikat uudelleen.

Hakemus korilajitteluvaihtoehdon riveille

Korilajittelulla voidaan lajitella sijoituksen mukaan . Jokainen kategoria ajetaan kahdesti. Ensimmäisellä ajokerralla lasketaan tiettyjen arvojen määrä tässä luokassa. Sitten kullekin mahdolliselle arvolle valmistetaan taulukot tallentamaan kyseisellä arvolla olevat elementit. Toisen läpimenon aikana itse elementit kirjoitetaan näihin matriisiin. Tehokas toteutus on mahdollista käyttämällä merkkijonoviittausten joukkoa itse merkkijonojen sijasta ja ylimääräistä "säiliökokojen" joukkoa, joka alustetaan ensimmäisessä läpiviennissä kunkin "bin" elementtien lukumäärällä.

Toinen ja sitä seuraavat siirrot suoritetaan erikseen jokaiselle edellisellä ajolla saadulle korille jakamalla se "alikoreihin" ja vertaamalla merkkijonojen toista ja myöhempiä merkkejä.

Toiminto päättyy, kun merkkijonon enimmäispituus saavutetaan tai kun kaikkien "alikorien" pituus on 1.

Muistiinpanot

Kirjallisuus

• Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Lajittelu ja haku. - 2. painos - M . : "Williams" , 2007. - S. 192-201. — ISBN 5-8459-0082-4 .

Linkit

• Visualizer1  on Java-sovelma.
• Visualizer2  on Java-sovelma.
• Algoritmin käyttöönotto C++:ssa Arkistoitu 27. heinäkuuta 2019 Wayback Machinessa .