Bubble Sort

ffprogramming · Beiträge: 44 Win XP C# Java C PHP

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:

markieren

C#-Quelltext

1:
2:
3:

t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;

Hier der ganze Code:

markieren

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 · Verfasst: 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: en.wikipedia.org/wik...tive_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:

markieren

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

markieren

C#-Quelltext

1:	static void BubbleSort<T>(IList<T> a) where T : IComparable<T>

aber das hat vielleicht noch Zeit

.

_________________
>λ=

gfoidl · Verfasst: Mo 03.08.09 23:36

Hallo,

schau dir mal dieses Applet 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ü

_________________
Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!

ffprogramming · Beiträge: 44 Win XP C# Java C PHP

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 · Verfasst: Di 04.08.09 09:09

Tipp:

Wenn du dich mit numerischer Software beschäftigen willst kann ich dir Numerical Recipes 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: www.nrbook.com/a/bookcpdf.php (Kapitel 8 fürs Sortieren).

mfG Gü

_________________
Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!

ffprogramming · Beiträge: 44 Win XP C# Java C PHP

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.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme