BubbleSort



  • Hallo liebe Leute,

    ich möchte gerne für ein Demoprogramm Bubblesort in Form eine generischen Klasse für alle Typen implementieren. Natürlich müssen Objekte von irgendeinem Typ die Methode CompareTo() enthalten, also müsste bei einer Klasse, deren Objekte sortiert werden sollen, das Interface IComparable implementiert sein.
    Der Programmcode ist hinsichtlich der Sortierung noch unvollständig, aber ich stoße auf das folgende Problem

    Hier ein Codeschnipsel der Klasse:

    class Bubblesort<T>
        {
            T[] data;
    
            public bool Ascend { get; set; }
    
            public Bubblesort(T[] _data)
            {
                data = _data;
                Ascend = true;
            }
    
            public void Sortieren()
            {
                // Temporäres Speicherelement
                // für den Tauschvorgang
                T tmp;
    
                for (int i = 0; i < data.Length-1; i++)
                {
                    if(data[i] > data[i+1])
                    {
                        // Es muss getauscht werden
                        tmp = data[i];
                        data[i] = data[i + 1];
                        data[i + 1] = tmp;
                    }
                }
            }
        }
    

    Bei der Zeile mit dem Vergleich erhalte ich eine Fehlemeldung, dass der > Operator nicht auf Operanden des Typs T angewendet werden kann.
    Ich habe mich nun 2 Stunden durch IComparable<T> und IComparer<T> durchgekämpft und bin zu dem Schluss gekommen, dass ich in der obigen Klasse das Interface IComparer<T> implementieren muss, aber leider bin ich noch nicht zum Ziel gekommen. Also:

    class Bubblesort<T>:IComparer<T>
    

    Wäre das so richtig? Kann mir bitte jemand auf die Sprünge helfen?

    LG Uwe



  • Nicht die Klasse muß IComparable<T> (oder IComparer<T>) implementieren, sondern der Generics-Parameter T muß dies. Also gibt das als Einschränkung an:

    class Bubblesort<T> where T : IComparable<T>
    {
      // ...
    }
    

    Dann mußt du aber auch den Vergleich ändern (s. CompareTo):

    if (data[i].CompareTo(data[i+1]) > 0)
    

    PS: Deine Bubblesort-Methode ist auch (noch) nicht richtig.



  • Hallo...

    Danke für die Sprunghilfe 🙂
    das dachte ich auch, aber ich habe den Syntax wohl nicht richtig getroffen.
    Ich hatte nämlich probiert:

    class BubbleSort<T:IComparable>
    

    aber das funktionierte auch nicht...jetzt geht alles.
    Vielen Dank!

    @Th69 sagte in BubbleSort:

    Nicht die Klasse muß IComparable<T> (oder IComparer<T>) implementieren, sondern der Generics-Parameter T muß dies. Also gibt das als Einschränkung an:

    class Bubblesort<T> where T : IComparable<T>
    {
      // ...
    }
    

    Dann mußt du aber auch den Vergleich ändern (s. CompareTo):

    if (data[i].CompareTo(data[i+1]) > 0)
    

    PS: Deine Bubblesort-Methode ist auch (noch) nicht richtig.

    Ich weiß...ist jetzt auch korrigiert...die äußere Schleife hat ja noch gefehlt...aber ich wollte erstmal das grundlegende Problem behoben haben.



  • Falls jemand sich für die Implementation interessiert 😉

    LG Uwe

        public enum Direction
        {
            Ascend, Descend
        };
    
        // Der Datentyp T muss das das Interface
        // IComparable implementieren
        class Bubblesort<T> where T : IComparable
        {
            private T[] data;
    
            private Direction direction;
            public Direction Direction
            {
                get { return direction; }
                set { direction = value; Sort(); }
            }
    
            public Bubblesort(T[] _data)
            {
                data = _data;
                direction = Direction.Ascend;
            }
    
            public Bubblesort(T[] _data, Direction _direction)
            {
                data = _data;
                direction = _direction;
            }
    
            public void Sort()
            {
                // Temporäres Speicherelement
                // für den Tauschvorgang
                T tmp;
                for (int i = data.Length; i > 1; i--)
                {
                    for (int j = 0; j < i - 1; j++)
                    {
                        if (direction == Direction.Ascend)
                        {
                            // Aufsteigend sortieren
                            if (data[j].CompareTo(data[j + 1]) > 0)
                            {
                                // Es muss getauscht werden
                                tmp = data[j];
                                data[j] = data[j + 1];
                                data[j + 1] = tmp;
                            }
                        }
                        else
                        {
                            // Absteigend sortieren
                            if (data[j].CompareTo(data[j + 1]) < 0)
                            {
                                // Es muss getauscht werden
                                tmp = data[j];
                                data[j] = data[j + 1];
                                data[j + 1] = tmp;
                            }
    
                        }
                    }
    
                }
            }
        }
    


  • @uhomm

    Du kannst auch Funktionen für generische Typen nutzen, nicht nur Klassen. Eine (nicht statische) Klasse 'BubbleSort ' ist jedenfalls maximal verwirrend.



  • Muss es nicht heissen; for (int j = 0; j <data.length-1; j++) beide Schleifen müssen über das ganze Array gehen. Meiner Meinung nach ...



  • Bubblesort ist aber teuer, es hat einen quadratischen Aufwand. Da gibt es noch schnellere. zB Quicksort ...Bubblesort hat eine Komplexität von O( n * n ),Quicksort dagegen
    O( n * log n) !



  • @biter sagte in BubbleSort:

    Muss es nicht heissen; for (int j = 0; j <data.length-1; j++) beide Schleifen müssen über das ganze Array gehen. Meiner Meinung nach ...

    Nein.
    Denn nach dem ersten Durchlauf der inneren Schleife ist das größte/kleinste Element an der richtigen Stelle.



  • @biter sagte in BubbleSort:

    Bubblesort ist aber teuer, es hat einen quadratischen Aufwand. Da gibt es noch schnellere. zB Quicksort ...Bubblesort hat eine Komplexität von O( n * n ),Quicksort dagegen
    O( n * log n) !

    Ja.
    Es ist aber eine Übung. Da fängt man mit einfachen Aufgaben an.



  • nehme alles zurück !



  • @biter Im Grunde hast du ja recht, wobei die Alternative zum stabilen Bubblesort nicht Quicksort (der im Übrigen wieder ganz andere Probleme hat [siehe Introsort]) , sondern Insertion-, oder, wenn es nicht in-place sein muss, Mergesort ist.
    Demoprogramm klingt auch danach, als ob der TE grundlegende Sortieralgorithmen evtl. Schülern oder einfach sich selbst näherbringen möchte - und da darf eben der Bubblesort nicht fehlen.
    Einfache Beispielimplementierungen für diverse Sorts in mehreren Sprachen sind z.B. hier zu finden.