Nyckelskillnad – Insättningssortering vs urvalssortering
Infogningssortering och urvalssortering är två sorteringsalgoritmer som används för att sortera en samling data. Ibland är det nödvändigt att ordna data i en specifik ordning. Sorteringsalgoritmer är mekanismer för att sortera en uppsättning data. Vid sortering är uppgifterna ordnade enligt en numerisk eller lexikografisk ordning. Om uppgifterna sorteras korrekt, skulle det vara lätt att söka efter data snabbare. Om telefonnumren i en telefonkatalog inte är sorterade skulle det vara svårt att hitta ett specifikt telefonnummer. På samma sätt, om orden i ordboken inte är ordnade i alfabetisk ordning, skulle det vara mycket svårt att hitta ord. Därför är sortering användbart i det dagliga livet. Inom datavetenskap finns det sorteringsalgoritmer för att sortera en samling data. Två sådana algoritmer är infogningssortering och urvalssortering. Insättningssorteringen är sorteringsalgoritmen som sorterar matrisen genom att flytta element ett efter ett. Urvalssorteringen är sorteringsalgoritmen som hittar det minsta elementet i matrisen och byter ut elementet med den första positionen, hittar sedan det näst minsta elementet och byter ut det med elementet i den andra positionen och fortsätter processen tills hela matrisen är sorterad. Den viktigaste skillnaden mellan infogningssorteringen och urvalssorteringen är att infogningssorteringen jämför två element åt gången medan urvalssorteringen väljer minimielementet från hela matrisen och sorterar det.
Vad är insättningssortering?
Infogningssortering är en jämförelsebaserad sorteringsalgoritm på plats. I denna metod genomsöks arrayen steg för steg. De osorterade objekten flyttas och infogas i den sorterade underlistan för arrayen. Insättningssorteringsalgoritmen kan förklaras med följande exempel.
Ta till exempel den initiala matrisen som 77, 33, 44, 11, 88. I denna sorteringsalgoritm är det första steget att välja det aktuella elementet.
Det aktuella elementet är 77. Det aktuella elementet jämförs med alla element på vänster sida. 77:an är det första elementet och det finns inga element på vänster sida. Indexet för den aktuella positionen är 0.
Då ökas indexet för den aktuella positionen med 1. Nu är indexet 1, och det aktuella elementet är 33. När man jämför det med elementet till vänster är det mindre än 77. Då båda dessa värden är utbytta. Nu är 33 i index 0 och 77 är i index1.
Nu är arrayen 33, 77, 44, 11, 88.
Återigen, indexet ökas. Indexet är 2 och det aktuella elementet är 44. Det jämförs med elementen på vänster sida. 44 är mindre än 77. Så dessa två värden byts om. Nu är matrisen 33, 44, 77, 11, 88. Det är nödvändigt att jämföra alla element till vänster. Så 44:an jämförs med 33. 33 är mindre än 44. Så dessa element behöver inte bytas ut.
Nu är arrayen 33, 44, 77, 11, 88.
Återigen, indexet ökas. Indexet är 3, och det aktuella elementet är 11. Det jämförs med alla element till vänster. 11 är mindre än 77, så dessa två är utbytta. Nu är matrisen 33, 44, 11, 77, 88. När man jämför 11 och 44 är 11 mindre än 44. Så dessa två byts om. Nu är matriserna 33, 11, 44, 77, 88. Återigen jämförs 11 med 33. 11 är mindre än 33, så dessa två värden byts om.
Nu är arrayen 11, 33, 44, 77, 88.
Om du ökar indexet blir indexet 4. Värdet är 88. Det är högre än 77. Så det finns inget behov av att byta. Slutligen är den sorterade matrisen 11, 33, 44, 77, 88.
Figur 01: Exempel på infogningssortering
Implementeringen av infogningssorteringen är enligt ovan. Den initiala matrisen var 77, 33, 44, 11, 88. Efter sortering ger den utdata 11, 33, 44, 77, 88.
Vad är urvalssortering?
Utvalssortering är en jämförelsebaserad sorteringsalgoritm på plats. Arrayerna är uppdelade i sektioner. Den sorterade delen är i den vänstra änden. Den osorterade delen är i den högra änden. Först ska det minsta värdet hittas. Sedan byts det ut med det vänstra elementet. Nu finns det elementet i den sorterade arrayen. Denna process fortsätter att flytta osorterad arraygräns från ett element till höger. Valsorteringsalgoritmen kan förklaras med följande exempel.
Ta till exempel den initiala arrayen som 77, 33, 44, 11, 88, 22. I denna sorteringsalgoritm hittas den minsta i arrayen. Det minsta elementet är 11. Det byts ut mot elementet i matrisens 0-index.
Nu är arrayen 11, 33, 44, 77, 88, 22.
Det minsta elementet finns i index 0, så 11 är nu sorterat. Från resten av elementen är den minsta 22. Den byts ut mot indexelementet 1st.
Nu är arrayen 11, 22, 44, 77, 88, 33.
Elementen 11 och 22 är redan sorterade. Från resten är det minsta värdet 33. Det byts ut med 2nd indexelement.
Nu är arrayen 11, 22, 33, 77, 88, 44.
Elementen 11, 22 och 33 är redan sorterade. Från resten är det minsta värdet 44. Det byts ut med 3rd indexelement.
Nu är arrayen 11, 22, 33, 44, 88, 66.
Elementen 11, 22, 33, 44 är redan sorterade. De återstående elementen är 88 och 66. Elementet 66 byts ut mot det 4th indexelementet.
Nu är arrayen 11, 22, 33, 44, 66, 88.
Det är den sorterade arrayen som använder urvalssorteringsalgoritmen.
Figur 02: Urvalssorteringsexempel
Implementeringen av infogningssorteringen är enligt ovan. Den initiala matrisen var 77, 33, 44, 11, 88. Efter sortering ger den utdata 11, 33, 44, 77, 88.
Vad är likheten mellan infogningssortering och urvalssortering?
Både infogningssortering och urvalssortering är sorteringsalgoritmer
Vad är skillnaden mellan infogningssortering och urvalssortering?
Infogningssortering vs urvalssortering |
|
| Infogningssorteringen är sorteringsalgoritmen som sorterar matrisen genom att flytta element ett efter ett. | Selekteringssorteringen är den sorteringsalgoritm som hittar det minsta elementet i arrayen och byter ut elementet med den första positionen, hitta sedan det näst minsta elementet och byt ut det med elementet i den andra positionen och fortsätter processen tills hela arrayen är sorterad. |
| Process | |
| Insättningssorteringen är att sortera underlistan genom att jämföra två element tills hela arrayen är sorterad. | Sorteringen väljer minimielementet och byter ut det med den första positionen, välj återigen minimum för resten och byter det till den andra positionen och fortsätt denna process till slutet. |
| Stabilitet | |
| Infogningssortering är en stabil sorteringsalgoritm. | Urvalssortering är inte en stabil sorteringsalgoritm. |
Sammanfattning – Infogningssortering vs urvalssortering
Ibland är det nödvändigt att sortera data. Inom datavetenskap finns det algoritmer för att sortera data. Den här artikeln diskuterade de två sorteringsalgoritmerna som är infogningssortering och urvalssortering. Insättningssorteringen är sorteringsalgoritmen som sorterar matrisen genom att flytta element ett efter ett. Urvalssorteringen är sorteringsalgoritmen som hittar det minsta elementet i matrisen och byter ut elementet med den första positionen, hittar sedan det näst minsta elementet och byter ut det med elementet i den andra positionen och fortsätter processen tills hela matrisen är sorterad. Skillnaden mellan infogningssorteringen och urvalssorteringen är att insättningssorteringen jämför två element åt gången medan urvalssorteringen väljer minimielementet från hela arrayen och sorterar det.
Ladda ner PDF-filen för Insertion Sort vs Selection Sort
Du kan ladda ner PDF-versionen av den här artikeln och använda den för offlineändamål enligt citat. Ladda ner PDF-versionen här: Skillnaden mellan infogningssortering och urvalssortering
