Nøgleforskel – Indsættelsessortering versus udvalgssortering
Indsættelsessortering og udvælgelsessortering er to sorteringsalgoritmer, der bruges til at sortere en samling af data. Nogle gange er det nødvendigt at arrangere data i en bestemt rækkefølge. Sorteringsalgoritmer er mekanismer til at sortere et sæt data. Ved sortering er dataene ordnet efter en numerisk eller en leksikografisk rækkefølge. Hvis dataene er sorteret korrekt, ville det være nemt at søge data hurtigere. Hvis telefonnumrene i en telefonbog ikke er sorteret, så ville det være svært at finde et specifikt telefonnummer. På samme måde, hvis ordene i ordbogen ikke er ordnet i alfabetisk rækkefølge, ville det være meget svært at finde ord. Derfor er sortering nyttig i dagligdagen. I datalogi findes der sorteringsalgoritmer til at sortere en samling af data. To sådanne algoritmer er indsættelsessortering og udvælgelsessortering. Indsættelsessorteringen er sorteringsalgoritmen, der sorterer arrayet ved at flytte elementer et efter et. Udvælgelsessortering er den sorteringsalgoritme, der finder det mindste element i arrayet og udveksler elementet med den første position, find derefter det næstmindste element og udskift det med elementet i den anden position og fortsætter processen, indtil hele arrayet er sorteret. Den vigtigste forskel mellem indsættelsessortering og udvælgelsessortering er, at indsættelsessortering sammenligner to elementer ad gangen, mens udvælgelsessortering vælger minimumselementet fra hele arrayet og sorterer det.
Hvad er indsættelsessortering?
Indsættelsessortering er en på stedet sammenligningsbaseret sorteringsalgoritme. I denne metode søges arrayet trin for trin. De usorterede elementer flyttes og indsættes i arrayets sorterede underliste. Indsættelsessorteringsalgoritmen kan forklares ved hjælp af følgende eksempel.
Tag f.eks. den indledende matrix som 77, 33, 44, 11, 88. I denne sorteringsalgoritme er det første trin at vælge det aktuelle element.
Det aktuelle element er 77. Det aktuelle element sammenlignes med alle elementer i venstre side. 77'eren er det første element, og der er ingen elementer på venstre side. Indekset for den aktuelle position er 0.
Så øges indekset for den aktuelle position med 1. Nu er indekset 1, og det aktuelle element er 33. Når man sammenligner det med elementet til venstre, er det mindre end 77. Så er begge disse værdier er byttet. Nu er 33 i indeks 0, og 77 er i indeks1.
Nu er arrayet 33, 77, 44, 11, 88.
Igen er indekset øget. Indekset er 2, og det aktuelle element er 44. Det sammenlignes med elementerne i venstre side. 44 er mindre end 77. Så disse to værdier er byttet om. Nu er arrayet 33, 44, 77, 11, 88. Det er nødvendigt at sammenligne alle elementer til venstre. Så 44'eren sammenlignes med 33. 33 er mindre end 44. Så disse elementer skal ikke udveksles.
Nu er arrayet 33, 44, 77, 11, 88.
Igen er indekset øget. Indekset er 3, og det aktuelle element er 11. Det sammenlignes med alle elementer i venstre. 11 er mindre end 77, så de to er byttet om. Nu er arrayet 33, 44, 11, 77, 88. Når man sammenligner 11 og 44, er 11 mindre end 44. Så disse to er byttet om. Nu er arrays 33, 11, 44, 77, 88. Igen sammenlignes 11 med 33. 11 er mindre end 33, så disse to værdier er byttet om.
Nu er arrayet 11, 33, 44, 77, 88.
Forøgelse af indekset vil gøre indekset til 4. Værdien er 88. Den er højere end 77. Så der er ikke behov for at bytte. Endelig er det sorterede array 11, 33, 44, 77, 88.
Figur 01: Eksempel på indsættelsessortering
Implementeringen af indsættelsessorteringen er som ovenfor. Det oprindelige array var 77, 33, 44, 11, 88. Efter sortering giver det outputtet 11, 33, 44, 77, 88.
Hvad er udvalgssortering?
Selection sort er en in-place sammenligning-baseret sorteringsalgoritme. Arrays er opdelt i sektioner. Den sorterede del er i venstre ende. Den usorterede del er i højre ende. Først skal den mindste værdi findes. Så er det byttet med det venstre element. Nu er det element i det sorterede array. Denne proces fortsætter med at flytte usorteret matrixgrænse fra ét element til højre. Valgsorteringsalgoritmen kan forklares ved hjælp af følgende eksempel.
Tag f.eks. den indledende matrix som 77, 33, 44, 11, 88, 22. I denne sorteringsalgoritme findes den mindste i matrixen. Det mindste element er 11. Det byttes med elementet i arrayets 0-indeks.
Nu er arrayet 11, 33, 44, 77, 88, 22.
Det mindste element er i indekset 0, så 11 er nu sorteret. Fra resten af elementerne er den mindste 22. Den er byttet med 1st indekselementet.
Nu er arrayet 11, 22, 44, 77, 88, 33.
Elementerne 11 og 22 er allerede sorteret. Fra resten er den mindste værdi 33. Den er byttet med 2nd indekselementet.
Nu er arrayet 11, 22, 33, 77, 88, 44.
Elementerne 11, 22 og 33 er allerede sorteret. Fra resten er den mindste værdi 44. Den er byttet med 3rd indekselementet.
Nu er arrayet 11, 22, 33, 44, 88, 66.
Elementerne 11, 22, 33, 44 er allerede sorteret. De resterende elementer er 88 og 66. Elementet 66 er byttet med 4th indekselementet.
Nu er arrayet 11, 22, 33, 44, 66, 88.
Det er det sorterede array, der bruger sorteringsalgoritmen for udvælgelse.
Figur 02: Eksempel på udvalgssortering
Implementeringen af indsættelsessorteringen er som ovenfor. Det oprindelige array var 77, 33, 44, 11, 88. Efter sortering giver det outputtet 11, 33, 44, 77, 88.
Hvad er ligheden mellem indsættelsessortering og udvalgssortering?
Både indsættelsessortering og udvalgssortering er sorteringsalgoritmer
Hvad er forskellen mellem indsættelsessortering og udvalgssortering?
Insertion Sort vs Selection Sort |
|
| Indsættelsessorteringen er sorteringsalgoritmen, der sorterer arrayet ved at flytte elementer et efter et. | Sorteringssorteringen er den sorteringsalgoritme, der finder det mindste element i arrayet og udveksler elementet med den første position, find derefter det næstmindste element og udskift det med elementet i den anden position og fortsætter processen indtil hele arrayet er sorteret. |
| Process | |
| Indsættelsessorteringen er at sortere underlisten ved at sammenligne to elementer, indtil hele arrayet er sorteret. | Sorteringen vælger minimumselementet og ombytter det med den første position, vælg igen minimum for resten og skift det til den anden position og fortsæt denne proces indtil slutningen. |
| Stabilitet | |
| Indsættelsessortering er en stabil sorteringsalgoritme. | Udvalgssortering er ikke en stabil sorteringsalgoritme. |
Opsummering – Indsættelsessortering vs. udvalgssortering
Nogle gange er det nødvendigt at sortere data. I datalogi findes der algoritmer til at sortere data. Denne artikel diskuterede de to sorteringsalgoritmer, som er indsættelsessortering og udvælgelsessortering. Indsættelsessorteringen er sorteringsalgoritmen, der sorterer arrayet ved at flytte elementer et efter et. Udvælgelsessortering er den sorteringsalgoritme, der finder det mindste element i arrayet og udveksler elementet med den første position, find derefter det næstmindste element og udskift det med elementet i den anden position og fortsætter processen, indtil hele arrayet er sorteret. Forskellen mellem indsættelsessortering og udvælgelsessortering er, at indsættelsessortering sammenligner to elementer ad gangen, mens udvælgelsessortering vælger minimumselementet fra hele arrayet og sorterer det.
Download PDF'en med sorteringssortering vs udvalg
Du kan downloade PDF-versionen af denne artikel og bruge den til offline-formål i henhold til citatnotat. Download venligst PDF-versionen her: Forskellen mellem indsættelsessortering og udvælgelsessortering
