Kurs Diskussion:Algorithmen und Datenstrukturen/Kapitel 2/BubbleSort

Fehler in der Programmlogik?

Der bubblesort-Parameter "n" scheint ja völlig unabhängig vom Array "a" zu sein. Wenn ich nun aber ein konkretes "n" verwende, welches größer als die Länge des Arrays "a" ist, gibt es Probleme.

1. Gibt's keine bessere Variante, die Länge eines Arrays herauszufinden?
2. Falls es gewollt ist, nur "n" Elemente des Arrays zu sortieren, dann sollte aber eine Überprüfung rein, dass dieses "n" nicht größer als die Array-Elementeanzahl ist.

--Exxu 09:44, 30. Okt. 2006 (CET)

Du hast völlig Recht, habs korrigiert und ein Kommentar hinzugefügt. In Oberon kann man mit LEN(a) die allozierte/deklarierte Länge des Arrays herausfinden, wäre aber so nicht sehr flexibel. Danke! --Pedro.Gonnet 10:58, 30. Okt. 2006 (CET)

Landau-Notation

Danke fuer die Korrekturen, Exxu! Nach meinem Wissen aber sind die ${\mathcal {O}}(\cdot )$ der Landau-Notation Mengen. Man schreibt daher $f(n)\in {\mathcal {O}}(\cdot )$ (also $f(x)$ in ${\mathcal {O}}(\cdot )$) und nicht 'in der Groessenordnung'... Oder taeusche ich mich da? --Pedro.Gonnet 18:56, 30. Okt. 2006 (CET)

Andere Sprachen

Musste feststellen, das hier nur eine Oberon-Implementierung von BubbleSort vorhanden ist. Daher hab ich hier zwei Implementierungen für dich:
Einmal Visual Basic .NET beim Sortieren eines Integer-Arrays und eine generische Implementierung in C#:

Implementierung in Visual Basic .NET

Eine Function, welche ein Array vom Typ Integer sortiert, würde wie folgt implementiert:

 1.	Public Shared Function BubbleSort(ByVal toSort() As Integer)
 2.		
 3.		Dim temp As Integer
 4.		Dim done As Boolean = False
 5.		
 6.		For k As Integer = toSort.Lenght - 1 To 0 Step -1
 7.		
 8.		done = True
 9.		
10.			For i As Integer = 0 To k Step 1
11.			
12.				If toSort(i) < toSort(i + 1) Then
13.				
14.					temp = toSort(i)
15.					toSort(i) = toSort(i + 1)
16.					toSort(i + 1) = temp
17.					done = False
18.				
19.				End If
20.
21.			Next i
22.
23.			If done Then
24.
25.				Exit For
26.
27.			End If
28.
29.		Next k
30.
31.	End Function 

Implementierung in C#

Ab Version 2.0 sind in C# generische Datentypen möglich. Eine generische Implementierung, welche alle Datentypen sortieren kann, die, die Schnittstelle System.IComparable implementieren, sähe folgendermaßen aus:

 1.        public static void BubbleSort<T>(T[] toSort)
 2.            where T : System.IComparable    /* Einschränkung des Typparameters;
 3.                                             * Dadurch sind nur Typen zugelassen, die das Interface System.IComparable implementieren.
 4.                                             * Dadurch verfügen alle Instanzen von T über eine Methode CompareTo(object obj), die angibt,
 5.                                             * ob ein Objekt größer, gleich oder kleiner als ein anderes ist.
 6.                                             * Die Verwendung anderer Typen führt zu einem Kompilierfehler
 7.                                             */
 8.        {
 9.            T temp;
10.            bool done = false;
11.
12.            for (int k = toSort.Length - 1; k > 0 && !done; --k)
13.            {
14.                done = true;
15.
16.                for (int i = 0; i < k; ++i)
17.                {
18.                    if (toSort[i].CompareTo(toSort[i + 1]) > 0)
19.                    {
20.                        temp = toSort[i];
21.                        toSort[i] = toSort[i + 1];
22.                        toSort[i + 1] = temp;
23.                        done = false;
24.                    }
25.                }
26.            }
27.        } 

Gruß Hölzl • @ 15:37, 8. Jul. 2009 (CEST)