Laden...

Sortieralgorithmen (bubble sort, insertion sort, selection sort + eigener algorithmus)

Erstellt von bluedragon vor 15 Jahren Letzter Beitrag vor 15 Jahren 24.804 Views
B
bluedragon Themenstarter:in
101 Beiträge seit 2008
vor 15 Jahren
Sortieralgorithmen (bubble sort, insertion sort, selection sort + eigener algorithmus)

Beschreibung:

Also da ich mal das Thema Sortieralgorithmen in der Schule behandelt habe, bzw. es 2-3 Schulstunden "angeschnitten" wurde, habe ich mich mal selbst informiert, was es so gibt und mal 4 Stück programmiert. 3 davon sind Ideen aus dem Internet (diese sind zum sortieren von Zahlen gedacht) und 1er ist von mir selber kreiert und auch (mag arrogant klingen) die schnellste Methode um (vor allem) große Datenmengen, die aus Strings bestehen (is ja oft ein Problem, das handling mit Strings bei einigen), zu sortieren.

Erst kommen die 3 "geklauten", dann mein Eigener.

Dieser trägt den Namen Bubblesort. Das rührt daher, weil immer 2 Zahlen, die direkt nebeneinander "liegen", betrachtet werden und man es sich so vorstellen kann, als sei eine Luftblase dort, die diese beiden umschließt.
Der Algorithmus funktioniert so, dass nach jedem Durchlauf, geschaut wird ob bei dem vorigem Durchlauf getauscht wurde und ob dieser schon n-mal durchgelaufen ist. Wenn das Letzte mal nicht getauscht wurde oder schon n-Durchläufe (im worse-case) geschehen sind, bedeutet das automatisch, dass alle Elemente soritert sind.


public void bubbleSort(ArrayList elemente ) 
{
  int  n = elemente.Count, help;
  bool vertauscht;
  do
  {
      vertauscht  = falsch;  
      for(int i = 0; i < n; i++)
         if(elemente[i] > elemente[i+1]) 
         {
            help = elemente[i];
            elemente[i] = elemente[i+1];
            elemente[i+1] = help; 
            vertauscht = true;
         }
    n--;
  while(vertauscht && n > 0)
}

Dieser hier trägt den Namen Selectionsort. Den Namen erhielt er, weil der Algorithmus n-mal, die zu sortierenden Elemente, durchgeht und sich jedes mal das kleineste raussucht, um es mit dem n-ten zu tauschen.
Dadurch ergibt sich nach jedem Durchlauf ein schon sortierter Teil und ein unsortierter Teil. D.h. brauch man bei jedem weiteren Durchlauf nur noch anzahl_der_elemente - n Elemente zu betrachten.



public void selectionSort(ArrayList elemente)
{
    for (int i = 0; i < elemente.Count; i++)
    {
        int min = i;
        for (int j = i + 1; j < elemente.Count; j++)
            if (elemente[j] < elemente[min])
                min = j;

        string tmp = elemente[min];
        elemente[min] = elemente[i];
        elemente[i] = tmp;
    }
}

Der Nächste heißt Insertionsort. Er bekam den Namen, weil dieser davon ausgeht, das n+1 Elemente schon sortiert sind (n = Anzahl der Durchläufe) und er sich dann das erste Element der unsortierten Elemente nimmt und direkt an die richtige Stelle in der Liste platziert.


private void insertionSort(ArrayList elemente)
{
    int i, austausch = 0, key;

    for (int j = 2; j < elemente.Count; j++)
    {
        key = elemente[j];
        i = j - 1;
        while (i >= 0 && teilmenge[i] > key)
        {
            elemente[i + 1] = elemente[i];
            i--;
        }
        elemente[i + 1] = key;
    }
}

Und hier kommt mein Algorithmus mit dem Namen Nameless 😉 Ne mir ist kein Name eingefallen =)
Bedinung ist eine Liste von n-Elementen zu haben, die rein aus Strings besteht und jeder String kann endlich viele Zeichen haben.
Das Prinzip ist, dass man beim Aufruf die Liste hat und bei allen Strings an Stelle n den kleinsten Buchstaben raussucht, dann erneut überprüft welsche Strings denn alle diesen kleinsten Buchstaben an Stelle n aufweisen können und diese dann separat in eine ArraList kommen. Alle anderen die ein anderes Zeichen an Stelle n haben, werden in eine Andere ArrayList gepackt.
Wenn man dann sortiere rekursiv Aufruft und als Parameter, die Erste Liste nimmt, wo schon die n-Zeichen gleich sind und als zweiten Parameter das n+1-te Zeichen übergibt, dann wird wieder von neu angefangen. Dadurch, dass man bei jedem Aufruf erst überprüft, ob nur noch 1 Element in der ArrayList ist, bedeutet das, dass dieses Element richtig ist und in der fertigen Liste abgelegt werden kann.
Die rekursive Aufrufs-Reihenfolge ist ja Umgangssprachlich "rufe erst den schon annähernd sortierten Teil neu auf und überprüfe ab dem nächsten Zeichen. Danach rufe den unsortierten Teil auf, mit den noch komplett unsortierten Strings."
Dadurch ergibt sich, dass autmatisch das kleinste Element nach oben rückt, weil es immer in die ArrayList mit den 'schon-sortierten-teilen' gepackt wird und das größte Element nach unten, weil diese immer in den unsortierten Teil gepackt wird.
Wenn das kleinste soweit oben ist, dass es allein im sortierten Teil ist, dann bedeutet das, dass es automatisch sortiert ist. Dann das 2-kleinste usw.



