Sortieren mit Insertion Sort

[osion]

Hallo

Ich habe einen InsertionSort (Direktes einfügen). Es sieht aus, als hätte ich was falsch gemacht, weil die Perfomance nicht stimmt, d. h. 10'000 Einträge 2 Sekunde -> 20'000 Einträge 4 Sekunden.

Seht ihr einen Fehler?

public class InsertionSort {
    /**
     *
     * @param array
     */
    public static void insertionSort(final Integer[] array){
        int elt;
        int j;

        if(array == null){
            return;
        }

        for(int i=1; i< array.length;i++){
            elt = array[i];
            j = i;
            while ((j > 0) && (array[j-1] > elt)){
                array[j] = array[j - 1];
                j--;
            }
            array[j] = elt;
        }
    }
}

 

[Blender3D]

weil die Perfomance nicht stimmt, d. h. 10'000 Einträge 2 Sekunde -> 20'000 Einträge 4 Sekunden.

Der Code macht nicht den Eindruck O(n) zu sein. Bei einem vorsortierten Array trifft das wohl zu.
Andernfalls liefert er O(n^2) --> bei verdoppeln der Einträger verdoppelt sich die Laufzeit nicht sondern wird entsprechend länger.

 

[osion]

Der Code macht nicht den Eindruck O(n) zu sein. Bei einem vorsortierten Array trifft das wohl zu.
Andernfalls liefert er O(n^2) --> bei verdoppeln der Einträger verdoppelt sich die Laufzeit nicht sondern wird entsprechend länger.

Ich meinte, dass ich bei meiner Messung kein O(n^2) erhalte, sondern mal n oder mal viel mehr als n^2. Mein Dozent meint, dass müsste an meinem Alg. liegen, aber ich glaube nicht.

 

[Blender3D]

Mein Dozent meint, dass müsste an meinem Alg. liegen, aber ich glaube nicht.

Der Algorithmus dürfte stimmen. Er sollte ein Laufzeitverhalten falls vorsortiert von O(n) haben. Sonst O(n^2)
Bei n = 10.000 -> 10.000^2 als Worstcase = 100.000.000 Durchläufe
Bei n = 20.000 -> 20.000^2 als Worstcase = 400.000.000 Durchläufe.

Ich habe einen InsertionSort (Direktes einfügen). Es sieht aus, als hätte ich was falsch gemacht, weil die Perfomance nicht stimmt, d. h. 10'000 Einträge 2 Sekunde -> 20'000 Einträge 4 Sekunden.

Das ist abhängig davon, ob die Daten großteils vorsortiert sind oder nicht.
Bei einem Worstcase Szenario sollten 20.000 Datensätze 4 mal länger brauchen als 10.000 Datensätze.
Sind die 20.000 aber vorsortiert brauchen sie lediglich 20.000 Durchläufe.
Also wären sie 5.000 mal schneller fertig als die unsortierten 10.000 Datensätze.
Das gilt es, bei Deinen Messungen zu berücksichtigen.