myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
   » Plugin für Firefox
   » Plugin für IE
   » Gadget für Windows
» Regeln
» Wie poste ich richtig?
» Datenschutzerklärung
» wbb-FAQ

Mitglieder
» Liste / Suche
» Stadt / Anleitung dazu
» Wer ist wo online?

Angebote
» ASP.NET Webspace
» Bücher
» Zeitschriften
   » dot.net magazin
» Accessoires

Ressourcen
» .NET-Glossar
» guide to C#
» openbook: Visual C#
» openbook: OO
» .NET BlogBook
» MSDN Webcasts
» Search.Net

Team
» Kontakt
» Übersicht
» Wir über uns
» Bankverbindung
» Impressum

» Unsere MiniCity
MiniCity
» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Gemeinschaft » .NET-Komponenten und C#-Snippets » Sortieralgorithmen (bubble sort, insertion sort, selection sort + eigener algorithmus)
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

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

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
bluedragon bluedragon ist männlich
myCSharp.de-Mitglied

Dabei seit: 11.06.2008
Beiträge: 95
Entwicklungsumgebung: Visual Studio 2005
Herkunft: Nordrheinwestfalen


bluedragon ist offline Füge bluedragon Deiner Kontaktliste hinzu

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

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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.

C#-Code:
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.

C#-Code:
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.

C#-Code:
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 fröhlich
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.

C#-Code:
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 fröhlich

MfG
bluedragon

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von bluedragon am 24.11.2008 19:52.

24.11.2008 19:52 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Team (Admin)

images/avatars/avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 48.721
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo bluedragon,

Zitat:
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
24.11.2008 20:08 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
bluedragon bluedragon ist männlich
myCSharp.de-Mitglied

Dabei seit: 11.06.2008
Beiträge: 95
Entwicklungsumgebung: Visual Studio 2005
Herkunft: Nordrheinwestfalen

Themenstarter Thema begonnen von bluedragon

bluedragon ist offline Füge bluedragon Deiner Kontaktliste hinzu

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
24.11.2008 20:19 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
GMLOD
myCSharp.de-Mitglied

images/avatars/avatar-2654.jpg


Dabei seit: 30.11.2007
Beiträge: 1.200


GMLOD ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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/
24.11.2008 20:23 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
bluedragon bluedragon ist männlich
myCSharp.de-Mitglied

Dabei seit: 11.06.2008
Beiträge: 95
Entwicklungsumgebung: Visual Studio 2005
Herkunft: Nordrheinwestfalen

Themenstarter Thema begonnen von bluedragon

bluedragon ist offline Füge bluedragon Deiner Kontaktliste hinzu

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von bluedragon am 24.11.2008 21:04.

24.11.2008 21:03 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Team (Admin)

images/avatars/avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 48.721
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
24.11.2008 21:11 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
zommi zommi ist männlich
myCSharp.de-Poweruser/ Experte

images/avatars/avatar-2617.png


Dabei seit: 14.11.2007
Beiträge: 1.291
Entwicklungsumgebung: VS 2005+2010
Herkunft: Berlin


zommi ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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 smile )
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(n*log(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 n*log(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. großes Grinsen

Ü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
24.11.2008 21:27 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
SeeQuark SeeQuark ist männlich
myCSharp.de-Mitglied

images/avatars/avatar-2825.jpg


Dabei seit: 27.10.2008
Beiträge: 946
Entwicklungsumgebung: Emacs


SeeQuark ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Das gehört zwar eigentlich nicht hier herein, aber ich habe noch einen schönen Vergleich der Sortiermethoden gefunden: Sorting Contest
24.11.2008 21:41 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
bluedragon bluedragon ist männlich
myCSharp.de-Mitglied

Dabei seit: 11.06.2008
Beiträge: 95
Entwicklungsumgebung: Visual Studio 2005
Herkunft: Nordrheinwestfalen

Themenstarter Thema begonnen von bluedragon

bluedragon ist offline Füge bluedragon Deiner Kontaktliste hinzu

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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 fröhlich
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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von bluedragon am 24.11.2008 21:45.

24.11.2008 21:45 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als 5 Jahre.
Der letzte Beitrag ist älter als 5 Jahre.
Antwort erstellen


© Copyright 2003-2014 myCSharp.de-Team. Alle Rechte vorbehalten. 25.07.2014 08:43