Selectionsort

Selectionsort

Lidt om algoritmen:
Meningen med selection sort er at hver skift af data indsætter elementet direkte på sin slut position.
Dette gøres ved at finde det største tal i listen og det bytter så plads med det sidste element i listen.
Dernæst findes det største tal i resten af listen og byttes med det næstsidste element i listen.
Dette gentages indtil hele listen er gennemløbet.

Da selection sort tilgår listen mere eller mindre tilfældigt, er det ikke en god algoritme at bruge på linkede lister, da en stor del af tiden vil blive brugt på at traversere listen, for at finde det rette element, samt flytning af pointere.

Hastighed:
Selection sort er en usædvanlig sorterings algoritme, da den foretager det samme antal sammeligninger og assignments.
Hvis listen har længden L, skal der derfor foretages L-1 sammenligninger.

Først sammenlignes det første og det andet element.
Her udvælges det største af de to elementer og det sammenlignes det med det tredie element.
Dette gentages indtil det største element i listen L-1 sammenlignes med det sidste element.

Dette giver et gennemsnitlig antal sammenligninger per element er L/2.
Ialt bruger selection sort L(L/2) eller L2/2.
Derfor er selection sort en O(n2) algoritme.

Eksempel:
Sourcekode til eksempel:
SortAlgorithm.java
MySelectionSort.java

Eksemplet er implementeret på et array.
MySelectionSort.java indeholder metoden sort( int[] a ) der udfører sorteringen.
Den første for løkke rykker et element frem i arrayet.
Herefter begynder den anden for løkke, startende fra marker1 + 1 og frem.
Her findes det mindste element i det resterende stykke af listen.
Det indsættes så på position min.

Der er metoder til sortering af en vektor.
Metoden print() til at udskrive det sorterede array.