Sorting Algorithms

Sorting is one of the most studied problems in CS. Understanding basic sorting algorithms builds intuition for algorithmic thinking.

Complexity Comparison

Bubble Sort

Repeatedly swap adjacent elements that are out of order:

public static void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
                swapped = true;
            }
        }
        if (!swapped) break; // already sorted
    }
}

Selection Sort

Find the minimum element and place it at the front:

public static void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        (arr[i], arr[minIdx]) = (arr[minIdx], arr[i]);
    }
}

In Production, Use Built-ins

For real code, use the optimized built-in sorting:

int[] data = { 5, 2, 8, 1, 9 };

Array.Sort(data); // in-place, IntroSort (hybrid)

// LINQ (returns new sequence)
var sorted = data.OrderBy(x => x).ToArray();
var desc = data.OrderByDescending(x => x).ToArray();