BubbleSort in C#

Sortieralgorithmen sind zentrale Bestandteile der Informatik und spielen eine entscheidende Rolle in der Datenverarbeitung. Einer der einfachsten, aber nichtsdestoweniger lehrreichsten Sortieralgorithmen ist der BubbleSort-Algorithmus. In diesem Blogbeitrag werden wir BubbleSort in C# detailliert betrachten, seine Funktionsweise erklären und einige praktische Anwendungsbeispiele zeigen.

Was ist BubbleSort?

BubbleSort ist ein einfacher Sortieralgorithmus, der eine Liste von Elementen durch mehrmaliges Vergleichen benachbarter Elemente sortiert. Der Algorithmus arbeitet, indem er die Elemente wiederholt durchläuft, benachbarte Elemente vergleicht und sie bei Bedarf vertauscht. Dieser Vorgang wird so lange wiederholt, bis die Liste vollständig sortiert ist.

BubbleSort ist ein stabiler Sortieralgorithmus, was bedeutet, dass er die relative Reihenfolge von gleichwertigen Elementen nicht verändert. Er hat jedoch eine hohe Zeitkomplexität von O(n²) im schlimmsten und durchschnittlichen Fall, was ihn bei größeren Datenmengen ineffizient macht.

Funktionsweise von BubbleSort

Der Algorithmus lässt sich in fünf grundlegende Schritte unterteilen:

1. Beginne am Anfang der Liste.
2. Vergleiche das aktuelle Element mit dem nächsten.
3. Vertausche die Elemente, falls das aktuelle größer ist als das nächste.
4. Bewege zum nächsten Element und wiederhole die Schritte 2 und 3 bis zum Ende der Liste.
5. Wiederhole den gesamten Prozess für die gesamte Liste, bis keine Vertauschungen mehr nötig sind.

Implementierung von BubbleSort in C#

Hier ist ein einfaches Beispiel für die Implementierung des BubbleSort-Algorithmus in C#:

using System;

namespace BubbleSortExample
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 64, 34, 25, 12, 22, 11, 90 };

            Console.WriteLine("Unsortiertes Array:");
            PrintArray(array);

            BubbleSort(array);

            Console.WriteLine("Sortiertes Array:");
            PrintArray(array);
        }

        static void BubbleSort(int[] arr)
        {
            int n = arr.Length;
            for (int i = 0; i < n - 1; i++)
            {
                for (int j = 0; j < n - i - 1; j++)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        // Swap arr[j] and arr[j+1]
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

        static void PrintArray(int[] arr)
        {
            foreach (int element in arr)
            {
                Console.Write(element + " ");
            }
            Console.WriteLine();
        }
    }
}

In diesem Beispiel definiert die Methode BubbleSort den Algorithmus selbst. Zunächst wird die Länge des Arrays ermittelt und zwei verschachtelte Schleifen verwendet, um das Array zu durchlaufen und die notwendigen Vertauschungen vorzunehmen. Die PrintArray Methode hilft dabei, den Status des Arrays vor und nach der Sortierung anzuzeigen.

Komplexität von BubbleSort

Die Zeitkomplexität von BubbleSort beträgt:

• Best Case: O(n) - Wenn das Array bereits sortiert ist.
• Average Case: O(n²) - Bei zufälliger Anordnung der Elemente.
• Worst Case: O(n²) - Wenn das Array in umgekehrter Reihenfolge sortiert ist.

Die Space-Komplexität ist O(1), da der Algorithmus nur eine konstante Menge an zusätzlichem Speicher benötigt, unabhängig von der Größe des Eingabe-Arrays.

Zusammenfassung

BubbleSort ist ein einfacher und intuitiver Sortieralgorithmus, der hervorragend für Bildungszwecke geeignet ist. Obwohl er in der Praxis ineffizient für große Datenmengen ist, bietet er einen klaren Einblick in das Konzept des Sortierens und die Funktionsweise von Algorithmen. In C# lässt sich BubbleSort leicht implementieren, und die grundlegende Mechanik kann in verschiedenen Programmierszenarien nützlich sein. Möchten Sie Ihre Programmierfähigkeiten weiter ausbauen, sind komplexere Algorithmen wie Quicksort oder Heapsort eine hervorragende Wahl.