Prednosti in slabosti Bubble Sort
Programerji, ki preklopijo 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 ogrodja. Za tiste, ki morajo napisati svoje lastne rutine razvrščanja, je tukaj nekaj premislekov o izbiri razvrščanja z majhnimi mehurčki.
Ozadje
Razvrščanje z mehurčki je preprost algoritem, ki razvršča seznam elementov v pomnilniku. Glede na matriko koda vedno znova primerja vsak par sosednjih elementov in jih zamenja, če niso v redu. Postopek se ponavlja, dokler ni več zamenjav. Če bi bilo možno videti matriko, medtem ko poteka razvrščanje, bi nizke vrednosti "poskočile" na vrh, medtem ko bi velike vrednosti potonile na dno. Tukaj je ustrezna koda v Visual Basicu 2010:
Medtem ko je swap =True swap =False For i =0 To tbl.length - 2 If tbl(i)> tbl(i + 1) Potem tmp =tbl(i) tbl(i) =tbl(i + 1) tbl(i + 1) =tmp swap =True End If Next End While
Kdaj izbrati razvrstitev mehurčkov
Ta algoritem ima več prednosti. Je preprost za pisanje, enostaven za razumevanje in potrebuje le nekaj vrstic kode. Podatki so razvrščeni na mestu, tako da je malo obremenitev pomnilnika in ko so razvrščeni, so podatki v pomnilniku, pripravljeni za obdelavo. Glavna pomanjkljivost je čas, ki je potreben za sortiranje. Povprečni čas narašča skoraj eksponentno, ko se povečuje število elementov tabele. Razvrščanje desetkrat večjega števila predmetov traja skoraj stokrat več časa.
Druge vrste matrik
Algoritmi za razvrščanje se razlikujejo po kompleksnosti, hitrosti in stroških. Razvrščanje z mehurčki je najmanj zapleteno, a tudi eno najpočasnejših. Druga razvrščanja, ki temeljijo na nizu, kot sta razvrščanje z vstavljanjem in razvrščanje z izmenjavo, so nekoliko hitrejša, vendar zahtevajo več kode (glejte spodnje reference). Glavna prednost razvrščanja na osnovi nizov 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 za razvrščanje
Večji nizi podatkov zahtevajo bolj zapleteno kodo in več pomnilnika. Hitro razvrščanje in razvrščanje na kup razdelita in kopirata nabore podatkov, da optimizirata število primerjav. Hitro razvrščanje nenehno razdeli seznam in ga nato znova sestavi v razvrščenem vrstnem redu. Razvrščanje kopice kopira podatke v drevesno strukturo in nato 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. Izberite te algoritme za velike nabore podatkov.