Selection sort

Selection sort is een sorteeralgoritme. Selection sort is een eenvoudige maar ook inefficiënte sorteermethode. Zij heeft een complexiteitsgraad van O(n²).

Werking

De methode werkt als volgt:

Zoek de kleinste waarde in de lijst.
Verwissel het met de eerste waarde in de lijst.
Herhaal de bovenstaande stappen met de rest van de lijst.

Een variant is om het grootste waarde in de lijst te zoeken en deze achteraan te plaatsen. In de literatuur vindt men soms de variant met de kleinste waarde vooraan te plaatsen, soms de variant met de grootste waarde achteraan te plaatsen.

Analyse

Als we het aantal vergelijkingen tussen diverse elementen als maatstaf nemen voor de uitvoeringstijd van het algoritme, dan is het eenvoudig om in te zien dat om in een lijst van n elementen, de kleinste waarde te zoeken, men n-1 aantal vergelijkigen tussen elementen nodig heeft.

Vervolgens heeft men n-2 vergelijkingen tussen elementen nodig om de tweede kleinste waarde te zoeken, enz.

Het totaal aantal vergelijkingen tussen elementen voor het gehele algoritme sommeert dan tot:

$(n-1)+(n-2)+(n-3)+...+2+1={n(n-1) \over 2}={n*n \over 2}-{n \over 2}$

Dit verklaart de kwadratische tijdscomplexiteit.

In Java

Een voorbeeld in Java van Selection Sort.

for (int i = 0; i < array.length - 1; i++) {                // invoer = array met integers	

	int minIndex = i;                               // zoek kleinste in de rest van de array
	for (int j = i + 1; j < array.length; j++) {
		if (array[j] < array[minIndex]) { 
			minIndex = j;
		}
	}

	int temp = array[i];                           // verwissel waarden
	array[i] = array[minIndex];
	array[minIndex] = temp;
}

In C++

for (int i = v.size() - 1; i >= 0; i--)
{
	T max = v[0];
	int maxpos = 0;
	int j;
	for (j = 1; j < i; j++)
	{
		if (v[j] > max){
			max = v[j];
			maxpos = j;
		}
	}
	swap(v[maxpos], v[i]);
}

In C#

Een voorbeeld in Csharp van Selection Sort.

public void SelectionSort(int[] T)
{
  for (int I = 0 ; I < T.Length - 1 ; I++){  //Loop door de hele array
    int MinIndex = I; //Hou de kleinste waarde bij, als we beginnen is die gelijk aan het element dat we proberen te sorteren
    for (int J = I + 1 ; J < T.Length ; J++){ //Loop door het ongesorteerde deel
        if (T[J] < T[MinIndex]){                        
           MinIndex = J;
        }
    }
    //Zet het kleinste element uit de rij op positie I
    Int temp = T[I];
    T[I] = T[MinIndex];
    T[MinIndex] = temp;
  }
}/*SelectionSort*/

In Python

def SelectionSort(lst):
    
    
    for i in range(len(lst)):
        kleinste=lst[i]
        te_wisselen=i
        for n in range(i,len(lst)):
            if lst[n]<kleinste:
                kleinste=lst[n]
                te_wisselen=n

        lst[te_wisselen]=lst[i]
        lst[i]=kleinste      

    return lst