SelectionSort bringt keine konstanten Ergebnisse

[Anorak]

Steht alles im Titel, klappt nicht immer ich denke, dass es an d

for (int i=0;i<n;i++){

ieser Zeile hier liegt
Gesamter Code:

 int n=zahlMerken.length;
    for (int i=0;i<n;i++){
      int min = i;
       for (int j=i+1;j<n;j++){
        if (zahlMerken[j] < zahlMerken[min]){
        min = j;
        z=zahlMerken[i];
        zahlMerken[i] = zahlMerken[min];
        zahlMerken[min] = z;
       }
      }
    }
    return zahlMerken;

 

[Robat]

1.deine äußere Schleife darf nur bis n-2 laufen.
2. Momentan tauschst du nur wenn zahlMerken[j] < zahlMerken[min] erfüllt ist. Du musst aber immer das gefundene (kleinste) Element (min) mit dem ersten Element der Iteration (i) tauschen.

 

[Anorak]

Wie funktioniert denn das, dass immer das kleinste Element gesucht wird

 

[Xyz1]

    public static void main(String[] args) {
        Boolean[] a = new Boolean[]{true, false, true};
        SelectionSort(a);
        System.out.println(Arrays.toString(a));

        Integer[] b = new Integer[]{2, -2, -2};
        SelectionSort(b);
        System.out.println(Arrays.toString(b));
    }

    static <T extends Comparable<T>> void SelectionSort(T[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[min].compareTo(a[j]) > 0) {
                    min = j;
                }
            }
            if (min != i) {

                T t = a[i];
                a[i] = a[min];
                a[min] = t;
            }
        }
    }

Erst kleinstes bestimmen und hinterher tauschen.
Du tauschst unmittelbar, dann zeigt min nicht mehr auf kleinstes - und die Stabilität ist nicht mehr gegeben.
Der Index min hat ne gewisse Eigenschaft. Aber tief in das mathematische will ich jetzt abtauchen.

 

[Xyz1]

Oh, selectionsort ist instabil - und die Begründung steht hier: https://stackoverflow.com/questions/4601057/why-is-selection-sort-not-stable/4601081#4601081 ...

The problem is that selection sort swaps elements from the front of the array into the spot vacated by the minimum element ...

Dh, meine Methode SelectionSort ist genau richtig. Kann aber nochmal gerne auch einen theoretischen Algorithmiker fragen wenn gewünscht?