Bester Sortieralgorithmus für kurze Arrays

[rosima26]

Moin,
mich würde mal interessieren was ihr so meint, was der schnellste Algorithmus für kurze Arrays (bis 10 Zeichen) ist.
Habe jetzt immer wieder von Insertion-Sort gehört, der hat aber im Worst-Case ja auch O(n^2) während die großen wie Merge Heap usw ja meistens O(nlogn) oder so haben was ja schneller ist. Was würdet ihr sagen eignet sich für kurze Arrays im Worst Case am besten ? Und spielt die Länge des Arrays da überhaupt eine Rolle oder ist Worst Case immer Worst Case ?
Danke schonmal

 

[KonradN]

Worst Case ist immer Worst case. Aber spielt es eine Rolle? Bei kleinem n ist es egal. Also wenn es nur um n=10 geht, dann ist der Overhead vermutlich am interessantesten. Da kann man also ggf. ein einfaches Bubblesort mit zwei Schleifen nehmen, da dies am wenigsten Overhead hat.

Also nur um es mal zu vergleichen: 10n ist da das gleiche wie n^2 - also selbst wenn Du einen Linearen Algorithmus hättest der aber pro Element 10 Mal mehr aufwendet, wäre er nicht schneller, als ein Algorithmus, der Quadratisch angeht aber pro Aktion nur 1/10 braucht.

 

[rosima26]

Und wenn man jetzt auch noch die Anzahl an Vergleichen auf das minimum reduzieren möchte?

 

[KonradN]

Dann müsstest Du - so wie bei der Komplexität-Bestimmung - einfach einmal bei jedem Algorithmus, der in Frage kommt, ermitteln was für Vergleiche Du hast (Minimal, im Schnitt, Maximal). Da es um kleines n geht und nicht um die generelle Entwicklung wie bei der O-Notation hast Du hier keine Faktoren zu entfernen.

 

[rosima26]

Danke ^^ hatte nach etwas Recherche und zählen den InsertionSort mit binärer Suche gefunden..

 

[yfons123]

Und wenn man jetzt auch noch die Anzahl an Vergleichen auf das minimum reduzieren möchte?

du kannst sortieralgorithmen mit O(1) hernehmen a la bucket sort der eig genial ist

das problem an allen O(1) algorithmen ist es dass das "universum" mitspielt dh bei blöden werten eskaliert die performance
bei O(log n n) algorithmen spielt das universum keine rolle deswegen ist beim soriteren in java auch der "verbesserte merge sort" ( ist mir so gesagt worden ) umgesetzt da der konsistent immer gleich ist egal wie blöd die werte sind

O(n²) algorithmen sind halt deppen eifnach verglichen mit merge sort, irgend einen tod stirbst du immer also musst du halt schauen welche art du wählen willst um abzudanken

 

[rosima26]

Ja also hauptaugenmerk würde ich wohl auf wenige Vergleiche im Worst-Case legen, da ist aber insertionSort gut dabei oder? Hat wenn ich mich nicht irre im Worst case bei nem 10er Array nur 20 Vergleiche

 

[yfons123]

der bucket sort hat 0
( ist er deswegen immer schneller?... witzigerweise nicht!)

 

[rosima26]

Ja suche aber einen vergleichsbasierten Sonst hätte ich Radix genommen !

 

[yfons123]

ob es einen vergleichsbasierten afu O(1) gibt weis ich nicht

 

[rosima26]

Das wäre jetzt mein Code, sehe ich schon richtig dass der 2 Vergleiche hat oder ? Also quasi je nach Länge des Arrays werden 2*array.length Vergleiche ausgeführt

[CODE=java]void sort(int[] a) {



        int l = a.length;



        for (int i = 1; i < l; ++i) {



            int c = a[i];

            int j = i - 1;



            while (j >= 0 && a[j] > c) {



               

               



                a[j + 1] = a[j];



                j --;      

            }

            a[j + 1] = c;  

        }



    }



}

 

