Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Bubble Sort


ffprogramming - Mo 03.08.09 19:11
Titel: Bubble Sort
Ich habe mal den Bouble Sort Algorithmus implediert.
Ich stelle mir die Frage, ob man das nicht noch optimieren kann. Gerade an der Stelle, an der die Variabeln vertauscht werden:


C#-Quelltext 
1:
2:
3:
 
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;



Hier der ganze Code:

C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
 
    public class sort
    {
        public int[] a={12,45,4,9,6,7,4654,44564,455,74,85,49,78,1};

        public void bubblesort()
        {
            
            int t;
            int i;
            int j;

            for (j = 1; j < a.Length; j++)
            {

                for (i = 0; i < a.Length - 1; i++)
                {
                    if (a[i] > a[i + 1])
                    {
                        t = a[i];
                        a[i] = a[i + 1];
                        a[i + 1] = t;
                    }

                }
            }
        }

    }


Kha - Mo 03.08.09 19:40
Bubblesort optimieren :mrgreen: ? Nun, ein paar Sachen kann man am Algorithmus noch drehen:
Anstatt immer n Durchgänge auszuführen, hörst du einfach auf, wenn du im letzten Durchgang gar keine Vertauschung gebraucht hast. Damit hast du einen Best Case von O(n).
Außerdem wird dir auffallen, dass nach n Durchgängen die letzten n Items bereits sortiert sind, die innere Schleife kannst du also einschränken.
Insgesamt wärst du dann bei dieser Version angelangt: http://en.wikipedia.org/wiki/Bubble_sort#Alternative_implementations

Oder meintest du Optimieren vom Code her? Das Vertauschen ist in Ordnung, allerdings solltest du die drei Variablen nicht vor der Schleife deklarieren, sondern erst bei der ersten Verwendung.
Als nächstes solltest du die Methode vollkommen autark gestalten:

C#-Quelltext 
1:
 
static void BubbleSort(int[] a)

Das gleiche Problem gibts bei deiner Library, ich schreibe nachher noch was dazu.

Der letzte Schritt wäre dann die Generalisierung zu

C#-Quelltext 
1:
 
static void BubbleSort<T>(IList<T> a) where T : IComparable<T>

aber das hat vielleicht noch Zeit ;) .


gfoidl - Mo 03.08.09 23:36
Hallo,

schau dir mal dieses Applet [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm] an -> da siehst du bei welchen Sortieralgorithmen die Post abgeht und welche langsam sind.

Vielleicht wählst du dann einen anderen Algorithmus (Quick Sort?).


mfG Gü


ffprogramming - Di 04.08.09 08:00
Es ging mir gar nicht darum den schnellsten Algoritgmus auszuwählen. Ich weiß das Bubble Sort langsam ist und Quicksort schneller ist (oder andere). Das Applet ist gut.
Ich bin kein Profi. Wollte aber mal gerne ein par Kritik/Hilfspunkte wie ich es noch besser machen kann.

Liebe Grüße
Filip


gfoidl - Di 04.08.09 09:09
Tipp:

Wenn du dich mit numerischer Software beschäftigen willst kann ich dir Numerical Recipes [http://www.nr.com/] empfehlen. Die Codes sind (noch) nicht in C# aber die Grundlagen gelten für jede Sprache.

Es gibt noch eine freie Variante für C: http://www.nrbook.com/a/bookcpdf.php (Kapitel 8 fürs Sortieren).


mfG Gü


ffprogramming - Di 04.08.09 11:10
Als nächstes möchte ich vieleicht mal Binäre Suche programmieren.
Wenn ihr wollt poste ich wenn ich fertig bin auch hier.
Noch danke für die Links.


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!