Bubble Sort (Φυσαλίδα): Απλή Εξήγηση

Τι είναι το Bubble Sort;

Το Bubble Sort είναι ένας απλός αλγόριθμος ταξινόμησης που χρησιμοποιείται για την οργάνωση ενός πίνακα ή λίστας σε αύξουσα ή φθίνουσα σειρά. Ονομάζεται “φυσαλίδα” γιατί οι μεγαλύτερες (ή μικρότερες) τιμές «ανεβαίνουν» (ή «κατεβαίνουν») στην επιφάνεια του πίνακα, σαν φυσαλίδες.

Πώς Λειτουργεί;

Ο αλγόριθμος λειτουργεί με την εξής διαδικασία:

  1. Σύγκριση: Συγκρίνει διαδοχικά ζευγάρια στοιχείων στον πίνακα.
  2. Ανταλλαγή: Εάν τα στοιχεία είναι σε λάθος σειρά, τα ανταλλάσσει.
  3. Επανάληψη: Επαναλαμβάνει τη διαδικασία για όλα τα στοιχεία στον πίνακα, μέχρι να μην γίνουν περισσότερες ανταλλαγές.

Βήματα του Bubble Sort

Ακολουθεί η ψευδογλώσσα για να κατανοήσεις τη διαδικασία:

ΛΕΞΗ BubbleSort(A)
    n = μήκος(A)
    ΓΙΑ i ΑΠΟ 0 ΕΩΣ n-1
        ΓΙΑ j ΑΠΟ 0 ΕΩΣ n-i-2
            ΕΑΝ A[j] > A[j+1] ΤΟΤΕ
                Swap(A[j], A[j+1]) // Ανταλλαγή
            ΤΕΛΟΣ_ΕΑΝ
        ΤΕΛΟΣ_ΓΙΑ
    ΤΕΛΟΣ_ΓΙΑ
ΤΕΛΟΣ

C# Υλοποίηση

Ακολουθεί η υλοποίηση του Bubble Sort στην C#:

using System;

class BubbleSortExample
{
    public 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(ref arr[j], ref arr[j + 1]);
                }
            }
        }
    }

    // Συνάρτηση ανταλλαγής
    public static void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("Αρχικός πίνακας:");
        Console.WriteLine(string.Join(", ", arr));

        // Εκτέλεση του Bubble Sort
        BubbleSort(arr);

        Console.WriteLine("Ταξινομημένος πίνακας:");
        Console.WriteLine(string.Join(", ", arr));
    }
}

Πώς Λειτουργεί ο Κώδικας

  1. BubbleSort: Κάνει τη διαδικασία ταξινόμησης του πίνακα.
    • Εξωτερικός βρόχος: Επαναλαμβάνει τη διαδικασία για κάθε στοιχείο του πίνακα.
    • Εσωτερικός βρόχος: Συγκρίνει κάθε ζευγάρι στοιχείων και τα ανταλλάσσει αν είναι σε λάθος σειρά.
  2. Swap: Ανταλλάσσει τις τιμές των δύο στοιχείων.

Παράδειγμα

Ας δούμε πώς λειτουργεί ο αλγόριθμος με ένα παράδειγμα:

  1. Αρχικός πίνακας: { 64, 34, 25, 12, 22, 11, 90 }
  2. Πρώτη Επανάληψη:
    • Συγκρίνουμε και ανταλλάσσουμε:
    • { 34, 25, 12, 22, 11, 64, 90 }
  3. Δεύτερη Επανάληψη:
    • Συγκρίνουμε ξανά:
    • { 25, 12, 22, 11, 34, 64, 90 }
  4. Συνεχίζουμε μέχρι να ταξινομηθούν όλα τα στοιχεία.

Συμπέρασμα

Ο αλγόριθμος Bubble Sort είναι απλός και εύκολος να κατανοηθεί. Χρησιμοποιείται συνήθως για εκπαιδευτικούς σκοπούς και για μικρούς πίνακες. Αν και δεν είναι ο πιο αποδοτικός αλγόριθμος για ταξινόμηση, είναι καλός για να μάθεις τη διαδικασία της ταξινόμησης.

bubble-sortDownload