[thecain]

du kannst sortieralgorithmen mit O(1) hernehmen a la bucket sort der eig genial ist

Wie kommst du auf O(1)? Bucketsort ist O(n)

 

[yfons123]

nvm

 

[yfons123]

Wie kommst du auf O(1)? Bucketsort ist O(n)

ups

 

[yfons123]

also bei deinem algorithmus bei 10 maximal dämlich angelgeten wert musst du 72 mal einen vergleich durchführen
bei 100 werten brauchst du nur 9900 vergleiche

 

[rosima26]

Hä wie das denn 😂

 

[yfons123]

class Office {
    void sort(int[] a) {

        int l = a.length;
        int vergleiche = 0;
        for (int i = 1; i < l; ++i) {

            int c = a[i];

            int j = i - 1;

            while (j >= 0 && a[j] > c) {
                vergleiche += 2;
                a[j + 1] = a[j];

                j--;

            }

            a[j + 1] = c;

        }
        System.out.println(vergleiche);
    }

}

public class Test {
    public static void main(String[] args) {
        Office office = new Office();
        // office.printPassword();
        int[] arr = new int[100];
        for (int i = 100; i > 0; i--) {
            arr[100-i] = i;
        }
        office.sort(arr);
        for (var val : arr) {
            System.out.print(val);
        }
        
        
    }
}

probiers selber aus

 

[mihe7]

Das wäre jetzt mein Code, sehe ich schon richtig dass der 2 Vergleiche hat oder ? Also quasi je nach Länge des Arrays werden 2*array.length Vergleiche ausgeführt

Nein. Der Vergleich in der Schleifenbedingung der for-Schleife wird n-mal (n = array.length) ausgeführt und für jede der n-1 Iterationen wird nun eine zweite Schleife durchlaufen, in der alle Elemente, die größer sind als das Element a[i] verschoben werden. In der Schleifenbedingung der inneren Schleife stehen zwei Vergleiche.

Im best case ist das Array aufsteigend sortiert, so dass je for-Schleifen-Iteration nur die beiden Vergleiche der while-Schleifenbedingung durchgeführt werden müssen. Macht (n-1)*2 innere Vergleiche und n Vergleiche für die for-Schleifenbedingung, insgesamt also n+(n-1)*2 = 3n - 2 Vergleiche.

Im worst case ist das Array absteigend sortiert. Dann müssen in der ersten for-Schleifen-Iteration n-1 Elemente, in der zweiten Iteration n-2 Elemente, in der i-ten Iteration n-i Elemente mit Hilfe der while-Schleife verschoben werden. Zum Verschieben von n-1 Elementen sind 2*n Vergleiche notwendig, heißt also 2n + 2(n-1) + 2(n-2) + .. Vergleiche.

Der kleine Gauß liefert uns 2 * (n²+n)/2, also n² + n Vergleiche für die while-Schleife. Hinzu kommen die n Vergleiche der for-Schleifenbedingung macht also n² + 2n Vergleiche gesamt.

 

[Neumi5694]

Bei einem Array der Länge 10 ist die Performance gelinde gesagt sc***egal, bei vielen CPUs geht in wenigen Durchgängen.
Grundsätzlich verwende ich mittlerweile den Standard-Algorithmus von Java, ich glaube, die verwenden dafür immer noch Timsort. Der profitiert davon, wenn die Daten teilweise schon sortiert sind.

Timsort – Wikipedia

de.wikipedia.org

 

[Oneixee5]

Grundsätzlich verwende ich mittlerweile den Standard-Algorithmus von Java, ich glaube, die verwenden dafür immer noch Timsort.

