Ohjelmoijat, jotka vaihtavat PC- ja verkkokehityksestä mobiililaitteiden tai sulautettujen järjestelmien koodaukseen, huomaavat, että omien tietorakenteiden ja algoritmien valitsemiseen ja koodaamiseen kuluu enemmän aikaa. Vähemmän muistia ja rajoitettua tiedontallennustilaa ei ole tilaa valmiille kirjastoille tai kehyksille. Joten niille, joiden on kirjoitettava omat lajittelurutiinit, tässä on joitain huomioita matalan kuplalajittelun valinnassa.
Tausta
Kuplalajittelu on yksinkertainen algoritmi, joka lajittelee luettelon muistissa olevista kohteista. Kun annetaan taulukko, koodi vertaa toistuvasti jokaista vierekkäisten kohteiden paria ja vaihtaa ne, jos ne eivät ole järjestyksessä. Prosessi toistuu, kunnes vaihtoja ei enää tapahdu. Jos taulukkoa olisi mahdollista tarkastella lajittelun aikana, pienet arvot "kuplisivat" ylös, kun taas suuret arvot vajosivat alas. Tässä on asiaankuuluva koodi Visual Basic 2010:ssä:
Päivän video
Vaikka swap = todellinen swap = epätosi i = 0 tbl.pituuteen - 2 Jos tbl (i) > tbl (i + 1) Sitten tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End While
Milloin kuplalajittelu kannattaa valita
Tällä algoritmilla on useita etuja. Se on helppo kirjoittaa, helppo ymmärtää ja se vie vain muutaman rivin koodia. Tiedot lajitellaan paikoilleen, joten muistia on vähän, ja kun tiedot on lajiteltu, ne ovat muistissa valmiina käsittelyyn. Suurin haittapuoli on lajitteluun kuluva aika. Keskimääräinen aika kasvaa lähes eksponentiaalisesti taulukon elementtien määrän kasvaessa. Kymmenkertainen määrä tavaroita lajittelussa kestää lähes sata kertaa kauemmin.
Muut taulukkolajit
Lajittelualgoritmit vaihtelevat monimutkaisuuden, nopeuden ja yleiskustannusten suhteen. Kuplalajittelu on vähiten monimutkainen, mutta myös yksi hitaimpia. Muut taulukkopohjaiset lajittelut, kuten lisäyslajittelu ja vaihtolajittelu, ovat hieman nopeampia, mutta vievät enemmän koodia (katso alla olevat viitteet). Taulukkopohjaisten lajittelujen tärkein etu on, että ne käyttävät vähiten koodia ja vievät vähiten työmuistia. Harkitse näitä yksinkertaisia taulukoita, joissa on alle muutama sata kohdetta.
Monimutkaiset lajittelualgoritmit
Suuremmat tietojoukot vaativat monimutkaisempaa koodia ja enemmän muistia. Pikalajittelu ja kasalajittelu sekä jakavat että kopioivat tietojoukot vertailujen määrän optimoimiseksi. Pikalajittelu jakaa luettelon jatkuvasti ja kokoaa sen sitten uudelleen lajiteltuun järjestykseen. Keon lajittelu kopioi tiedot puurakenteeseen ja kulkee sitten puun läpi kopioidakseen tiedot takaisin järjestykseen. Molemmat ovat nopeita ja tehokkaita, mutta vievät enemmän koodia ja paljon toimivampaa tallennustilaa. Valitse nämä algoritmit suurille tietojoukoille.
