Verschil tussen Insertion Sort en Selection Sort

Belangrijkste verschil - Insertion Sorteer versus selectiesortering
 

Insertion sort en selection sort zijn twee sorteeralgoritmen die worden gebruikt om een ​​verzameling gegevens te sorteren. Soms is het nodig om gegevens in een specifieke volgorde te ordenen. Sorteeralgoritmen zijn mechanismen om een ​​reeks gegevens te sorteren. Bij het sorteren worden de gegevens gerangschikt volgens een numerieke of een lexicografische volgorde. Als de gegevens correct zijn gesorteerd, zou het gemakkelijk zijn om sneller gegevens te zoeken. Als de telefoonnummers in een telefoongids niet gesorteerd zijn, is het moeilijk om een ​​specifiek telefoonnummer te vinden. Op dezelfde manier is het erg moeilijk om woorden te vinden als de woorden in het woordenboek niet in alfabetische volgorde zijn gerangschikt. Daarom is sorteren nuttig in het dagelijks leven. In Computer Science zijn er sorteeralgoritmen om een ​​verzameling gegevens te sorteren. Twee van dergelijke algoritmen zijn insertion sort en selection sort. 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 uitwisselt met de eerste positie, vervolgens het op een na kleinste element vindt en dit met het element in de tweede positie vervangt en het proces voortzet totdat de gehele array is gesorteerd . De belangrijk verschil tussen de invoegselectie en selectiesortering is dat invoegselectie vergelijkt twee elementen tegelijk, terwijl de selectiesortering het minimumelement uit de hele array selecteert en sorteert.

INHOUD

1. Overzicht en belangrijkste verschil
2. Wat is Insertion Sort
3. Wat is Selection Sort
4. Overeenkomsten tussen invoegselectie en selectiesortering
5. Vergelijking zij aan zij - Insertion Sort vs Selection Sort in tabelvorm
6. Samenvatting

Wat is Insertion Sort?

Insertion sort is een vergelijkend op locatie gebaseerd sorteeralgoritme. In deze methode wordt de array stap voor stap doorzocht. De ongesorteerde items worden verplaatst en ingevoegd in de gesorteerde sublijst van de array. Het insertiesorteeralgoritme kan worden verklaard 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.

Vervolgens wordt de index van de huidige positie verhoogd met 1. Nu is de index 1 en het huidige element 33. Als u het vergelijkt met het element links, is het kleiner dan 77. Vervolgens worden beide waarden omgewisseld. Nu staat 33 in index 0 en 77 in index1.

Nu is de array 33, 77, 44, 11, 88.

Nogmaals, de index is geïncrementeerd. De index is 2 en het huidige element is 44. Het wordt vergeleken met de elementen aan de linkerkant. 44 is minder dan 77. Dus die twee waarden zijn verwisseld. Nu is de reeks 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. Dus die elementen hoeven niet te worden uitgewisseld.

Nu is de reeks 33,44,77,11,88.

Nogmaals, de index is geïncrementeerd. De index is 3 en het huidige element is 11. Het wordt vergeleken met alle elementen links. 11 is minder dan 77, dus die twee zijn verwisseld. Nu is de reeks 33,44,11,77,88. Bij het vergelijken van 11 en 44 is 11 minder dan 44. Dus die twee zijn verwisseld. De reeksen zijn nu 33,11,44,77,88. Opnieuw wordt 11 vergeleken met 33. 11 is minder dan 33, dus die twee waarden worden verwisseld.

Nu is de array 11,33,44,77,88.

Als u de index verhoogt, wordt de index ingesteld op 4. De waarde is 88. Deze is hoger dan 77. U hoeft dus niet te swappen. Ten slotte is de gesorteerde array 11,33,44,77,88.

Afbeelding 01: invoegsorteervoorbeeld

De implementatie van de invoegsortering is zoals hierboven. De aanvankelijke reeks was 77,33, 44,11,88. Na het sorteren geeft het de uitvoer 11,33,44,77,88.

Wat is Selection Sort?

Selectiesortering is een vergelijkend op locatie gebaseerd sorteeralgoritme. De arrays zijn verdeeld in secties. Het gesorteerde deel bevindt zich aan de linkerkant. Het ongesorteerde gedeelte bevindt zich aan het juiste uiteinde. Eerst moet de kleinste waarde worden gevonden. Vervolgens wordt het verwisseld met het linkerelement. Dat element bevindt zich nu in de gesorteerde array. Dit proces gaat door met het verplaatsen van ongesorteerde array-grenzen van één element naar rechts. Het algoritme voor selectie van sortering 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 elementen is de kleinste 22. Het wordt verwisseld met de 1^st indexelement.

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. Het wordt geruild met de 2^nd indexelement.

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 geruild met de 3^rd indexelement.

Nu is de reeks 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 is verwisseld met de 4^th indexelement.

Nu is de array 11,22,33,44,66,88.

Het is de gesorteerde array die het algoritme voor selectie sortering gebruikt.

Figuur 02: Selectiemodel sorteren

De implementatie van de invoegsortering is zoals hierboven. De aanvankelijke reeks was 77,33, 44,11,88. Na het sorteren geeft het de uitvoer 11,33,44,77,88.

Wat is de overeenkomst tussen invoegselectie en selectiesortering?

• Zowel Insertion Sort als Selection Sort zijn sorteringsalgoritmen.

Wat is het verschil tussen Insertion Sort en Selection Sort?

Insertion Sort versus Selection Sort
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 uitwisselt met de eerste positie, vervolgens het op een na kleinste element vindt en dit met het element in de tweede positie vervangt en het proces voortzet totdat de gehele array is gesorteerd.
Werkwijze
De invoegselectie is om de sublijst te sorteren door twee elementen te vergelijken tot de hele array is gesorteerd.	De selectiesortering selecteert het minimale element en verwisselt het met de eerste positie, selecteer opnieuw het minimum voor de rest en verwissel het de tweede positie en ga door met dit proces tot het einde.
Stabiliteit
Insertion sort is een stabiel sorteeralgoritme.	Selectie sorteren is geen stabiel sorteeralgoritme.

Samenvatting - invoeging Sorteer versus selectiesortering 

Soms is het nodig om gegevens te sorteren. In Computer Science zijn er algoritmen om gegevens te sorteren. In dit artikel worden de twee sorteringsalgoritmen besproken die invoegingssoort 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 uitwisselt met de eerste positie, vervolgens het op een na kleinste element vindt en dit met het element in de tweede positie vervangt en het proces voortzet totdat de gehele array is gesorteerd . Het verschil tussen de invoegselectie en selectiesortering is dat invoegselectie twee elementen tegelijkertijd vergelijkt terwijl de selectiesortering het minimumelement uit de hele array selecteert en sorteert.

Download de PDF van invoegsortering versus selectiesortering

U kunt de PDF-versie van dit artikel downloaden en gebruiken voor offline doeleinden volgens citaatnotitie. Download de PDF-versie hier: Verschil tussen invoegselectie Sorteren en sorteren sorteren

Referentie:

1.Point, zelfstudies. "Gegevensstructuren en algoritmen invoegsortering." Www.tutorialspoint.com, Tutorials Point, 8 jan. 2018.Beschikbaar Hier
2.Selectiesortering in gegevensstructuren | Datastructuur Zelfstudie | Studytonight.  Beschikbaar Hier
3.Theoryapp. "Selectie, invoegen en bellen sorteren." TheoryApp, 20 januari 2014.  Beschikbaar Hier
4.Insertiesortering in gegevensstructuren | Datastructuur Zelfstudie | Studytonight.  Beschikbaar Hier