In der Doku steht: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets.
Grundsätzlich mache ich mir auch keine Gedanken über den Sortieralgorithmus. Der ist in Java vorhanden und funktioniert. Was braucht man noch? Gedanken über einen Sortieralgorithmus für kurze Arrays sind völliger Unfug. Wie teuer soll denn so ein Programm werden? Bis der Algorithmus ausgereift und getestet ist, hat man längst einer VM mehr Power verpasst oder neue Hardware angeschafft - falls wirklich die Sortierung eines kurzen Arrays zum Problem werden sollte!
Hier noch mal kurz zu Relation, zur Simulation des Aufwandes ein Array zu erzeugen und zu sortieren:

        long start = System.currentTimeMillis();

        final int[] randomIntsArray =
                IntStream.generate(() -> new Random().nextInt(100)).limit(Integer.MAX_VALUE / 2).toArray();

        System.out.println("array created in seconds: " + (System.currentTimeMillis() - start) / 1000);

        start = System.currentTimeMillis();

        Arrays.sort(randomIntsArray);

        System.out.println("array sorted in seconds: " + (System.currentTimeMillis() - start) / 1000);

array created in seconds: 1190
array sorted in seconds: 20

 

[Neumi5694]

In der Doku steht: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets.
[/CODE]

Ah, wurde also mittlerweile geändert, auch gut
Da sieht man mal, wie lange es her ist.


Sortieralgorithmen umzusetzen ist eine nette Übungsaufgabe, aber in der praktischen Anwendung sollte man einfach den Profis vertrauen, die sich bereits sehr lange damit beschäftigt haben. Möchte mathematische Geschichte schreiben und da noch was rausholen, ist dieses Forum nicht der geeignete Startpunkt.

 

[mihe7]

Sortieralgorithmen umzusetzen ist eine nette Übungsaufgabe, aber in der praktischen Anwendung sollte man einfach den Profis vertrauen, die sich bereits sehr lange damit beschäftigt haben.

Ja, das ist hier sicher der Fall, wobei man prinzipiell schon zwischen dem allgemeinen Fall und Spezialfällen unterscheiden kann und sich durchaus Situationen ergeben können, wo eine andere Implementierung sinnvoller ist, die dann eben in O(n) läuft.

 

[rosima26]

Geht mir nur ums Verständnis, habe nicht vor hier mathematische Geschichte zu schreiben.

 

[rosima26]

Suche einen vergleichsbasierten Sortieralgorithmus für ein unsortiertes Array mit einer einstelligen Länge, der im Worst-Case möglichst wenige Vergleiche hat. Das ist alles

 

[rosima26]

class Office {
    void sort(int[] a) {

        int l = a.length;
        int vergleiche = 0;
        for (int i = 1; i < l; ++i) {

            int c = a[i];

            int j = i - 1;

            while (j >= 0 && a[j] > c) {
                vergleiche += 2;
                a[j + 1] = a[j];

                j--;

            }

            a[j + 1] = c;

        }
        System.out.println(vergleiche);
    }

}

public class Test {
    public static void main(String[] args) {
        Office office = new Office();
        // office.printPassword();
        int[] arr = new int[100];
        for (int i = 100; i > 0; i--) {
            arr[100-i] = i;
        }
        office.sort(arr);
        for (var val : arr) {
            System.out.print(val);
        }
       
       
    }
}

probiers selber aus

Was das hier betrifft komme ich eher auf n^2-n Vergleiche im Worst-Case
Wie kann das sein?

 

[mihe7]

Was das hier betrifft komme ich eher auf n^2-n Vergleiche im Worst-Case
Wie kann das sein?

Ich sehe gerade, dass sich ich in #18 nicht berücksichtigt habe, dass die for-Schleife bei 1 beginnt und beim Eintreffen der Abbruchbedingung in der while-Schleife nur ein Vergleich durchgeführt wird...

Im Code müssten jedenfalls noch der Vergleich der for-Schleife und die Vergleiche der Abbruchbedingungen (while und for-Schleife) gezählt werden:

