Selectionsort

Einfache Sprache

Insertionsort ist ein Sortierverfahren, wobei das Feld in zwei Teile aufgeteilt wird. Ein sortierte und ein unsortierter Teil. Für das Sortieren wird das minimale Element aus dem unsortieren Teil gewählt und an den Anfang des unsortierten Teil getauscht. Wiederhole das solange bis der unsortierte Teil leer ist.

Idee Selectionsort

Halte einen sortierten (die ersten $i$ Elemente in $A$ von Position $0$ bis $i-1$) und einen nicht-sortierten Bereich in $A$ (die Elemente in $A$ von Position $i$ bis $n-1$) vor. Im $i$-ten Durchlauf (für $i$ von $1$ bis $n-1$) wähle das minimale Element aus dem nicht-sortierten Bereich in $A$ und vertausche es mit dem Element an Position $i$.

Algorithmus

 1def selection_sort(A: list) -> None:
 2    """
 3    Sorts an array in-place using Selection Sort algorithm.
 4    
 5    Args:
 6        A: List of comparable elements to be sorted
 7        
 8    Returns:
 9        None: The input list is sorted in-place
10    """
11    n = len(A)
12    for i in range(n-1):
13        min_index = i
14        min_val = A[i]
15        for j in range(i+1, n):
16            if A[j] < min_val:
17                min_val = A[j]
18                min_index = j
19        A[i], A[min_index] = A[min_index], A[i]

Laufzeit

Selectionsort hat eine Laufzeit von $\mathcal O(n^2)$.