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)
{
  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] = T[temp]
  }
}/*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