ArrayList fertig = new ArrayList(); //ArrayList wo am ende alles fertig sortiert vor zufinden ist

private void sortiere(ArrayList teil, int zeichen)
{ 
    //wenn die arraylist nur noch aus einem element besteht, dann ist dieses
    //element automatisch sortiert und soll in die fertige arrayliste gepackt werden
    if(teil.Count == 1)
        fertig.Add(teil[0]);
    else if (teil.Count > 0)
    {
        ArrayList help1 = new ArrayList(); //die ArrayList wo die, bis zu dem zeichen-stem Buchstaben richtig sortierten, Strings reinkommen 

        ArrayList help2 = new ArrayList(); //unsortierter Teil

        //es wird zu Beginn davon augegangen, dass im ersten String der zeichen-ste Buchstabe am kleinsten ist 
        string help_char = teil[0].ToString()[zeichen].ToString(); 

        for(int i = 0; i < teil.Count; i++) //kleinsten Buchstaben herrausfinden
        {                    
            if (String.Compare(help_char, teil[i].ToString()[zeichen].ToString()) > 0)
            {
                //wenn der erste teil größer ist,dann das Andere zwichenspeichern in help_char
                help_char = teil[i].ToString()[zeichen].ToString();   
            }
        }


        for(int j = 0; j < teil.Count; j++)
        {
            //die arrayliste durchlaufen lassen und schauen, ob der kleinste buchstabe
            //mit dem an der Stelle 'zeichen' übereinstimmt
            //wenn ja --> gesamten String in die sortierte ArrayList packen
            //wenn nein --> gesamten String in die unsortierte Arraylist packen
            if (String.Compare(teil[j].ToString()[zeichen].ToString(), help_char) == 0)
                help1.Add(teil[j].ToString());
            else
                help2.Add(teil[j].ToString());
        }
        //sortiere nochmal aufrufen mit der Arraylist wo bis zu dem zeichen-stem Buchstaben alles gleich ist
        //aber diesmal beim nächsten zeichen prüfen
        sortiere(help1, zeichen + 1); 
        
        //den ganzen unsortierten teil neuaufrufen und dort wieder den kleinsten
        //buchstaben rauspicken und sortieren/auf die ArrayListen verteilen
        sortiere(help2, zeichen);
    }
}

// "gestartet" wird der Algorithmus mit "sortieren(elemente, 0)" , weil 'elemente' 
//eine ArrayList mit unsortierten Strings ist und 0 das Start- oder Erst-Zeichen in einem String ist

Sorry für den vielen Text, aber ich möchte es, von vornherein, so verständlich machen wie es nur geht 🙂

Schlagwörter:*bubble sort *insertion sort *selection sort *rekursive sortierung *sortieren durch rekursion *rekursiver algorithmus

Bin wie imer für konstruktive Kritik offen =)

MfG
bluedragon

Man muss viel gelernt haben, um nach etwas, worüber man nicht Bescheid weiß, richtig fragen zu können.

Wenn du jemandem vertrauen kannst, erübrigt sich ein Vertrag. Kannst du ihm nicht vertrauen, ist ein Vertrag nutzlos.

49.485 Beiträge seit 2005
vor 15 Jahren

Hallo bluedragon,

ich möchte es, von vornherein, so verständlich machen wie es nur geht

das ist dir in meinen Augen gut gelungen. Ist ein netter, wenn auch nicht vollständiger Einblick in das Thema Sortieren. Natürlich gibt es auch einige Anmerkungen dazu.

Wenn es einem nur darauf ankommt, zu sortieren (und nicht wie dir das Thema Sortieren zu verstehen), wird man keinen der Algorithmen nehmen, sondern Array.Sort oder List<>.Sort verwenden.

ArrayList gehört in die Mottenkiste und sollte wie alle untypisierten Collections aus System.Collections nicht mehr benutzt werden. Stattdessen würde man List<T> (und die anderen typisierten Collections aus System.Collections.Generic) verwenden.

Man würde entsprechend die Algorithmen besser als generische Methoden mit ILIst<T> als Parameter in Kombination mit den Interfaces IComparable<T> und/oder IComparer<T> schreiben.

