Belangrijk verschil - Invoegsortering versus selectiesortering
Invoegsortering en selectiesortering zijn twee sorteeralgoritmen die worden gebruikt om een verzameling gegevens te sorteren. Soms is het nodig om gegevens in een bepaalde volgorde te ordenen. Sorteeralgoritmen zijn mechanismen om een reeks gegevens te sorteren. Bij het sorteren worden de gegevens gerangschikt volgens een numerieke of lexicografische volgorde. Als de gegevens goed zijn gesorteerd, is het gemakkelijk om gegevens sneller te doorzoeken. Als de telefoonnummers in een telefoonboek niet gesorteerd zijn, is het moeilijk om een specifiek telefoonnummer te vinden. Op dezelfde manier, als de woorden in het woordenboek niet in alfabetische volgorde zijn gerangschikt, zou het erg moeilijk zijn om woorden te vinden. Sorteren is daarom handig in het dagelijks leven. In Computer Science zijn er sorteeralgoritmen om een verzameling gegevens te sorteren. Twee van dergelijke algoritmen zijn invoegsortering en selectiesortering. De invoegsortering is het sorteeralgoritme dat de array sorteert door elementen één voor één te verschuiven. De selectiesortering is het sorteeralgoritme dat het kleinste element in de array vindt en het element met de eerste positie verwisselt, vervolgens het op een na kleinste element vindt en dit verwisselt met het element op de tweede positie en het proces voortzet totdat de hele array is gesorteerd. Het belangrijkste verschil tussen de invoegsortering en de selectiesortering is dat de invoegsortering twee elementen tegelijk vergelijkt, terwijl de selectiesortering het minimumelement uit de hele array selecteert en sorteert.
Wat is invoegsortering?
Invoegsortering is een in-place sorteeralgoritme op basis van vergelijkingen. Bij deze methode wordt de array stap voor stap doorzocht. De ongesorteerde items worden verplaatst en ingevoegd in de gesorteerde sublijst van de array. Het invoegsorteeralgoritme kan worden uitgelegd aan de hand van het volgende voorbeeld.
Neem bijvoorbeeld de initiële array als 77, 33, 44, 11, 88. In dit sorteeralgoritme is de eerste stap het selecteren van het huidige element.
Het huidige element is 77. Het huidige element wordt vergeleken met alle elementen aan de linkerkant. De 77 is het eerste element en er zijn geen elementen aan de linkerkant. De index van de huidige positie is 0.
Dan wordt de index van de huidige positie met 1 verhoogd. Nu is de index 1, en het huidige element is 33. Als je het vergelijkt met het element aan de linkerkant, is het kleiner dan 77. Dan zijn beide waarden zijn verwisseld. Nu staat 33 in index 0 en 77 in index1.
Nu is de array 33, 77, 44, 11, 88.
Nogmaals, de index wordt verhoogd. De index is 2 en het huidige element is 44. Het wordt vergeleken met de elementen aan de linkerkant. 44 is kleiner dan 77. Dus die twee waarden zijn verwisseld. Nu is de array 33, 44, 77, 11, 88. Het is noodzakelijk om alle elementen aan de linkerkant te vergelijken. Dus de 44 wordt vergeleken met 33. 33 is kleiner dan 44. Die elementen hoeven dus niet uitgewisseld te worden.
Nu is de array 33, 44, 77, 11, 88.
Nogmaals, de index wordt verhoogd. De index is 3 en het huidige element is 11. Het wordt vergeleken met alle elementen aan de linkerkant. 11 is kleiner dan 77, dus die twee zijn verwisseld. Nu is de array 33, 44, 11, 77, 88. Bij het vergelijken van 11 en 44 is 11 minder dan 44. Dus die twee zijn verwisseld. Nu zijn de arrays 33, 11, 44, 77, 88. Opnieuw wordt 11 vergeleken met 33. 11 is kleiner dan 33, dus die twee waarden zijn verwisseld.
Nu is de array 11, 33, 44, 77, 88.
Het verhogen van de index zal de index op 4 brengen. De waarde is 88. Het is hoger dan 77. Het is dus niet nodig om te wisselen. Ten slotte is de gesorteerde array 11, 33, 44, 77, 88.
Figuur 01: Voorbeeld van invoegsortering
De implementatie van de invoegsortering is zoals hierboven. De initiële array was 77, 33, 44, 11, 88. Na het sorteren geeft het de output 11, 33, 44, 77, 88.
Wat is Selectie Sorteren?
Selectie sorteren is een in-place sorteeralgoritme op basis van vergelijkingen. De arrays zijn onderverdeeld in secties. Het gesorteerde deel bevindt zich aan de linkerkant. Het ongesorteerde deel bevindt zich aan de rechterkant. Eerst moet de kleinste waarde worden gevonden. Vervolgens wordt het verwisseld met het linkerelement. Nu staat dat element in de gesorteerde array. Dit proces gaat door met het verplaatsen van de ongesorteerde arraygrens van het ene element naar rechts. Het selectiesorteeralgoritme kan worden uitgelegd aan de hand van het volgende voorbeeld.
Neem bijvoorbeeld de initiële array als 77, 33, 44, 11, 88, 22. In dit sorteeralgoritme wordt de kleinste in de array gevonden. Het kleinste element is 11. Het wordt verwisseld met het element in de 0-index van de array.
Nu is de array 11, 33, 44, 77, 88, 22.
Het kleinste element staat in de index 0, dus 11 is nu gesorteerd. Van de rest van de elementen is de kleinste 22. Het wordt verwisseld met het indexelement 1st.
Nu is de array 11, 22, 44, 77, 88, 33.
De elementen 11 en 22 zijn al gesorteerd. Van de rest is de kleinste waarde 33. Deze wordt verwisseld met het indexelement 2nd.
Nu is de array 11, 22, 33, 77, 88, 44.
De elementen 11, 22 en 33 zijn al gesorteerd. Van de rest is de kleinste waarde 44. Deze wordt verwisseld met het indexelement 3rd.
Nu is de array 11, 22, 33, 44, 88, 66.
De elementen 11, 22, 33, 44 zijn al gesorteerd. De overige elementen zijn 88 en 66. Het element 66 wordt verwisseld met het 4th indexelement.
Nu is de array 11, 22, 33, 44, 66, 88.
Het is de gesorteerde array met behulp van het selectiesorteeralgoritme.
Figuur 02: Selectie Sorteer voorbeeld
De implementatie van de invoegsortering is zoals hierboven. De initiële array was 77, 33, 44, 11, 88. Na het sorteren geeft het de output 11, 33, 44, 77, 88.
Wat is de overeenkomst tussen invoegsortering en selectiesortering?
Zowel Insertion Sort als Selection Sort zijn sorteeralgoritmen
Wat is het verschil tussen invoegsortering en selectiesortering?
Invoegsortering versus selectiesortering |
|
| De invoegsortering is het sorteeralgoritme dat de array sorteert door elementen één voor één te verschuiven. | De selectiesortering is het sorteeralgoritme dat het kleinste element in de array vindt en het element met de eerste positie verwisselt, dan het op een na kleinste element vindt en het verwisselt met het element op de tweede positie en het proces voortzet tot de hele array is gesorteerd. |
| Proces | |
| De invoegsortering is om de sublijst te sorteren door twee elementen te vergelijken totdat de hele array is gesorteerd. | De selectiesortering selecteert het minimumelement en verwisselt het met de eerste positie, selecteert opnieuw het minimum voor de rest en verwisselt het naar de tweede positie en zet dit proces voort tot het einde. |
| Stabiliteit | |
| Invoegsortering is een stabiel sorteeralgoritme. | Selectie sorteren is geen stabiel sorteeralgoritme. |
Samenvatting – Invoegsortering versus selectiesortering
Soms is het nodig om gegevens te sorteren. In Computer Science zijn er algoritmen om gegevens te sorteren. Dit artikel besprak de twee sorteeralgoritmen die invoegsortering en selectiesortering zijn. De invoegsortering is het sorteeralgoritme dat de array sorteert door elementen één voor één te verschuiven. De selectiesortering is het sorteeralgoritme dat het kleinste element in de array vindt en het element met de eerste positie verwisselt, vervolgens het op een na kleinste element vindt en dit verwisselt met het element op de tweede positie en het proces voortzet totdat de hele array is gesorteerd. Het verschil tussen de invoegsortering en de selectiesortering is dat de invoegsortering twee elementen tegelijk vergelijkt, terwijl de selectiesortering het minimumelement uit de hele array selecteert en sorteert.
Download de PDF van Insertion Sort vs Selection Sort
U kunt de PDF-versie van dit artikel downloaden en gebruiken voor offline doeleinden volgens de citatienota. Download hier de PDF-versie: Verschil tussen invoegsortering en selectiesortering
