Nøkkelforskjell – innsettingssortering vs utvalgssortering
Innsettingssortering og utvalgssortering er to sorteringsalgoritmer som brukes til å sortere en samling av data. Noen ganger er det nødvendig å ordne data i en bestemt rekkefølge. Sorteringsalgoritmer er mekanismer for å sortere et sett med data. Ved sortering er dataene ordnet etter en numerisk eller leksikografisk rekkefølge. Hvis dataene er sortert riktig, vil det være enkelt å søke i data raskere. Hvis telefonnumrene i en telefonkatalog ikke er sortert, vil det være vanskelig å finne et spesifikt telefonnummer. På samme måte, hvis ordene i ordboken ikke er ordnet i alfabetisk rekkefølge, vil det være svært vanskelig å finne ord. Derfor er sortering nyttig i dagliglivet. I informatikk finnes det sorteringsalgoritmer for å sortere en samling av data. To slike algoritmer er innsettingssortering og utvalgssortering. Innsettingssortering er sorteringsalgoritmen som sorterer matrisen ved å skifte elementer ett etter ett. Utvelgelsesorteringen er sorteringsalgoritmen som finner det minste elementet i matrisen og bytter ut elementet med den første posisjonen, finn deretter det nest minste elementet og bytt det ut med elementet i den andre posisjonen og fortsetter prosessen til hele matrisen er sortert. Den viktigste forskjellen mellom innsettingssortering og utvalgssortering er at innsettingssortering sammenligner to elementer om gangen, mens utvalgssortering velger minimumselementet fra hele matrisen og sorterer det.
Hva er innsettingssortering?
Innsettingssortering er en sammenligningsbasert sorteringsalgoritme på stedet. I denne metoden søkes arrayen trinnvis. De usorterte elementene flyttes og settes inn i den sorterte underlisten til matrisen. Algoritmen for innsettingssortering kan forklares ved hjelp av følgende eksempel.
Ta for eksempel den innledende matrisen som 77, 33, 44, 11, 88. I denne sorteringsalgoritmen er det første trinnet å velge det gjeldende elementet.
Det gjeldende elementet er 77. Det gjeldende elementet sammenlignes med alle elementene på venstre side. 77, er det første elementet, og det er ingen elementer på venstre side. Indeksen for gjeldende posisjon er 0.
Så økes indeksen til gjeldende posisjon med 1. Nå er indeksen 1, og det gjeldende elementet er 33. Når man sammenligner det med elementet til venstre, er det mindre enn 77. Da er begge disse verdiene er byttet. Nå er 33 i indeks 0, og 77 er i indeks1.
Nå er matrisen 33, 77, 44, 11, 88.
Igjen, indeksen økes. Indeksen er 2, og gjeldende element er 44. Det sammenlignes med elementene på venstre side. 44 er mindre enn 77. Så disse to verdiene er byttet. Nå er matrisen 33, 44, 77, 11, 88. Det er nødvendig å sammenligne alle elementene til venstre. Så 44 sammenlignes med 33. 33 er mindre enn 44. Så disse elementene trenger ikke å byttes.
Nå er matrisen 33, 44, 77, 11, 88.
Igjen, indeksen økes. Indeksen er 3, og gjeldende element er 11. Det sammenlignes med alle elementene til venstre. 11 er mindre enn 77, så de to er byttet. Nå er matrisen 33, 44, 11, 77, 88. Når man sammenligner 11 og 44, er 11 mindre enn 44. Så disse to er byttet. Nå er matrisene 33, 11, 44, 77, 88. Igjen sammenlignes 11 med 33. 11 er mindre enn 33, så disse to verdiene er byttet.
Nå er matrisen 11, 33, 44, 77, 88.
Hvis du øker indeksen, blir indeksen 4. Verdien er 88. Den er høyere enn 77. Så det er ikke nødvendig å bytte. Til slutt er den sorterte matrisen 11, 33, 44, 77, 88.
Figur 01: Eksempel på innsettingssortering
Implementeringen av innsettingssorteringen er som ovenfor. Den opprinnelige matrisen var 77, 33, 44, 11, 88. Etter sortering gir den utdataene 11, 33, 44, 77, 88.
Hva er utvalgssortering?
Utvalgssortering er en sammenligningsbasert sorteringsalgoritme på stedet. Arrayene er delt inn i seksjoner. Den sorterte delen er i venstre ende. Den usorterte delen er i høyre ende. Først bør den minste verdien finnes. Deretter byttes det med venstre element. Nå er det elementet i den sorterte matrisen. Denne prosessen fortsetter å flytte usortert matrisegrense fra ett element til høyre. Valgsorteringsalgoritmen kan forklares ved hjelp av følgende eksempel.
Ta for eksempel den innledende matrisen som 77, 33, 44, 11, 88, 22. I denne sorteringsalgoritmen finnes den minste i matrisen. Det minste elementet er 11. Det byttes med elementet i 0-indeksen til matrisen.
Nå er matrisen 11, 33, 44, 77, 88, 22.
Det minste elementet er i indeksen 0, så 11 er nå sortert. Fra resten av elementene er den minste 22. Den byttes med 1st indekselementet.
Nå er matrisen 11, 22, 44, 77, 88, 33.
Elementene 11 og 22 er allerede sortert. Fra resten er den minste verdien 33. Den byttes med 2nd indekselementet.
Nå er matrisen 11, 22, 33, 77, 88, 44.
Elementene 11, 22 og 33 er allerede sortert. Fra resten er den minste verdien 44. Den byttes med 3rd indekselementet.
Nå er matrisen 11, 22, 33, 44, 88, 66.
Elementene 11, 22, 33, 44 er allerede sortert. De resterende elementene er 88 og 66. Elementet 66 er byttet med 4th indekselementet.
Nå er matrisen 11, 22, 33, 44, 66, 88.
Det er den sorterte matrisen som bruker utvalgssorteringsalgoritmen.
Figur 02: Sorteringseksempel
Implementeringen av innsettingssorteringen er som ovenfor. Den opprinnelige matrisen var 77, 33, 44, 11, 88. Etter sortering gir den utdataene 11, 33, 44, 77, 88.
Hva er likheten mellom innsettingssortering og utvalgssortering?
Både innsettingssortering og utvalgssortering er sorteringsalgoritmer
Hva er forskjellen mellom innsettingssortering og utvalgssortering?
Innsettingssortering vs utvalgssortering |
|
| Innsettingssorteringen er sorteringsalgoritmen som sorterer matrisen ved å skifte elementer ett etter ett. | Utvalgssorteringen er sorteringsalgoritmen som finner det minste elementet i matrisen og bytter elementet med den første posisjonen, finn deretter det nest minste elementet og bytt det ut med elementet i den andre posisjonen og fortsetter prosessen til hele matrisen er sortert. |
| Prosess | |
| Innsettingssorteringen er å sortere underlisten ved å sammenligne to elementer til hele matrisen er sortert. | Utvalgssorteringen velger minimumselementet og bytter det med den første posisjonen, velg igjen minimum for resten og bytt det til den andre posisjonen og fortsett denne prosessen til slutten. |
| Stability | |
| Innsettingssortering er en stabil sorteringsalgoritme. | Utvalgssortering er ikke en stabil sorteringsalgoritme. |
Summary – Insertion Sort vs Selection Sort
Noen ganger er det nødvendig å sortere data. I informatikk finnes det algoritmer for å sortere data. Denne artikkelen diskuterte de to sorteringsalgoritmene som er innsettingssortering og utvalgssortering. Innsettingssortering er sorteringsalgoritmen som sorterer matrisen ved å skifte elementer ett etter ett. Utvelgelsesorteringen er sorteringsalgoritmen som finner det minste elementet i matrisen og bytter ut elementet med den første posisjonen, finn deretter det nest minste elementet og bytt det ut med elementet i den andre posisjonen og fortsetter prosessen til hele matrisen er sortert. Forskjellen mellom innsettingssortering og utvalgssortering er at innsettingssortering sammenligner to elementer om gangen, mens utvalgssortering velger minimumselementet fra hele matrisen og sorterer det.
Last ned PDF-en av Insertion Sort vs Selection Sort
Du kan laste ned PDF-versjonen av denne artikkelen og bruke den til offline-formål i henhold til sitat. Last ned PDF-versjonen her: Difference Between Insertion Sort and Selection Sort