Dein eigener Algorithmus ist nett ausgedacht, aber letztlich nicht so schnell, wie du dir erhoffst. Im Vergleich zu den anderen vorgestellten Verfahren mag er sich tapfer schlagen, aber meistens wird das in Array.Sort bzw. List<>.Sort verwende Quicksort deutlich schneller sortieren.

herbivore

B
bluedragon Themenstarter:in
101 Beiträge seit 2008
vor 15 Jahren

Ja den Quicksort habe ich mir auch durchgelesen, bzw einige der Algorithmen die es zum sortieren gibt, aber ich wollte mal eine eigene Kreation rekursiv entwerfen.
Das Quicksort schneller ist, sagt einerseits der Name und andererseits die Tatsache wie er funktioniert. Mag etwas plump klingen, aber dieser ist wirklich mit Abstand der schnellste Sortieralgorithmus. Denn er unterteilt (ähnlich wie ich) auch erst die gesamte Liste und legt die Mitte mit einem sogenannten "pivo" fest. Dann wird verglichen/getauscht und die beiden Teile die sich ergeben, rekursive übergeben und wieder unterteil, mit pivo versehen, verglichen, getauscht und wieder übergeben. das Geht dann wie bei mir so weiter, bis nur noch Teile übrig bleiben, die automatisch sortiert sind.
Was den Quicksort im Gegensatz zu meinem noch einen Schritt schneller macht (meiner ist ja nicht langsam 🙂), ist die Tatsache, dass bei mir minimum 1 Element in einer ArrayList übrig bleiben darf, damit es sortiert ist, beim Quicksort ist ein Teil schon zwichen 1 und 3 Elemten fertig sortiert !

Und danke für die Kritik, das Lob und die Information darüber, dass ArrayListen veraltet sind !!!

MfG
bluedragon

Man muss viel gelernt haben, um nach etwas, worüber man nicht Bescheid weiß, richtig fragen zu können.

Wenn du jemandem vertrauen kannst, erübrigt sich ein Vertrag. Kannst du ihm nicht vertrauen, ist ein Vertrag nutzlos.

1.200 Beiträge seit 2007
vor 15 Jahren

Quick Sort braucht im worst case quadratische Zeit, Merge Sort hingegen läuft konstant und ist deswegen für große Datenmengen oder bereits sehr "vorsortierte" Listen die bessere Wahl imho. Ich gehe aber davon aus, dass dies so im .NET Framework verwirklicht ist und dort eine Optimierung greift. Alles andere würde mich verwundern.

Grundsätzlich denke ich: Gerade zum Sortieren ist es besser einen bewährten Algorithmus aus einer Bibliothek zu nehmen, als etwas der Marke Eigenbau einzusetzen. Sonst kommt irgendwann das böse Erwachen.

Aber für deinen eigenen Algorithmus muss ich dir Respekt zollen, bluedragon. Das hast du sehr gut hinbekommen.

Ich weiss nicht ob du schon diese Website kennst, aber wenn du dich für Sortieralgorithmen interessierst, wird sie dir sicher gefallen:

http://www.sorting-algorithms.com/

Shift to the left, shift to the right!
Pop up, push down, byte, byte, byte!

YARRRRRR!

B
bluedragon Themenstarter:in
101 Beiträge seit 2008
vor 15 Jahren

Danke auch für dein Lob und auch für die Seite, habe sie gerade überflogen und ich muss sagen, dass sie mir echt interessant erscheint. Vom MergeSort habe ich bis dato noch nix gehört, werde ihn mir aber auch mal einverleiben. Ausserdem finde ich den ShellSort noch sehr interessant, denn dieser scheint auch eine sehr geringe Laufzeit aufzuweisen.

Danke ersmal an euch.

Es kann sein, dass ich hier das Forum falsch verstanden habe, dachte hier kann man auch seine Programmierungen vorstellen, um sie kritisieren zu lassen, damit man sie verbessert. Ich wusste nicht, dass es lediglich für die Nutzung Anderer gut sein soll. Denn es ist mir schon klar, dass es immer bessere Methoden gibt, es gibt sogar bestimmt einen Algorithmus, der besser als der der Lib von C# ist, vielleicht wurde dieser nur noch nicht entdeckt 🙂 Wenn ich das nun auch wieder missverstanden habe, bitte ich um Aufklärung 🙂

MfG
bluedragon

Man muss viel gelernt haben, um nach etwas, worüber man nicht Bescheid weiß, richtig fragen zu können.

Wenn du jemandem vertrauen kannst, erübrigt sich ein Vertrag. Kannst du ihm nicht vertrauen, ist ein Vertrag nutzlos.

49.485 Beiträge seit 2005
vor 15 Jahren

Hallo bluedragon,

