Selection sort

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
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 - 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++[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] = 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