Programerji, ki preidejo z osebnega in spletnega razvoja na kodiranje za mobilne naprave ali vgrajene sisteme, ugotovijo, da več časa porabijo za izbiro in kodiranje lastnih podatkovnih struktur in algoritmov. Z manj pomnilnika in omejenim shranjevanjem podatkov ni prostora za vnaprej zgrajene knjižnice ali okvire. Za tiste, ki morajo napisati svoje lastne rutine razvrščanja, je tukaj nekaj premislekov o izbiri nizke razvrščanja z mehurčki.
Ozadje
Razvrščanje z mehurčki je preprost algoritem, ki razvrsti seznam elementov v pomnilniku. Glede na matriko koda večkrat primerja vsak par sosednjih elementov in jih zamenja, če niso v redu. Postopek se ponavlja, dokler ne pride več do zamenjav. Če bi si bilo mogoče ogledati matriko, medtem ko je razvrščanje v teku, bi nizke vrednosti "mehurčkale" na vrh, velike vrednosti pa bi padle na dno. Tukaj je ustrezna koda v Visual Basicu 2010:
Video dneva
Medtem ko zamenjava = True Swap = False Za i = 0 Do tbl.length - 2 Če tbl (i) > tbl (i + 1) Potem je tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = zamenjava tmp = True End, če naslednji konec Medtem
Kdaj izbrati razvrščanje z mehurčki
Ta algoritem ima več prednosti. Enostavno ga je napisati, enostavno je razumeti in zahteva le nekaj vrstic kode. Podatki so razvrščeni na mestu, tako da je malo pomnilnika in ko so razvrščeni, so podatki v pomnilniku, pripravljeni za obdelavo. Glavna pomanjkljivost je čas, potreben za sortiranje. Povprečni čas narašča skoraj eksponentno, ko se povečuje število elementov tabele. Za razvrščanje desetkrat večjega števila predmetov je potrebno skoraj stokrat dlje.
Druge vrste nizov
Algoritmi za razvrščanje se razlikujejo po zapletenosti, hitrosti in stroških. Razvrstitev mehurčkov je najmanj zapletena, a tudi ena najpočasnejših. Druge vrste, ki temeljijo na matrikah, kot sta vstavljanje in izmenjava, so nekoliko hitrejše, vendar zahtevajo več kode (glejte spodnje reference). Glavna prednost vrst, ki temeljijo na matrikah, je, da uporabljajo najmanj kode in zavzamejo najmanj delovnega pomnilnika. Razmislite o teh vrstah za preproste nize z manj kot nekaj sto elementi.
Kompleksni algoritmi razvrščanja
Večji nabori podatkov zahtevajo bolj zapleteno kodo in več pomnilnika. Hitro razvrščanje in razvrščanje kopice tako razdelita kot kopirata nabore podatkov za optimizacijo števila primerjav. Hitro razvrščanje nenehno razdeli seznam, nato pa ga ponovno sestavi v razvrščenem vrstnem redu. Razvrščanje kopice kopira podatke v drevesno strukturo, nato pa prečka drevo, da kopira podatke nazaj v vrstni red. Oba sta hitra in učinkovita, vendar zahtevata več kode in veliko več delovnega prostora za shranjevanje. Izberite te algoritme za velike nabore podatkov.