wie dieses Unterforum zu verstehen ist, steht in der Forenbeschreibung. Und da hast du ja jetzt entdeckt, dass es hier vor allem um die Nutzung durch andere geht. 🙂

Was dir wohl eigentlich vorgeschwebt hat, quasi eine Art Codereview durch andere, ist sowieso durch ein Forum kaum zu leisten. Das ist - wenn man es ernsthaft macht - viel zu aufwändig. Und wenn man es nicht ernsthaft machen, bringt es zu wenig. Deshalb lass ich den Thread auch hier stehen. So nützt er auf jeden Fall anderen, die sich für Sortierung interessieren.

Das nur als Erläuterung. Bitte hier keine Diskussion dazu. Vielen Dank!

herbivore

1.361 Beiträge seit 2007
vor 15 Jahren

Hi bluedragon,

von mir auch noch etwas Feedback:

Auch wenn die ersten 3 Algorithmen natürlich alle grottenlangsam sind, hat einer von Ihnen ne Daseinsberechtigung.
(Ok, Bubblesort sieht wenn man ihn visualisiert noch ganz nett aus - aber das mein ich nicht 🙂 )
SelectionSort bietet nämlich einen Vorteil: Er verwendet die wenigsten Verschiebe-Operationen. Und auf Maschinen, wo lesen/vergleichen schnell geht im vergleich zum vertauschen/schreiben, kann der hier manchmal alle andern ausstechen.

Und noch zu anderen Algorithmen:*Wichtig ist auf alle Fälle noch MergeSort. (lässt sich auch wunderbar parallelisieren und wenn man Datenstrukturen hat, die eh in Form von verketteten Listen vorliegen [ohne wahlfreien Zugriff], dann ist das Der Algo der Wahl !)

***QuickSort **(hast du ja schon beschrieben)

HeapSort. Ein weiterer richtig guter Algorithmus. Mit gesicherter O(nlog(n))-Laufzeitkomplexität. Besonders wichtig bei Echtzeit Systemen.
(Militär, Flugwesen, Medizintechnik, ...)
Da reichen "im-Mittel"-Aussagen über die Laufzeit nicht aus. Sondern es muss eine _gesicherte _maximale Zeit her. Und bei QuickSort ist die n^2 und auch wenn HeapSort schon langsamer (im Mittel ist) ist es sicher !

Zusätzlich zu diesen allgemeinen Sortierverfahren, gibs noch spezielle, die die genaue Struktur der Daten ausnutzen (also mehr als nur a < b). Diese können nämlich durch das Zusatzwissen die magische Grenze von nlog(n) durchbrechen.
Dazu gehört auch dein eigener 4ter Algo. (denn du vergleichst Stellenweise, und sowas geht nicht bei allen Dingen, die man einfach nur "vergleichen" kann)
Das ganze geht in Richtung BucketSort/RadixSort, nur dass die dort nicht wie du rekursiv einen Behälter immer weiter sortieren, sondern immer in einem Rutsch alles bezüglich der n-ten Stelle. (Also mehr Breiten- aus Tiefensuche...auch wenn dieser Graphenvergleich hier etwas hinkt)

Also: Da gibs noch genügend Stoff zum reinknien. 😁

Übrigens: Ich persönlich fänds noch schicker, wenn du im Code von Bubble/Selection-Sort oben eine Hilfsfunktion "swap(array a, index i, index j)" verwendest. Das machts noch untuitiver.
(Am edelsten wahrscheinlich sogar eine Extension-Methode "myArray.swap(i,j)" oder gibt es sowas schon?)

beste Grüße
zommi

946 Beiträge seit 2008
vor 15 Jahren

Das gehört zwar eigentlich nicht hier herein, aber ich habe noch einen schönen Vergleich der Sortiermethoden gefunden:Sorting Contest

B
bluedragon Themenstarter:in
101 Beiträge seit 2008
vor 15 Jahren

Sowohl HeapSort und Radixsort/Bucketsort (beide sehr ähnlich), kenne ich auch und finde ich wie du ebenfalls interessant eben wegen dieser Strukturunabhängigkeit(Radixsort/Bucketsort) der zu sortierenden Elemente. Ich habe die drei in meinem letzten Post nur nicht erwähnt, weil ich nicht zu sehr von dem eigentlichem Code abweichen wollte =)
Aber du hast Recht, wenn du sagst, das diese beiden auch sehr interessant und schnell sind !

MfG
bluedragon

PS: so etwas wie 'swap' gibt es nicht, aber lässt sich ja leicht realisieren/implementieren.

Man muss viel gelernt haben, um nach etwas, worüber man nicht Bescheid weiß, richtig fragen zu können.

Wenn du jemandem vertrauen kannst, erübrigt sich ein Vertrag. Kannst du ihm nicht vertrauen, ist ein Vertrag nutzlos.