Algorytmy — opis i kod/pseudokod

Sortowanie bąbelkowe

Sortowanie bąbelkowe

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        // Demo: dwa sortowania malejąco
        double[] demo = { 3.2, 7.5, -1.0, 7.51, 2.0, 2.0 };
        var copy = (double[])demo.Clone();

        int bubbleIterations;
        BubbleSortDescending(demo, out bubbleIterations);
        SelectionSortDescending(copy);

        Console.WriteLine("Bubble sort (malejąco): " + string.Join(", ", demo));
        Console.WriteLine("Liczba iteracji (porównań) w bubble sort: " + bubbleIterations);
        Console.WriteLine("Selection sort (malejąco): " + string.Join(", ", copy));
        Console.WriteLine();

        // Badanie złożoności (średnia liczba iteracji bubble sort)
        int[] sizes = { 100, 110, 120, 130, 140, 150 };
        const int trials = 10;
        Console.WriteLine("Średnia liczba iteracji bubble sort (po 10 uruchomieniach):");
        foreach (int n in sizes)
        {
            double avg = AverageBubbleIterations(n, trials);
            Console.WriteLine($"n={n,-3} -> średnio {avg:F0} iteracji");
        }
    }

    /// 
    /// Sortowanie bąbelkowe malejąco z optymalizacją:
    /// 1) ograniczanie prawej granicy (ostatni element po przebiciu jest na miejscu),
    /// 2) wcześniejsze wyjście, gdy w przebiegu nie było zamian.
    /// Zwraca liczbę iteracji (porównań) w pętli wewnętrznej.
    /// 
    public static void BubbleSortDescending(double[] a, out int iterations)
    {
        iterations = 0;
        int last = a.Length - 1;
        while (last > 0)
        {
            bool swapped = false;
            for (int i = 0; i < last; i++)
            {
                iterations++; // licznik porównań (iteracji)
                if (a[i] < a[i + 1])
                {
                    (a[i + 1], a[i]) = (a[i], a[i + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break; // już posortowana
            last--;               // ostatni element jest na miejscu
        }
    }

    /// 
    /// Sortowanie przez wybieranie (selection sort) malejąco.
    /// 
    public static void SelectionSortDescending(double[] a)
    {
        int n = a.Length;
        for (int i = 0; i < n - 1; i++)
        {
            int maxIdx = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] > a[maxIdx]) maxIdx = j;

            if (maxIdx != i)
                (a[i], a[maxIdx]) = (a[maxIdx], a[i]);
        }
    }

    /// 
    /// Generuje losową tablicę double i zwraca średnią liczbę iteracji
    /// (porównań) bubble sorta po 'trials' uruchomieniach.
    /// 
    private static double AverageBubbleIterations(int n, int trials)
    {
        var rng = new Random();
        long sum = 0;
        for (int t = 0; t < trials; t++)
        {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++)
                arr[i] = rng.NextDouble() * 1000.0; // losowe double

            BubbleSortDescending(arr, out int iters);
            sum += iters;
        }
        return (double)sum / trials;
    }
}