Ist das noch Insertionsort?

[Staddl]

Servus - ich bitte um eure Meinung!

In der Schule machen wir gerade Sortieralgorithmen - ich probier's immer selbst bevor ich mir die Referenz ansehe und habe folgenden Algorithmus entworfen (Kommentare bitte einfach ignorieren):

int[] arr = {9, 2, 7, 5, 4, 3, 1, 8, 6};
int temp;

System.out.println("--Insertionsort--");
System.out.println("Unsortiert: " + Arrays.toString(arr));



for (int i = 1; i < arr.length; i++) {  //das erste Element zum vor das 1. Element einfügen ist sinnlos => wir starten bei i=1

    for (int j = 0; j < i; j++) {
        if (arr<arr[j]) {
            temp=arr;
            arr=arr[j];
            arr[j]=temp;
        }
    }
    /* innere For-Schleife bis zu <i, da das i'te Elementt ein nach rechts verschobenes ist => muss größer sein als alles links davon
    *die 3ecks-Vertauschung findet so oft statt, wie viele größere Elemente es vor dem i'ten Element gibt
    * im Prinzip wird das i'te Elemente mit dem j'ten Element vertauscht, dann wieder das i'te (was jetzt das vorherige j'te ist)
    * wieder mit dem neuen j'ten Elementt. Dieses ist dann wieder das i'te Element usw., bis links vom i'ten Element keine
    * Elemente < arr mehr sind */

    System.out.println("Zwischenstand: " + Arrays.toString(arr));
}

System.out.println("Sortiert: " + Arrays.toString(arr));

So, jetzt wird ja (scheinbar) mit jedem durchlauf der äußeren For-Schleife ein Element eingefügt, so wie gewollt. Wie ihr es aber wahrscheinlich schon seht vertausche ich eigentlich Elemente von 0 bis i, je nachdem welches halt als erstes >arr(i) ist.
Nun meine eigentliche Frage: ist das Insertionsort (wenn auch schlechter als die Norm), oder einfach irgendein Algorithmus?

Danke fürs durchlesen!

P.S. das meine ich mit "Norm": https://www.geeksforgeeks.org/insertion-sort/

 

[yfons123]

warum sollte das ding überhaupt kompilieren?
( nicht notwendige kommentare zum durchlesen sind in unter 1 sec zu löschen )

 

[Meniskusschaden]

Beim Einfügen des Codes sind offenbar einige [i] verloren gegangen und haben die kursive Darstellung bewirkt.

Nun meine eigentliche Frage: ist das Insertionsort (wenn auch schlechter als die Norm), oder einfach irgendein Algorithmus?

Es gibt eine sortierte und eine unsortierte Teilmenge der Elemente. Das jeweils zu sortierende Element wird der unsortierten Teilmenge auf triviale Weise entnommen und der sortierten Teilmenge auf komplexere Weise hinzugefügt. Der eigentliche Sortieraufwand entsteht also beim Einfügen. Für mich sind damit die wesentlichen Kriterien für InsertionSort erfüllt.

 

[KonradN]

Also das Insertionsort sollte aber doch eigentlich keine Vertauschungen haben.

Die Idee bei Insertionsort ist, dass immer ein Element entnommen und an der richtigen Stelle eingefügt wird. Damit keine Vertauschungen sondern lediglich Verschiebeoperationen.

Auf Grund dieses Unterschieds würde ich diesen Algorithmus nicht als Insertionsort bezeichnen.

Insertionsort – Wikipedia

de.wikipedia.org

Insertionsort entnimmt der unsortierten Eingabefolge ein beliebiges Element und fügt es an richtiger Stelle in die (anfangs leere) Ausgabefolge ein. Geht man hierbei in der Reihenfolge der ursprünglichen Folge vor, so ist das Verfahren stabil. Wird auf einem Array gearbeitet, so müssen die Elemente hinter dem neu eingefügten Element verschoben werden. Dies ist die eigentlich aufwendige Operation des Insertionsorts. Das Auffinden der richtigen Einfügeposition kann über eine binäre Suche vergleichsweise effizient erfolgen.

Aber das mag eine Definitionsfrage sein, aber das ist der Punkt, der mir etwas aufstösst.