Indhold
Bestilling af et sæt emner på en liste er en hyppig opgave ved programmering. Ofte kan et menneske udføre denne opgave intuitivt. Dog skal et computerprogram følge en nøjagtig sekvens af instruktioner for at fuldføre det, og denne sekvens kaldes en algoritme. En bestillingsalgoritme er en metode, der bruges til at placere en liste over uorganiserede varer i en given ordre. Bestillingssekvensen bestemmes af en nøgle. Der er flere sorteringsalgoritmer, der adskiller sig med hensyn til effektivitet og ydeevne. Nogle kendte og vigtige af denne type inkluderer: boblesortering, valgsortering, indsættelsessortering og hurtig sortering.
Boblesortering
Boblesorteringen udveksler gentagne gange tilstødende elementer, der ikke er i orden, indtil hele listen over varer er i rækkefølge. På denne måde flyder varerne på listen i henhold til deres værdier, hvor den største (i tilfælde af stigende sortering) går til slutningen i slutningen af hver iteration.
Den største fordel ved denne algoritme er, at dens implementering er let og kendt. Derudover ændres elementerne i boblesorteringen steder uden brug af midlertidig opbevaring, hvilket gør pladsbehovet minimalt. Den største ulempe er, at det ikke viser gode resultater, når listen indeholder mange emner. Dette skyldes, at denne type sortering kræver n²-behandlingstrin for hvert n antal elementer, der skal sorteres. Derfor er boblesorteringen velegnet til akademisk uddannelse, men ikke til applikationer i det virkelige liv.
Valg sortering
Valgssorteringen søger gentagne gange på listen over emner, vælger et element ad gangen og placerer det i den rigtige position i sekvensen.
Den største fordel ved valg af sortering er, at den fungerer godt på en kort liste. Derudover, da det er en algoritme til bestilling af steder, behøver den ikke midlertidig opbevaring ud over hvad der er nødvendigt for at gemme den oprindelige liste. Den største ulempe er dens lave effektivitet på store lister. Ligesom boblesorteringen kræver det n² antal trin for hvert n-element. Derudover påvirkes dets ydeevne let af den oprindelige rækkefølge på varerne før sorteringsprocessen. På grund af dette er denne valgtype kun egnet til en liste, hvor få elementer er i tilfældig rækkefølge.
Indsættelse sortering
Indsættelsessorteringen scanner listen gentagne gange og indsætter hver gang et element fra den uordnede sekvens i den rigtige position.
Den største fordel ved sortering efter indsættelse er dens enkelhed ud over at vise god ydeevne på små lister. Det er en placeringsalgoritme, så pladsbehovet er minimalt. Ulempen er, at den ikke fungerer så godt som andre sorteringsalgoritmer. Med n² trin, der er nødvendige for at arbejde, fungerer indsættelsessorteringen heller ikke godt med store lister. Det er dog især nyttigt med lister over få ting.
Hurtig sortering
Hurtig sortering fungerer på princippet om deling og erobring. For det første opdeler det artikellisten i to underlister baseret på et drejelement. Alle elementer i den første underliste er arrangeret, så de er mindre end pivoten, mens alle elementer i den anden underliste er arrangeret til at være større end pivot. Den samme partitionerings- og organisationsproces udføres gentagne gange på de resulterende underlister, indtil hele listen er organiseret.
Hurtig sortering anses af nogle for at være den bedste sorteringsalgoritme på grund af dens betydelige effektivitetsfordel, da den fungerer godt sammen med en stor liste over varer. Ved bestilling på stedet er der heller ikke behov for ekstra lagerplads. Den lille ulempe, den udgør, er, at dens dårligste ydeevne svarer til gennemsnittets ydeevne for de andre algoritmer, der er beskrevet ovenfor. Det er dog vigtigt at bemærke, at dette værste tilfælde er meget sjældent. Mere generelt producerer hurtig sortering den mest effektive og udbredte metode til at organisere en liste af enhver størrelse.