Bester Sortieralgorithmus für kurze Arrays

rosima26

rosima26

Aktives Mitglied
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 🙂
 
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.
 
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 hat gesagt.:
Und wenn man jetzt auch noch die Anzahl an Vergleichen auf das minimum reduzieren möchte?
Zum Vergrößern anklicken....
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
 
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
 
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: 
[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;  

        }



    }



}
 
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
 
Java: 
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
 
rosima26 hat gesagt.:
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
Zum Vergrößern anklicken....
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.
 
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 de.wikipedia.org
 
Neumi5694 hat gesagt.:
Grundsätzlich verwende ich mittlerweile den Standard-Algorithmus von Java, ich glaube, die verwenden dafür immer noch Timsort.
Zum Vergrößern anklicken....
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:
Java: 
        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);
Code: 
array created in seconds: 1190
array sorted in seconds: 20
 
Zuletzt bearbeitet:
Oneixee5 hat gesagt.:
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]
Zum Vergrößern anklicken....
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.
 
Neumi5694 hat gesagt.:
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.
Zum Vergrößern anklicken....
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.
 
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
 
yfons123 hat gesagt.:
Java: 
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
Zum Vergrößern anklicken....
Was das hier betrifft komme ich eher auf n^2-n Vergleiche im Worst-Case
Wie kann das sein?
 
rosima26 hat gesagt.:
Was das hier betrifft komme ich eher auf n^2-n Vergleiche im Worst-Case
Wie kann das sein?
Zum Vergrößern anklicken....
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:

Java: 
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);
    }
}
 
mihe7 hat gesagt.:
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:

Java: 
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);
    }
}
Zum Vergrößern anklicken....
Danke, dachte aber dass als Vergleiche nur explizit die Elementvergleiche eines Arrays herangezogen werden dürfen.. Was zählt denn dann alles als Vergleich ?
 
rosima26 hat gesagt.:
Danke, dachte aber dass als Vergleiche nur explizit die Elementvergleiche eines Arrays herangezogen werden dürfen.. Was zählt denn dann alles als Vergleich ?
Zum Vergrößern anklicken....
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.
 
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
 
rosima26 hat gesagt.:
Gibt dann aber ja noch andere Algorithmen die O(nlog(n)) haben. Dann sollte ich eher so einen wählen oder?
Zum Vergrößern anklicken....
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.
 
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.
 
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 ;-)
 
Oneixee5 hat gesagt.:
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.
Zum Vergrößern anklicken....
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.
 
Zuletzt bearbeitet:
httpdigest hat gesagt.:
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?
Zum Vergrößern anklicken....
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?
Java: 
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;

    }

}
 
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?
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Bester Stream für ein Spiel?
Antworten: 15
klausurvorbereitung uni HILFE!! kurze fragen,kurze antworten
Antworten: 9
Aktionen zwischen zwei Klassen: Bester Weg?
Antworten: 10
Projekte den BuildPath hinzufügen - Bester Weg?
Antworten: 6
Bester Weg Methode bei Fehler abzubrechen
Antworten: 3

Zurück
Oben