Bubble sort program in C#

Bubble sort is a simple comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order until the entire array is sorted. Bubble sort has a time complexity of O(n^2) in the average and worst cases.

Here's an explanation of the bubble sort algorithm step by step:

1. Compare adjacent elements: Starting from the beginning of the array, compare each element with its adjacent element.
2. Swap if necessary: If the adjacent elements are in the wrong order (e.g., the current element is greater than the next element in ascending order), swap them.
3. Repeat until sorted: Repeat steps 1 and 2 for each element in the array until the array is fully sorted. Each iteration moves the largest element to its correct position at the end of the array.
4. Optimize: Bubble sort can be optimized by introducing a flag that tracks whether any swaps were made during a pass. If no swaps were made during an iteration, it means the array is already sorted, and the algorithm can terminate early.

using System;

public class BubbleSort
{
    public static void Main()
    {
        int[] arr = { 64, 25, 12, 22, 11 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(int[] arr)
    {
        int n = arr.Length;
        bool swapped;

        for (int i = 0; i < n - 1; i++)
        {
            swapped = false;

            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;
                    swapped = true;
                }
            }

            // If no swap was made in the inner loop, the array is already sorted
            if (!swapped)
            {
                break;
            }
        }
    }

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

In this example, the Sort method implements the bubble sort algorithm. The Main method initializes an array, calls the Sort method to sort the array, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
64 25 12 22 11 
Sorted array:
11 12 22 25 64 

The program demonstrates the step-by-step execution of the bubble sort algorithm on the given array and outputs the sorted array.

Bubble sort is straightforward to implement but generally less efficient than other sorting algorithms, especially for larger datasets. It is mainly used for educational purposes or for sorting small arrays where simplicity is more important than performance.