2 - Basic Sorting Algorithms

Basic sorting algorithms are simple to understand and implement but typically have O(n²) time complexity. Despite their inefficiency for large datasets, they are valuable for educational purposes and can be practical for small collections or partially sorted data.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.

How It Works

Start at the beginning of the array.
Compare the first two elements. If the first is greater than the second, swap them.
Move to the next pair of elements and repeat the comparison and swap if necessary.
After reaching the end of the array, start again from the beginning.
Continue this process until no more swaps are needed.

Implementation

public static void BubbleSort<T>(T[] array) where T : IComparable<T>
{
    int n = array.Length;
    bool swapped;
    
    for (int i = 0; i < n - 1; i++)
    {
        swapped = false;
        
        for (int j = 0; j < n - i - 1; j++)
        {
            if (array[j].CompareTo(array[j + 1]) > 0)
            {
                // Swap array[j] and array[j+1]
                T temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        
        // If no swapping occurred in this pass, the array is sorted
        if (!swapped)
            break;
    }
}

Optimization

The implementation above includes an optimization: it tracks whether any swaps occurred in each pass. If no swaps occur, the array is already sorted, and the algorithm can terminate early.

Characteristics

Time Complexity:
- Best Case: O(n) when the array is already sorted
- Average Case: O(n²)
- Worst Case: O(n²)
Space Complexity: O(1) - in-place sorting
Stability: Stable - preserves the relative order of equal elements
Adaptivity: Adaptive - performs better on partially sorted arrays

When to Use

Educational purposes
Very small datasets
When simplicity is more important than efficiency
When the array is already nearly sorted

Selection Sort

Selection Sort divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly finds the minimum element from the unsorted sublist and moves it to the end of the sorted sublist.

How It Works

Find the minimum element in the unsorted sublist.
Swap it with the first element of the unsorted sublist.
Move the boundary between the sorted and unsorted sublists one element to the right.
Repeat until the entire list is sorted.

Implementation

public static void SelectionSort<T>(T[] array) where T : IComparable<T>
{
    int n = array.Length;
    
    for (int i = 0; i < n - 1; i++)
    {
        // Find the minimum element in the unsorted part
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (array[j].CompareTo(array[minIndex]) < 0)
            {
                minIndex = j;
            }
        }
        
        // Swap the found minimum element with the first element
        if (minIndex != i)
        {
            T temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

Characteristics

Time Complexity:
- Best Case: O(n²)
- Average Case: O(n²)
- Worst Case: O(n²)
Space Complexity: O(1) - in-place sorting
Stability: Unstable - can change the relative order of equal elements
Adaptivity: Non-adaptive - performs the same regardless of initial order

When to Use

When memory is limited (it makes the minimum number of swaps)
Small datasets
When simplicity is more important than efficiency

Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It's much like sorting playing cards in your hand: you pick up one card at a time and insert it into its correct position.

How It Works

Start with the second element (assume the first element is already sorted).
Compare the current element with the previous elements.
If the previous element is greater than the current element, move the previous element one position ahead.
Repeat step 3 until you find the correct position for the current element.
Insert the current element at the correct position.
Repeat steps 2-5 for all elements in the array.

Implementation

public static void InsertionSort<T>(T[] array) where T : IComparable<T>
{
    int n = array.Length;
    
    for (int i = 1; i < n; i++)
    {
        T key = array[i];
        int j = i - 1;
        
        // Move elements of array[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && array[j].CompareTo(key) > 0)
        {
            array[j + 1] = array[j];
            j--;
        }
        
        array[j + 1] = key;
    }
}

Binary Insertion Sort

A variation of Insertion Sort that uses binary search to find the correct position for insertion, reducing the number of comparisons:

public static void BinaryInsertionSort<T>(T[] array) where T : IComparable<T>
{
    int n = array.Length;
    
    for (int i = 1; i < n; i++)
    {
        T key = array[i];
        int insertionPoint = BinarySearch(array, key, 0, i - 1);
        
        // Shift elements to make room for the key
        Array.Copy(array, insertionPoint, array, insertionPoint + 1, i - insertionPoint);
        array[insertionPoint] = key;
    }
}

private static int BinarySearch<T>(T[] array, T key, int low, int high) where T : IComparable<T>
{
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        int comparison = key.CompareTo(array[mid]);
        
        if (comparison < 0)
            high = mid - 1;
        else
            low = mid + 1;
    }
    
    return low;
}

Characteristics

Time Complexity:
- Best Case: O(n) when the array is already sorted
- Average Case: O(n²)
- Worst Case: O(n²)
Space Complexity: O(1) - in-place sorting
Stability: Stable - preserves the relative order of equal elements
Adaptivity: Adaptive - performs better on partially sorted arrays

When to Use

Small datasets
Nearly sorted data
Online algorithms (where elements come one at a time)
When simplicity and low overhead are important

Comparison of Basic Sorting Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space	Stable	In-Place	Adaptive
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Yes	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Yes

Performance Characteristics

Bubble Sort: Makes the most comparisons and swaps, but can detect when the array is sorted.
Selection Sort: Makes the fewest swaps (n-1) but doesn't adapt to partially sorted arrays.
Insertion Sort: Generally performs best among the three for real-world data, especially for small or nearly sorted arrays.

Visualizing Basic Sorting Algorithms

Understanding how these algorithms work visually can be very helpful:

Bubble Sort Visualization

Initial array: [5, 3, 8, 4, 2]

Pass 1:
Compare 5 and 3 -> Swap -> [3, 5, 8, 4, 2]
Compare 5 and 8 -> No swap -> [3, 5, 8, 4, 2]
Compare 8 and 4 -> Swap -> [3, 5, 4, 8, 2]
Compare 8 and 2 -> Swap -> [3, 5, 4, 2, 8]

Pass 2:
Compare 3 and 5 -> No swap -> [3, 5, 4, 2, 8]
Compare 5 and 4 -> Swap -> [3, 4, 5, 2, 8]
Compare 5 and 2 -> Swap -> [3, 4, 2, 5, 8]

Pass 3:
Compare 3 and 4 -> No swap -> [3, 4, 2, 5, 8]
Compare 4 and 2 -> Swap -> [3, 2, 4, 5, 8]

Pass 4:
Compare 3 and 2 -> Swap -> [2, 3, 4, 5, 8]

Sorted array: [2, 3, 4, 5, 8]

Selection Sort Visualization

Initial array: [5, 3, 8, 4, 2]

Pass 1:
Find minimum in [5, 3, 8, 4, 2] -> 2
Swap 5 and 2 -> [2, 3, 8, 4, 5]

Pass 2:
Find minimum in [3, 8, 4, 5] -> 3
No swap needed -> [2, 3, 8, 4, 5]

Pass 3:
Find minimum in [8, 4, 5] -> 4
Swap 8 and 4 -> [2, 3, 4, 8, 5]

Pass 4:
Find minimum in [8, 5] -> 5
Swap 8 and 5 -> [2, 3, 4, 5, 8]

Sorted array: [2, 3, 4, 5, 8]

Insertion Sort Visualization

Initial array: [5, 3, 8, 4, 2]

Pass 1:
Consider 3, insert before 5 -> [3, 5, 8, 4, 2]

Pass 2:
Consider 8, already in correct position -> [3, 5, 8, 4, 2]

Pass 3:
Consider 4, insert after 3 and before 5 -> [3, 4, 5, 8, 2]

Pass 4:
Consider 2, insert at beginning -> [2, 3, 4, 5, 8]

Sorted array: [2, 3, 4, 5, 8]

Practical Considerations

Implementation in C#

When implementing these algorithms in C#, consider:

Generic Implementation: Use generics to make your sorting algorithm work with any comparable type.
Comparison Delegates: Allow custom comparison logic through delegates or lambda expressions.
Extension Methods: Implement as extension methods for arrays or collections.

Example of a more flexible implementation:

public static class SortingExtensions
{
    public static void BubbleSort<T>(this T[] array, Comparison<T> comparison = null)
    {
        comparison ??= Comparer<T>.Default.Compare;
        
        int n = array.Length;
        bool swapped;
        
        for (int i = 0; i < n - 1; i++)
        {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; j++)
            {
                if (comparison(array[j], array[j + 1]) > 0)
                {
                    // Swap array[j] and array[j+1]
                    T temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            
            if (!swapped)
                break;
        }
    }
    
    // Similar implementations for other sorting algorithms...
}

Built-in Sorting in .NET

Remember that .NET provides efficient built-in sorting methods:

// For arrays
Array.Sort(myArray);

// For lists
myList.Sort();

// With custom comparison
Array.Sort(myArray, (x, y) => x.CompareTo(y));

// With LINQ
var sortedCollection = myCollection.OrderBy(x => x.Property);

These built-in methods typically use more efficient algorithms like Quicksort or Heapsort, with optimizations for different data patterns.

Comprehensive Example: Basic Sorting Algorithms in Practice

The following example demonstrates a practical implementation of basic sorting algorithms with detailed instrumentation and visualization capabilities. This implementation is designed to be educational, showing how these algorithms work step by step and providing insights into their performance characteristics.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace BasicSortingAlgorithms
{
    /// <summary>
    /// Provides implementations and analysis tools for basic sorting algorithms.
    /// </summary>
    public class BasicSortingDemo
    {
        // Performance counters
        private static int _comparisons;
        private static int _swaps;
        
        // Visualization settings
        private static bool _visualize;
        private static StringBuilder _visualizationLog;
        
        /// <summary>
        /// Main entry point for the basic sorting algorithms demonstration.
        /// </summary>
        public static void Main()
        {
            Console.WriteLine("Basic Sorting Algorithms Demonstration");
            Console.WriteLine("======================================\n");
            
            // Demonstrate algorithm behavior with a small array
            int[] smallArray = { 5, 3, 8, 4, 2, 9, 1, 7, 6 };
            
            Console.WriteLine("Original Array: " + string.Join(", ", smallArray));
            Console.WriteLine();
            
            // Demonstrate Bubble Sort
            DemonstrateBubbleSort(smallArray);
            
            // Demonstrate Selection Sort
            DemonstrateSelectionSort(smallArray);
            
            // Demonstrate Insertion Sort
            DemonstrateInsertionSort(smallArray);
            
            // Compare performance with larger arrays
            ComparePerformance();
            
            // Demonstrate adaptive behavior
            DemonstrateAdaptiveBehavior();
        }
        
        #region Algorithm Demonstrations
        
        /// <summary>
        /// Demonstrates the Bubble Sort algorithm with visualization.
        /// </summary>
        /// <param name="originalArray">The array to sort.</param>
        private static void DemonstrateBubbleSort(int[] originalArray)
        {
            Console.WriteLine("BUBBLE SORT DEMONSTRATION");
            Console.WriteLine("-------------------------");
            
            // Create a copy of the original array
            int[] array = (int[])originalArray.Clone();
            
            // Enable visualization
            _visualize = true;
            _visualizationLog = new StringBuilder();
            _comparisons = 0;
            _swaps = 0;
            
            // Sort with visualization
            BubbleSort(array);
            
            // Display results
            Console.WriteLine("Visualization:");
            Console.WriteLine(_visualizationLog.ToString());
            Console.WriteLine($"Comparisons: {_comparisons}");
            Console.WriteLine($"Swaps: {_swaps}");
            Console.WriteLine($"Sorted Array: {string.Join(", ", array)}");
            Console.WriteLine();
        }
        
        /// <summary>
        /// Demonstrates the Selection Sort algorithm with visualization.
        /// </summary>
        /// <param name="originalArray">The array to sort.</param>
        private static void DemonstrateSelectionSort(int[] originalArray)
        {
            Console.WriteLine("SELECTION SORT DEMONSTRATION");
            Console.WriteLine("---------------------------");
            
            // Create a copy of the original array
            int[] array = (int[])originalArray.Clone();
            
            // Enable visualization
            _visualize = true;
            _visualizationLog = new StringBuilder();
            _comparisons = 0;
            _swaps = 0;
            
            // Sort with visualization
            SelectionSort(array);
            
            // Display results
            Console.WriteLine("Visualization:");
            Console.WriteLine(_visualizationLog.ToString());
            Console.WriteLine($"Comparisons: {_comparisons}");
            Console.WriteLine($"Swaps: {_swaps}");
            Console.WriteLine($"Sorted Array: {string.Join(", ", array)}");
            Console.WriteLine();
        }
        
        /// <summary>
        /// Demonstrates the Insertion Sort algorithm with visualization.
        /// </summary>
        /// <param name="originalArray">The array to sort.</param>
        private static void DemonstrateInsertionSort(int[] originalArray)
        {
            Console.WriteLine("INSERTION SORT DEMONSTRATION");
            Console.WriteLine("---------------------------");
            
            // Create a copy of the original array
            int[] array = (int[])originalArray.Clone();
            
            // Enable visualization
            _visualize = true;
            _visualizationLog = new StringBuilder();
            _comparisons = 0;
            _swaps = 0;
            
            // Sort with visualization
            InsertionSort(array);
            
            // Display results
            Console.WriteLine("Visualization:");
            Console.WriteLine(_visualizationLog.ToString());
            Console.WriteLine($"Comparisons: {_comparisons}");
            Console.WriteLine($"Swaps: {_swaps}");
            Console.WriteLine($"Sorted Array: {string.Join(", ", array)}");
            Console.WriteLine();
        }
        
        #endregion
        
        #region Performance Comparison
        
        /// <summary>
        /// Compares the performance of basic sorting algorithms with different array sizes.
        /// </summary>
        private static void ComparePerformance()
        {
            Console.WriteLine("PERFORMANCE COMPARISON");
            Console.WriteLine("---------------------");
            
            // Test with different array sizes
            int[] sizes = { 100, 1000, 5000 };
            
            foreach (int size in sizes)
            {
                Console.WriteLine($"\nArray Size: {size}");
                Console.WriteLine($"{"Algorithm",-15} {"Time (ms)",-10} {"Comparisons",-12} {"Swaps",-10}");
                Console.WriteLine(new string('-', 47));
                
                // Generate a random array
                int[] randomArray = GenerateRandomArray(size);
                
                // Test Bubble Sort
                MeasurePerformance("Bubble Sort", randomArray, BubbleSort);
                
                // Test Selection Sort
                MeasurePerformance("Selection Sort", randomArray, SelectionSort);
                
                // Test Insertion Sort
                MeasurePerformance("Insertion Sort", randomArray, InsertionSort);
            }
            
            Console.WriteLine();
        }
        
        /// <summary>
        /// Measures the performance of a sorting algorithm.
        /// </summary>
        /// <param name="algorithmName">The name of the algorithm.</param>
        /// <param name="originalArray">The array to sort.</param>
        /// <param name="sortMethod">The sorting method to test.</param>
        private static void MeasurePerformance(string algorithmName, int[] originalArray, Action<int[]> sortMethod)
        {
            // Create a copy of the original array
            int[] array = (int[])originalArray.Clone();
            
            // Reset counters
            _visualize = false;
            _comparisons = 0;
            _swaps = 0;
            
            // Measure execution time
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            
            sortMethod(array);
            
            stopwatch.Stop();
            double milliseconds = stopwatch.Elapsed.TotalMilliseconds;
            
            // Display results
            Console.WriteLine($"{algorithmName,-15} {milliseconds,10:F2} {_comparisons,12} {_swaps,10}");
        }
        
        #endregion
        
        #region Adaptive Behavior Demonstration
        
        /// <summary>
        /// Demonstrates the adaptive behavior of sorting algorithms with partially sorted arrays.
        /// </summary>
        private static void DemonstrateAdaptiveBehavior()
        {
            Console.WriteLine("ADAPTIVE BEHAVIOR DEMONSTRATION");
            Console.WriteLine("------------------------------");
            
            // Generate arrays with different degrees of sortedness
            int size = 1000;
            int[] randomArray = GenerateRandomArray(size);
            int[] nearlySortedArray = GenerateNearlySortedArray(size);
            int[] reversedArray = GenerateReversedArray(size);
            
            Console.WriteLine("\nRandom Array:");
            Console.WriteLine($"{"Algorithm",-15} {"Time (ms)",-10} {"Comparisons",-12} {"Swaps",-10}");
            Console.WriteLine(new string('-', 47));
            MeasurePerformance("Bubble Sort", randomArray, BubbleSort);
            MeasurePerformance("Insertion Sort", randomArray, InsertionSort);
            
            Console.WriteLine("\nNearly Sorted Array:");
            Console.WriteLine($"{"Algorithm",-15} {"Time (ms)",-10} {"Comparisons",-12} {"Swaps",-10}");
            Console.WriteLine(new string('-', 47));
            MeasurePerformance("Bubble Sort", nearlySortedArray, BubbleSort);
            MeasurePerformance("Insertion Sort", nearlySortedArray, InsertionSort);
            
            Console.WriteLine("\nReversed Array:");
            Console.WriteLine($"{"Algorithm",-15} {"Time (ms)",-10} {"Comparisons",-12} {"Swaps",-10}");
            Console.WriteLine(new string('-', 47));
            MeasurePerformance("Bubble Sort", reversedArray, BubbleSort);
            MeasurePerformance("Insertion Sort", reversedArray, InsertionSort);
            
            Console.WriteLine();
        }
        
        #endregion
        
        #region Array Generation Methods
        
        /// <summary>
        /// Generates a random array of integers.
        /// </summary>
        /// <param name="size">The size of the array.</param>
        /// <returns>A random array of integers.</returns>
        private static int[] GenerateRandomArray(int size)
        {
            Random random = new Random(42); // Fixed seed for reproducibility
            int[] array = new int[size];
            
            for (int i = 0; i < size; i++)
            {
                array[i] = random.Next(size * 10);
            }
            
            return array;
        }
        
        /// <summary>
        /// Generates a nearly sorted array of integers.
        /// </summary>
        /// <param name="size">The size of the array.</param>
        /// <returns>A nearly sorted array of integers.</returns>
        private static int[] GenerateNearlySortedArray(int size)
        {
            Random random = new Random(42); // Fixed seed for reproducibility
            int[] array = new int[size];
            
            // Fill with sorted values
            for (int i = 0; i < size; i++)
            {
                array[i] = i;
            }
            
            // Swap a few elements (about 5% of the array)
            int swaps = size / 20;
            for (int i = 0; i < swaps; i++)
            {
                int pos1 = random.Next(size);
                int pos2 = random.Next(size);
                
                int temp = array[pos1];
                array[pos1] = array[pos2];
                array[pos2] = temp;
            }
            
            return array;
        }
        
        /// <summary>
        /// Generates a reversed (descending) array of integers.
        /// </summary>
        /// <param name="size">The size of the array.</param>
        /// <returns>A reversed array of integers.</returns>
        private static int[] GenerateReversedArray(int size)
        {
            int[] array = new int[size];
            
            for (int i = 0; i < size; i++)
            {
                array[i] = size - i;
            }
            
            return array;
        }
        
        #endregion
        
        #region Sorting Algorithm Implementations
        
        /// <summary>
        /// Implements the Bubble Sort algorithm.
        /// Bubble Sort repeatedly steps through the list, compares adjacent elements,
        /// and swaps them if they're in the wrong order.
        /// </summary>
        /// <param name="array">The array to sort.</param>
        public static void BubbleSort(int[] array)
        {
            int n = array.Length;
            bool swapped;
            
            // Visualization: Initial state
            if (_visualize)
            {
                _visualizationLog.AppendLine($"Initial array: [{string.Join(", ", array)}]");
                _visualizationLog.AppendLine();
            }
            
            for (int i = 0; i < n - 1; i++)
            {
                swapped = false;
                
                // Visualization: Start of pass
                if (_visualize)
                {
                    _visualizationLog.AppendLine($"Pass {i + 1}:");
                }
                
                for (int j = 0; j < n - i - 1; j++)
                {
                    // Compare adjacent elements
                    _comparisons++;
                    if (array[j] > array[j + 1])
                    {
                        // Swap them if they are in the wrong order
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                        swapped = true;
                        _swaps++;
                        
                        // Visualization: Show the swap
                        if (_visualize)
                        {
                            _visualizationLog.AppendLine($"  Compare {array[j + 1]} and {temp} -> Swap -> [{string.Join(", ", array)}]");
                        }
                    }
                    else if (_visualize)
                    {
                        // Visualization: Show the comparison without swap
                        _visualizationLog.AppendLine($"  Compare {array[j]} and {array[j + 1]} -> No swap -> [{string.Join(", ", array)}]");
                    }
                }
                
                // If no swapping occurred in this pass, the array is sorted
                if (!swapped)
                {
                    // Visualization: Early termination
                    if (_visualize)
                    {
                        _visualizationLog.AppendLine($"  No swaps in this pass. Array is sorted.");
                    }
                    break;
                }
                
                // Visualization: End of pass
                if (_visualize)
                {
                    _visualizationLog.AppendLine();
                }
            }
        }
        
        /// <summary>
        /// Implements the Selection Sort algorithm.
        /// Selection Sort divides the input list into two parts: a sorted sublist and an unsorted sublist.
        /// It repeatedly finds the minimum element from the unsorted sublist and moves it to the end of the sorted sublist.
        /// </summary>
        /// <param name="array">The array to sort.</param>
        public static void SelectionSort(int[] array)
        {
            int n = array.Length;
            
            // Visualization: Initial state
            if (_visualize)
            {
                _visualizationLog.AppendLine($"Initial array: [{string.Join(", ", array)}]");
                _visualizationLog.AppendLine();
            }
            
            for (int i = 0; i < n - 1; i++)
            {
                // Visualization: Start of pass
                if (_visualize)
                {
                    _visualizationLog.AppendLine($"Pass {i + 1}:");
                }
                
                // Find the minimum element in the unsorted part
                int minIndex = i;
                for (int j = i + 1; j < n; j++)
                {
                    _comparisons++;
                    if (array[j] < array[minIndex])
                    {
                        minIndex = j;
                    }
                }
                
                // Visualization: Show the minimum element found
                if (_visualize)
                {
                    _visualizationLog.AppendLine($"  Find minimum in [{string.Join(", ", array, i, n - i)}] -> {array[minIndex]}");
                }
                
                // Swap the found minimum element with the first element
                if (minIndex != i)
                {
                    int temp = array[i];
                    array[i] = array[minIndex];
                    array[minIndex] = temp;
                    _swaps++;
                    
                    // Visualization: Show the swap
                    if (_visualize)
                    {
                        _visualizationLog.AppendLine($"  Swap {temp} and {array[i]} -> [{string.Join(", ", array)}]");
                    }
                }
                else if (_visualize)
                {
                    // Visualization: No swap needed
                    _visualizationLog.AppendLine($"  No swap needed -> [{string.Join(", ", array)}]");
                }
                
                // Visualization: End of pass
                if (_visualize)
                {
                    _visualizationLog.AppendLine();
                }
            }
        }
        
        /// <summary>
        /// Implements the Insertion Sort algorithm.
        /// Insertion Sort builds the final sorted array one item at a time.
        /// It's much like sorting playing cards in your hand.
        /// </summary>
        /// <param name="array">The array to sort.</param>
        public static void InsertionSort(int[] array)
        {
            int n = array.Length;
            
            // Visualization: Initial state
            if (_visualize)
            {
                _visualizationLog.AppendLine($"Initial array: [{string.Join(", ", array)}]");
                _visualizationLog.AppendLine();
            }
            
            for (int i = 1; i < n; i++)
            {
                // Visualization: Start of pass
                if (_visualize)
                {
                    _visualizationLog.AppendLine($"Pass {i}:");
                    _visualizationLog.AppendLine($"  Consider {array[i]}");
                }
                
                int key = array[i];
                int j = i - 1;
                
                // Move elements of array[0..i-1] that are greater than key
                // to one position ahead of their current position
                while (j >= 0)
                {
                    _comparisons++;
                    if (array[j] > key)
                    {
                        array[j + 1] = array[j];
                        _swaps++; // Count as a swap even though it's technically a move
                        j--;
                        
                        // Visualization: Show the shift
                        if (_visualize)
                        {
                            _visualizationLog.AppendLine($"  Shift {array[j + 1]} right -> [{string.Join(", ", array)}]");
                        }
                    }
                    else
                    {
                        break;
                    }
                }
                
                if (j + 1 != i)
                {
                    array[j + 1] = key;
                    
                    // Visualization: Show the insertion
                    if (_visualize)
                    {
                        _visualizationLog.AppendLine($"  Insert {key} at position {j + 1} -> [{string.Join(", ", array)}]");
                    }
                }
                else if (_visualize)
                {
                    // Visualization: No insertion needed
                    _visualizationLog.AppendLine($"  Already in correct position -> [{string.Join(", ", array)}]");
                }
                
                // Visualization: End of pass
                if (_visualize)
                {
                    _visualizationLog.AppendLine();
                }
            }
        }
        
        #endregion
    }
}

Step-by-Step Explanation

This comprehensive example demonstrates the implementation and analysis of basic sorting algorithms in C#. Let's break it down:

Program Structure:
- The program is organized into a class called BasicSortingDemo with a Main method as the entry point.
- It includes implementations of three basic sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort.
- The code is structured into logical regions for clarity: algorithm demonstrations, performance comparison, adaptive behavior demonstration, array generation, and algorithm implementations.
Algorithm Visualization:
- Each sorting algorithm includes detailed visualization capabilities that show the step-by-step process.
- For Bubble Sort, it shows each comparison and swap operation, highlighting how adjacent elements are compared and swapped.
- For Selection Sort, it shows how the minimum element is found in each pass and swapped with the first unsorted element.
- For Insertion Sort, it shows how each element is inserted into its correct position in the sorted portion of the array.
Performance Measurement:
- The program measures and compares the performance of each algorithm using several metrics:
  - Execution time in milliseconds
  - Number of comparisons performed
  - Number of swaps or moves performed
- These metrics help in understanding the efficiency of each algorithm.
Adaptive Behavior Demonstration:
- The program demonstrates how some algorithms (Bubble Sort and Insertion Sort) adapt to partially sorted data.
- It compares their performance on random, nearly sorted, and reversed arrays.
- This shows why adaptive algorithms can be more efficient in certain scenarios.
Test Data Generation:
- The program generates different types of test data:
  - Random arrays: completely unsorted data
  - Nearly sorted arrays: mostly in order with a few elements out of place
  - Reversed arrays: sorted in descending order
- This allows for testing algorithm performance under different conditions.

Key Concepts Demonstrated

Bubble Sort:
- Repeatedly steps through the list, comparing adjacent elements and swapping them if they're in the wrong order.
- Optimization: Tracks whether any swaps occurred in each pass. If no swaps occur, the array is already sorted.
- Time Complexity: O(n²) in worst and average cases, O(n) in best case (already sorted).
- Space Complexity: O(1) - in-place sorting.
- Adaptive: Performs better on partially sorted arrays.
- Stable: Preserves the relative order of equal elements.
Selection Sort:
- Divides the input into a sorted and an unsorted region, repeatedly finding the minimum element from the unsorted region and moving it to the end of the sorted region.
- Time Complexity: O(n²) in all cases.
- Space Complexity: O(1) - in-place sorting.
- Non-adaptive: Performance doesn't improve for partially sorted arrays.
- Unstable: Can change the relative order of equal elements.
- Advantage: Makes the minimum number of swaps (n-1).
Insertion Sort:
- Builds the final sorted array one item at a time, much like sorting playing cards in your hand.
- Time Complexity: O(n²) in worst and average cases, O(n) in best case (already sorted).
- Space Complexity: O(1) - in-place sorting.
- Adaptive: Performs better on partially sorted arrays.
- Stable: Preserves the relative order of equal elements.
- Advantage: Simple implementation and efficient for small or nearly sorted arrays.

Performance Analysis

The example demonstrates several important performance characteristics:

Comparison Count:
- Selection Sort always performs the same number of comparisons (n(n-1)/2) regardless of the initial order.
- Bubble Sort and Insertion Sort can perform fewer comparisons on partially sorted arrays.
Swap Count:
- Selection Sort performs the fewest swaps (at most n-1).
- Bubble Sort typically performs the most swaps.
- Insertion Sort performs moves rather than swaps, which can be more efficient in some contexts.
Execution Time:
- For random arrays, Insertion Sort is often faster than Bubble Sort but slower than Selection Sort.
- For nearly sorted arrays, Insertion Sort is typically the fastest.
- For reversed arrays, Selection Sort often outperforms the others.
Adaptive Behavior:
- The example clearly shows how Bubble Sort and Insertion Sort adapt to the initial order of the data.
- This adaptivity makes them suitable for scenarios where the data is already partially sorted.

When to Use Each Algorithm

Bubble Sort:
- When simplicity is more important than efficiency
- For very small datasets
- When the array is already nearly sorted
- When detecting whether an array is sorted is part of the requirement
Selection Sort:
- When minimizing the number of swaps is important
- For small datasets
- When memory writes are expensive
- When simplicity is valued over performance
Insertion Sort:
- For small datasets (typically less than 20 elements)
- When the array is already nearly sorted
- As part of more complex algorithms (like Quicksort for small subarrays)
- When implementing online algorithms (where elements come one at a time)

Conclusion

Basic sorting algorithms are foundational in computer science education. While they're not typically used for large datasets in production environments, understanding them provides insights into algorithm design, analysis, and optimization. They also serve as building blocks for more complex algorithms and can be practical in specific scenarios, especially for small datasets or when simplicity is valued over performance.

The comprehensive example provided demonstrates not only how these algorithms work but also their performance characteristics and when each might be preferred. By studying these implementations and their behavior on different types of data, you can gain a deeper understanding of sorting algorithms and make informed decisions about which to use in various scenarios.

Bubble Sort​

How It Works​

Implementation​

Optimization​

Characteristics​

When to Use​

Selection Sort​

How It Works​

Implementation​

Characteristics​

When to Use​

Insertion Sort​

How It Works​

Implementation​

Binary Insertion Sort​

Characteristics​

When to Use​

Comparison of Basic Sorting Algorithms​

Performance Characteristics​

Visualizing Basic Sorting Algorithms​

Bubble Sort Visualization​

Selection Sort Visualization​

Insertion Sort Visualization​

Practical Considerations​

Implementation in C#​

Built-in Sorting in .NET​

Comprehensive Example: Basic Sorting Algorithms in Practice​

Step-by-Step Explanation​

Key Concepts Demonstrated​

Performance Analysis​

When to Use Each Algorithm​

Conclusion​

Bubble Sort

How It Works

Implementation

Optimization

Characteristics

When to Use

Selection Sort

How It Works

Implementation

Characteristics

When to Use

Insertion Sort

How It Works

Implementation

Binary Insertion Sort

Characteristics

When to Use

Comparison of Basic Sorting Algorithms

Performance Characteristics

Visualizing Basic Sorting Algorithms

Bubble Sort Visualization

Selection Sort Visualization

Insertion Sort Visualization

Practical Considerations

Implementation in C#

Built-in Sorting in .NET

Comprehensive Example: Basic Sorting Algorithms in Practice

Step-by-Step Explanation

Key Concepts Demonstrated

Performance Analysis

When to Use Each Algorithm

Conclusion