class Office {
    void sort(int[] a) {

        int l = a.length;
        int vergleiche = 0;
        for (int i = 1; i < l; ++i) {
            vergleiche++; // Vergleich i < l
            int c = a[i];

            int j = i - 1;

            while (j >= 0 && a[j] > c) {
                vergleiche += 2;
                a[j + 1] = a[j];

                j--;

            }
            vergleiche++; // Abbruchbedingung der while-Schleife erreicht

        }
        vergleiche++; // Abbruchbedingung der for-Schleife
        System.out.println(vergleiche);
    }
}

 

[rosima26]

Ich sehe gerade, dass sich ich in #18 nicht berücksichtigt habe, dass die for-Schleife bei 1 beginnt und beim Eintreffen der Abbruchbedingung in der while-Schleife nur ein Vergleich durchgeführt wird...

Im Code müssten jedenfalls noch der Vergleich der for-Schleife und die Vergleiche der Abbruchbedingungen (while und for-Schleife) gezählt werden:

class Office {
    void sort(int[] a) {

        int l = a.length;
        int vergleiche = 0;
        for (int i = 1; i < l; ++i) {
            vergleiche++; // Vergleich i < l
            int c = a[i];

            int j = i - 1;

            while (j >= 0 && a[j] > c) {
                vergleiche += 2;
                a[j + 1] = a[j];

                j--;

            }
            vergleiche++; // Abbruchbedingung der while-Schleife erreicht

        }
        vergleiche++; // Abbruchbedingung der for-Schleife
        System.out.println(vergleiche);
    }
}

Danke, dachte aber dass als Vergleiche nur explizit die Elementvergleiche eines Arrays herangezogen werden dürfen.. Was zählt denn dann alles als Vergleich ?

 

[mihe7]

Danke, dachte aber dass als Vergleiche nur explizit die Elementvergleiche eines Arrays herangezogen werden dürfen.. Was zählt denn dann alles als Vergleich ?

Das kommt ja auf die Fragestellung an. Wenn Du mich pauschal nach den wenigsten Vergleichen fragst, dann zähle ich natürlich jeden Vergleich Bzgl. der Laufzeitkomplexität ist das Jacke wie Hose, da schaust Du Dir an: ah, zwei verschachtelte Schleifen, ok, wie oft laufen die grob (das sieht man meist sogar auf den ersten Blick, hier ist es nicht ganz so ersichtlich) und dann weißt Du schon: O(n²).

Nachtrag: weil es mir gerade auffällt: wenn von einem vergleichsbasierten Verfahren die Rede ist, dann ist damit natürlich gemeint, dass die Elemente miteinander verglichen werden.

 

[rosima26]

Gut, das wäre hier ja O(n^2). Gibt dann aber ja noch andere Algorithmen die O(nlog(n)) haben. Dann sollte ich eher so einen wählen oder? Also zb Heapsort oder MergeSort

 

[mihe7]

Gibt dann aber ja noch andere Algorithmen die O(nlog(n)) haben. Dann sollte ich eher so einen wählen oder?

In der Regel schon.

Aber wie schon mehrfach gesagt, spielt das bei kleinen n keine Rolle bzw. kann es bei kleinen n sogar sein, dass der O(n log(n))-Algorithmus in der Praxis eine längere Laufzeit (z. B. für die Initialisierung benötigter Datenstrukturen) und ggf. auch in der Theorie mehr Schritte benötigt als der O(n²)-Algorithmus.

 

[rosima26]

Ja danke, darum geht es aber in diesem Fall nicht.

 

[httpdigest]

Wenn `n = 10` ist, geht es sehr wohl in diesem Fall darum, dass jegliche Komplexitätsklassenbetrachtung völlig hinfällig ist und das einzige, was zählt und was dir wirklich was bringt, echtes Benchmarking/Messen von echtem Code unter Realbedingungen ist. Ich empfehle hier JMH.

 

[rosima26]

Ja, verstehe ich völlig. Aber geht hier um ne Übung unter Isolierung eines speziellen Faktors. Dass das in der Realität wieder anders ist bezweifle ich nicht ;-)

 

