Selection sort

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Animatie van selection sort.

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

Werking[bewerken]

De methode werkt als volgt:

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


In Java[bewerken]

Een voorbeeld in Java van Selection Sort.

for (int i = 0; i < array.length; 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++[bewerken]

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#[bewerken]

Een voorbeeld in Csharp van Selection Sort.

public void SelectionSort(int[] T)
{
  int K, X;
  for (int I = 0 ; I < T.Length - 1 ; I++)
  {
    K = I;
    X = T[I];
    for (int J = i + 1 ; J < T.Length ; J++)
    {
	if (T[J] < X)
	{                                    // bijhouden kleinste in de array die nog niet gesorteerd is
	  K = J;
	  X = T[J];
	}
    }
    T[K] = T[I];
    T[I] = X;
  }
}/*SelectionSort*/

In Python[bewerken]

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