selectie sorteren is een eenvoudig sorteeralgoritme. Dit sorteeralgoritme is een op plaats gebaseerd vergelijkingsalgoritme waarin de lijst is verdeeld in twee delen, het gesorteerde deel aan de linkerkant en het ongesorteerde deel aan de rechterkant. Aanvankelijk is het gesorteerde deel leeg en het ongesorteerde deel is de volledige lijst.
het kleinste element wordt geselecteerd uit de ongesorteerde array en geruild met het meest linkse element, en dat element wordt een deel van de gesorteerde array. Dit proces gaat door met het verplaatsen van ongesorteerde array grens door een element naar rechts.
dit algoritme is niet geschikt voor grote gegevensverzamelingen omdat de gemiddelde en worst case-complexiteit van het algoritme Ο(n2) zijn, waarbij n het aantal items is.
Hoe Werkt Selectie Sorteren?
beschouw de volgende afgebeelde array als een voorbeeld.
voor de eerste positie in de gesorteerde lijst wordt de hele lijst achtereenvolgens gescand. De eerste positie waar 14 momenteel wordt opgeslagen, doorzoeken we de hele lijst en vinden dat 10 de laagste waarde is.
dus we vervangen 14 door 10. Na een iteratie 10, die toevallig de minimale waarde in de lijst, verschijnt in de eerste positie van de gesorteerde lijst.
voor de tweede positie, waar 33 zich bevindt, beginnen we de rest van de lijst lineair te scannen.
we vinden dat 14 de op een na laagste waarde in de lijst is en het zou op de tweede plaats moeten verschijnen. We wisselen deze waarden om.
na twee herhalingen worden twee kleinste waarden gesorteerd aan het begin geplaatst.
hetzelfde proces wordt toegepast op de rest van de items in de array.
hier volgt een picturale weergave van het gehele sorteerproces −
laten we nu wat programmeeraspecten van selectie Sorteren leren.
algoritme
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
Pseudocode
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
om meer te weten te komen over de implementatie van selectie sorteren in de programmeertaal C, Klik hier.