[httpdigest]

Was genau ist denn dann aber deine Frage?
Im ersten Post hast du geschrieben:

mich würde mal interessieren was ihr so meint, was der schnellste Algorithmus für kurze Arrays (bis 10 Zeichen) ist.

Aber jetzt willst du was genau haben? Du willst nicht wissen, was der _schnellste_ Algorithmus ist, sondern... was genau?

 

[mrBrown]

In der Doku steht: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets.

Das gilt für primitive Arrays, für Objekt-Arrays wird eine TimSort-Adaption genutzt.

Timsort dürfte zu weniger „zufälligen“ Zugriffen führen und damit besserer Cache-Ausnutzung, zusätzlich ist er stabil, was bei primitiven egal ist, bei Objekten aber nicht.

 

[rosima26]

Was genau ist denn dann aber deine Frage?
Im ersten Post hast du geschrieben:

Aber jetzt willst du was genau haben? Du willst nicht wissen, was der _schnellste_ Algorithmus ist, sondern... was genau?

Wollte wissen welcher Algorithmus im Worst-Case die wenigesten Vergleiche braucht. Hab jetzt mal einen HeapSort geschrieben. Leider counted der nicht richtig, da müsste eigentlich 6 rauskommen im Worstcase. Hab ich die counts falsch gesetzt?

public class Sort4A {
    
    int count = 0;

    void sort(int[] a) {

        buildHeap(a);
        

        for (int i = a.length - 1; i > 0; i--) {
            tausche(a, 0, i);

            heapify(a, 0, i - 1);

        }
        
    }

    void buildHeap(int[] a) {

        for (int i = a.length / 2; i >= 0; i--) {
            heapify(a, i, a.length - 1);
        }

    }

    void heapify(int[] a, int zuUntersuchenderKnoten, int heapGroesse) {
        
        int linkerSohn = 2 * zuUntersuchenderKnoten + 1;
        int rechterSohn = 2 * zuUntersuchenderKnoten + 2;
        int sohn;
        if (linkerSohn <= heapGroesse && rechterSohn > heapGroesse) {
            
            
            if (a[linkerSohn] < a[zuUntersuchenderKnoten]) {
                count++;
                tausche(a, linkerSohn, zuUntersuchenderKnoten);
            }
        } else {
            if (rechterSohn <= heapGroesse) {
                
                
                sohn = a[linkerSohn] < a[rechterSohn] ? linkerSohn : rechterSohn;
                count+=1;
                if (a[sohn] < a[zuUntersuchenderKnoten]) {
                    count++;
                    tausche(a, zuUntersuchenderKnoten, sohn);
                    heapify(a, sohn, heapGroesse);

                }
            }
        }

    }

    private void tausche(int[] a, int element1, int element2) {
        int temp = a[element1];
        a[element1] = a[element2];
        a[element2] = temp;

    }

}

 

[mihe7]

Wollte wissen welcher Algorithmus im Worst-Case die wenigesten Vergleiche braucht.

Elementvergleiche.

 

[rosima26]

Habs jetzt raus, er braucht wohl 6 Vergleiche. Was ich nicht verstehe ist, wieso er 6 und nicht 8 braucht. 4log2(4) ist doch 8 und nicht 6?

 

[mihe7]

Habs jetzt raus, er braucht wohl 6 Vergleiche. Was ich nicht verstehe ist, wieso er 6 und nicht 8 braucht. 4log2(4) ist doch 8 und nicht 6?

Weil n log(n) nur die grobe Hausnummer ist, um die es geht.

 

[rosima26]

http://www.allisons.org/ll/AlgDS/Sort/Heap/ die können das hier exakt berechnen, hast du ne Ahnung wie sich der Faktor bei stats berechnen lässt?

 

[mihe7]

count / (a.length * Math.log(a.length)/Math.log(2))