Innhold
Å bestille et sett med elementer i en liste er en hyppig oppgave i programmeringen. Ofte kan et menneske utføre denne oppgaven intuitivt. Et dataprogram må imidlertid følge en nøyaktig sekvens av instruksjoner for å fullføre den, og den sekvensen kalles en algoritme. En bestillingsalgoritme er en metode som brukes til å plassere en liste over uorganiserte varer i en gitt ordre. Bestillingssekvensen bestemmes av en nøkkel. Det er flere sorteringsalgoritmer som varierer med hensyn til effektivitet og ytelse. Noen kjente og viktige av denne typen inkluderer: boblesortering, utvalgssortering, innsettingssortering og rask sortering.
Boblesortering
Boblesorteringen utveksler gjentatte ganger tilstøtende elementer som ikke er i orden før hele varelisten er i rekkefølge. På denne måten flyter elementene i listen i henhold til deres verdier, med den største (i tilfelle økende sortering) som går til slutten på slutten av hver iterasjon.
Den største fordelen med denne algoritmen er at implementeringen er enkel og kjent. I tillegg, i boblesorteringen, endres elementene uten å bruke midlertidig lagring, noe som gjør plassbehovet minimalt. Den største ulempen er at den ikke viser gode resultater når listen inneholder mange gjenstander. Dette er fordi denne typen sortering krever n² prosesseringstrinn for hvert n antall elementer som skal sorteres. Derfor er boblesorteringen egnet for akademisk utdanning, men ikke for virkelige applikasjoner.
Valg sorter
Utvalget sorterer gjentatte ganger i listen over elementer, velger ett element om gangen og plasserer det i riktig posisjon i sekvensen.
Hovedfordelen med utvalgssortering er at den fungerer bra på en kort liste. I tillegg, siden det er en bestillingsalgoritme, trenger den ikke midlertidig lagring utover det som er nødvendig for å lagre den opprinnelige listen. Den største ulempen er den lave effektiviteten på store lister. I likhet med boblesorteringen krever det et antall trinn for hvert n-element. I tillegg påvirkes ytelsen lett av den opprinnelige rekkefølgen på varene før sorteringsprosessen. På grunn av dette er denne valgtypen bare egnet for en liste der få elementer er i tilfeldig rekkefølge.
Sortering av innsetting
Innsettingssorten skanner listen gjentatte ganger og setter inn et element fra den uordnede sekvensen i riktig posisjon hver gang.
Den største fordelen med å sortere etter innsetting er enkelheten, i tillegg til å vise god ytelse i små lister. Det er en bestillingsalgoritme, så plassbehovet er minimalt. Ulempen er at den ikke fungerer like bra som andre sorteringsalgoritmer. Med trinn som er nødvendige for å fungere, fungerer innsettingssorteringen heller ikke bra med store lister. Det er imidlertid spesielt nyttig med lister med få ting.
Rask sortering
Rask sortering fungerer på prinsippet om deling og erobring. Først deler den varelisten i to underlister basert på et pivotelement. Alle elementene i den første underlisten er ordnet slik at de er mindre enn pivoten, mens alle elementene i den andre underlisten er ordnet slik at de er større enn pivoten. Den samme partisjonerings- og organisasjonsprosessen utføres gjentatte ganger på de resulterende underlistene til hele listen er organisert.
Rask sortering anses av noen å være den beste sorteringsalgoritmen på grunn av dens betydelige effektivitetsfordel, da den fungerer bra med en stor liste over varer. Ved bestilling på stedet er det heller ikke behov for ekstra lagringsplass. Den lille ulempen den gir, er at dens dårligste ytelse er lik den gjennomsnittlige ytelsen til de andre algoritmene beskrevet ovenfor. Det er imidlertid viktig å merke seg at denne verste saken er svært sjelden. Mer generelt gir rask sortering den mest effektive og mest brukte metoden for å organisere en liste av alle størrelser.
