10.4 - Basic Sorting Algorithms

Sorting is a fundamental operation in game development. Whether you're organizing a player's inventory by item value, arranging enemies by distance, or sorting leaderboard entries by score, efficient sorting algorithms are essential for creating well-organized and responsive games.

Introduction to Sorting

A sorting algorithm is a method for rearranging elements in a collection according to a specific order (usually ascending or descending). The efficiency of a sorting algorithm is typically measured by:

1. Time complexity: How long it takes to sort the collection
2. Space complexity: How much additional memory is required during sorting
3. Stability: Whether elements with equal values maintain their relative order

Let's explore some fundamental sorting algorithms and their applications in game development.

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.

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;
        
        // Last i elements are already in place
        for (int j = 0; j < n - i - 1; j++)
        {
            // Compare adjacent elements
            if (array[j].CompareTo(array[j + 1]) > 0)
            {
                // Swap if they're in the wrong order
                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;
        }
    }
}

Characteristics

• Time Complexity: O(n²) in worst and average cases, O(n) in best case (already sorted)
• Space Complexity: O(1) - uses a constant amount of extra space
• Stability: Stable - equal elements maintain their relative order
• Advantages: Simple to implement, works well for very small datasets
• Disadvantages: Very inefficient for large datasets

Tracing Bubble Sort

Let's trace through a bubble sort example:

Array: [5, 1, 4, 2, 8]

Pass 1:
Compare 5 > 1? Yes, swap: [1, 5, 4, 2, 8]
Compare 5 > 4? Yes, swap: [1, 4, 5, 2, 8]
Compare 5 > 2? Yes, swap: [1, 4, 2, 5, 8]
Compare 5 > 8? No, no swap: [1, 4, 2, 5, 8]

Pass 2:
Compare 1 > 4? No, no swap: [1, 4, 2, 5, 8]
Compare 4 > 2? Yes, swap: [1, 2, 4, 5, 8]
Compare 4 > 5? No, no swap: [1, 2, 4, 5, 8]
Compare 5 > 8? No, no swap: [1, 2, 4, 5, 8]

Pass 3:
Compare 1 > 2? No, no swap: [1, 2, 4, 5, 8]
Compare 2 > 4? No, no swap: [1, 2, 4, 5, 8]
Compare 4 > 5? No, no swap: [1, 2, 4, 5, 8]
Compare 5 > 8? No, no swap: [1, 2, 4, 5, 8]

No swaps in Pass 3, so the array is sorted: [1, 2, 4, 5, 8]

Selection Sort

Selection Sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

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 portion
        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 element at position i
        if (minIndex != i)
        {
            T temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

Characteristics

• Time Complexity: O(n²) in all cases
• Space Complexity: O(1) - uses a constant amount of extra space
• Stability: Not stable - equal elements may change their relative order
• Advantages: Simple implementation, performs well on small arrays, minimizes the number of swaps
• Disadvantages: Inefficient for large datasets

Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It's much like sorting playing cards in your hand.

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 greater than key one position ahead
        while (j >= 0 && array[j].CompareTo(key) > 0)
        {
            array[j + 1] = array[j];
            j--;
        }
        
        // Place key in its correct position
        array[j + 1] = key;
    }
}

Characteristics

• Time Complexity: O(n²) in worst and average cases, O(n) in best case (already sorted)
• Space Complexity: O(1) - uses a constant amount of extra space
• Stability: Stable - equal elements maintain their relative order
• Advantages: Simple implementation, efficient for small datasets, works well on nearly sorted data
• Disadvantages: Inefficient for large datasets

Game Development Example: Inventory Sorting

public class InventoryItem : IComparable<InventoryItem>
{
    public string Name { get; }
    public ItemRarity Rarity { get; }
    public int Value { get; }
    public int Quantity { get; set; }
    
    public InventoryItem(string name, ItemRarity rarity, int value, int quantity)
    {
        Name = name;
        Rarity = rarity;
        Value = value;
        Quantity = quantity;
    }
    
    // Default comparison by rarity (highest to lowest)
    public int CompareTo(InventoryItem other)
    {
        // Note: Reversed comparison for descending order
        return other.Rarity.CompareTo(Rarity);
    }
}

public enum ItemRarity
{
    Common = 0,
    Uncommon = 1,
    Rare = 2,
    Epic = 3,
    Legendary = 4
}

public enum InventorySortType
{
    ByRarity,
    ByValue,
    ByName,
    ByQuantity
}

public class Inventory
{
    private List<InventoryItem> items = new List<InventoryItem>();
    
    public void AddItem(InventoryItem item)
    {
        items.Add(item);
    }
    
    public void SortInventory(InventorySortType sortType)
    {
        // For small inventories, insertion sort is efficient
        InsertionSort(sortType);
    }
    
    private void InsertionSort(InventorySortType sortType)
    {
        for (int i = 1; i < items.Count; i++)
        {
            InventoryItem key = items[i];
            int j = i - 1;
            
            // Move elements greater than key one position ahead
            while (j >= 0 && CompareItems(items[j], key, sortType) > 0)
            {
                items[j + 1] = items[j];
                j--;
            }
            
            // Place key in its correct position
            items[j + 1] = key;
        }
    }
    
    private int CompareItems(InventoryItem a, InventoryItem b, InventorySortType sortType)
    {
        switch (sortType)
        {
            case InventorySortType.ByRarity:
                // Sort by rarity (highest to lowest)
                return b.Rarity.CompareTo(a.Rarity);
                
            case InventorySortType.ByValue:
                // Sort by value (highest to lowest)
                return b.Value.CompareTo(a.Value);
                
            case InventorySortType.ByName:
                // Sort by name (alphabetically)
                return a.Name.CompareTo(b.Name);
                
            case InventorySortType.ByQuantity:
                // Sort by quantity (highest to lowest)
                return b.Quantity.CompareTo(a.Quantity);
                
            default:
                return 0;
        }
    }
    
    public void DisplayInventory()
    {
        Console.WriteLine("Inventory Contents:");
        foreach (InventoryItem item in items)
        {
            Console.WriteLine($"{item.Name} (Rarity: {item.Rarity}, Value: {item.Value}, Quantity: {item.Quantity})");
        }
    }
}

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.

Implementation

public static void MergeSort<T>(T[] array) where T : IComparable<T>
{
    // If the array has 0 or 1 elements, it's already sorted
    if (array.Length <= 1)
    {
        return;
    }
    
    // Create a temporary array for merging
    T[] temp = new T[array.Length];
    
    // Call the recursive helper function
    MergeSortRecursive(array, temp, 0, array.Length - 1);
}

private static void MergeSortRecursive<T>(T[] array, T[] temp, int left, int right) where T : IComparable<T>
{
    if (left < right)
    {
        // Find the middle point
        int mid = left + (right - left) / 2;
        
        // Sort first and second halves
        MergeSortRecursive(array, temp, left, mid);
        MergeSortRecursive(array, temp, mid + 1, right);
        
        // Merge the sorted halves
        Merge(array, temp, left, mid, right);
    }
}

private static void Merge<T>(T[] array, T[] temp, int left, int mid, int right) where T : IComparable<T>
{
    // Copy data to temp arrays
    for (int i = left; i <= right; i++)
    {
        temp[i] = array[i];
    }
    
    int i1 = left;     // Initial index of first subarray
    int i2 = mid + 1;  // Initial index of second subarray
    int current = left; // Initial index of merged subarray
    
    // Merge the temp arrays back into array[left..right]
    while (i1 <= mid && i2 <= right)
    {
        if (temp[i1].CompareTo(temp[i2]) <= 0)
        {
            array[current] = temp[i1];
            i1++;
        }
        else
        {
            array[current] = temp[i2];
            i2++;
        }
        current++;
    }
    
    // Copy the remaining elements of left subarray, if any
    while (i1 <= mid)
    {
        array[current] = temp[i1];
        i1++;
        current++;
    }
    
    // Note: We don't need to copy the remaining elements of right subarray
    // because they are already in the correct position
}

Characteristics

• Time Complexity: O(n log n) in all cases
• Space Complexity: O(n) - requires additional space for the temporary array
• Stability: Stable - equal elements maintain their relative order
• Advantages: Efficient for large datasets, predictable performance
• Disadvantages: Requires additional memory

Quick Sort

Quick Sort is another divide-and-conquer algorithm that works by selecting a 'pivot' element and partitioning the array around the pivot.

Implementation

public static void QuickSort<T>(T[] array) where T : IComparable<T>
{
    QuickSortRecursive(array, 0, array.Length - 1);
}

private static void QuickSortRecursive<T>(T[] array, int low, int high) where T : IComparable<T>
{
    if (low < high)
    {
        // Partition the array and get the pivot index
        int pivotIndex = Partition(array, low, high);
        
        // Recursively sort elements before and after the pivot
        QuickSortRecursive(array, low, pivotIndex - 1);
        QuickSortRecursive(array, pivotIndex + 1, high);
    }
}

private static int Partition<T>(T[] array, int low, int high) where T : IComparable<T>
{
    // Choose the rightmost element as pivot
    T pivot = array[high];
    
    // Index of smaller element
    int i = low - 1;
    
    for (int j = low; j < high; j++)
    {
        // If current element is smaller than or equal to pivot
        if (array[j].CompareTo(pivot) <= 0)
        {
            i++;
            
            // Swap array[i] and array[j]
            T temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    
    // Swap array[i+1] and array[high] (put the pivot in its correct position)
    T temp2 = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp2;
    
    return i + 1;
}

Characteristics

• Time Complexity: O(n log n) on average, O(n²) in worst case
• Space Complexity: O(log n) for the recursive call stack
• Stability: Not stable - equal elements may change their relative order
• Advantages: Often faster in practice than other O(n log n) algorithms, in-place sorting
• Disadvantages: Worst-case performance is poor, not stable

Game Development Example: Enemy Distance Sorting

public class Enemy
{
    public string Name { get; }
    public Vector2 Position { get; }
    
    public Enemy(string name, Vector2 position)
    {
        Name = name;
        Position = position;
    }
}

public class EnemyManager
{
    private List<Enemy> enemies = new List<Enemy>();
    private Vector2 playerPosition;
    
    public EnemyManager(Vector2 playerPosition)
    {
        this.playerPosition = playerPosition;
    }
    
    public void AddEnemy(Enemy enemy)
    {
        enemies.Add(enemy);
    }
    
    public void UpdatePlayerPosition(Vector2 newPosition)
    {
        playerPosition = newPosition;
    }
    
    // Get enemies sorted by distance from player (closest first)
    public List<Enemy> GetEnemiesByDistance()
    {
        // Create a list of enemies with their distances
        List<EnemyDistance> enemyDistances = new List<EnemyDistance>();
        
        foreach (Enemy enemy in enemies)
        {
            float distance = Vector2.Distance(playerPosition, enemy.Position);
            enemyDistances.Add(new EnemyDistance(enemy, distance));
        }
        
        // Sort using QuickSort (efficient for this use case)
        QuickSort(enemyDistances, 0, enemyDistances.Count - 1);
        
        // Extract just the enemies in sorted order
        List<Enemy> sortedEnemies = new List<Enemy>();
        foreach (EnemyDistance ed in enemyDistances)
        {
            sortedEnemies.Add(ed.Enemy);
        }
        
        return sortedEnemies;
    }
    
    // Get the nearest n enemies to the player
    public List<Enemy> GetNearestEnemies(int count)
    {
        List<Enemy> sortedEnemies = GetEnemiesByDistance();
        return sortedEnemies.Take(Math.Min(count, sortedEnemies.Count)).ToList();
    }
    
    private void QuickSort(List<EnemyDistance> list, int low, int high)
    {
        if (low < high)
        {
            int pivotIndex = Partition(list, low, high);
            QuickSort(list, low, pivotIndex - 1);
            QuickSort(list, pivotIndex + 1, high);
        }
    }
    
    private int Partition(List<EnemyDistance> list, int low, int high)
    {
        EnemyDistance pivot = list[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++)
        {
            if (list[j].Distance <= pivot.Distance)
            {
                i++;
                
                // Swap
                EnemyDistance temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
        
        // Swap pivot to its final position
        EnemyDistance temp2 = list[i + 1];
        list[i + 1] = list[high];
        list[high] = temp2;
        
        return i + 1;
    }
    
    // Helper class to associate enemies with their distances
    private class EnemyDistance
    {
        public Enemy Enemy { get; }
        public float Distance { get; }
        
        public EnemyDistance(Enemy enemy, float distance)
        {
            Enemy = enemy;
            Distance = distance;
        }
    }
}

// Simple Vector2 struct for this example
public struct Vector2
{
    public float X { get; }
    public float Y { get; }
    
    public Vector2(float x, float y)
    {
        X = x;
        Y = y;
    }
    
    public static float Distance(Vector2 a, Vector2 b)
    {
        float dx = a.X - b.X;
        float dy = a.Y - b.Y;
        return (float)Math.Sqrt(dx * dx + dy * dy);
    }
}

Comparison of Sorting Algorithms

Here's a comparison of the sorting algorithms we've covered:

Algorithm	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity	Stable	Best For
Bubble Sort	O(n²)	O(n²)	O(1)	Yes	Very small datasets, educational purposes
Selection Sort	O(n²)	O(n²)	O(1)	No	Small datasets, minimizing swaps
Insertion Sort	O(n²)	O(n²)	O(1)	Yes	Small datasets, nearly sorted data
Merge Sort	O(n log n)	O(n log n)	O(n)	Yes	Large datasets, stable sorting needed
Quick Sort	O(n log n)	O(n²)	O(log n)	No	Large datasets, general-purpose sorting

Built-in Sorting in C#

For most practical applications, you should use C#'s built-in sorting methods, which are highly optimized:

// Sorting arrays
int[] numbers = { 5, 2, 8, 1, 9 };
Array.Sort(numbers);

// Sorting lists
List<int> numberList = new List<int> { 5, 2, 8, 1, 9 };
numberList.Sort();

// Sorting with custom comparison
List<InventoryItem> inventory = GetInventory();
inventory.Sort((a, b) => b.Value.CompareTo(a.Value)); // Sort by value (highest first)

// Using LINQ for sorting
var sortedItems = inventory.OrderByDescending(item => item.Rarity)
                          .ThenByDescending(item => item.Value);

Unity Relevance

In Unity, sorting is commonly used for:

1. Rendering order: Sorting objects by distance for transparency
2. AI targeting: Sorting enemies or targets by priority
3. UI elements: Sorting inventory items, leaderboards, etc.
4. Gameplay mechanics: Sorting collectibles by value, quests by difficulty

Unity's System.Array.Sort() and LINQ methods use highly optimized implementations, so you should prefer these over custom sorting algorithms for most cases.

// Example: Sorting enemies by distance in Unity
void SortEnemiesByDistance()
{
    GameObject[] enemies = GameObject.FindGameObjectsWithTag("Enemy");
    
    // Sort enemies by distance to player
    System.Array.Sort(enemies, (a, b) => {
        float distA = Vector3.Distance(a.transform.position, transform.position);
        float distB = Vector3.Distance(b.transform.position, transform.position);
        return distA.CompareTo(distB);
    });
    
    // Now enemies[0] is the closest enemy
    if (enemies.Length > 0)
    {
        Debug.Log($"Closest enemy: {enemies[0].name}");
    }
}

When to Use Each Algorithm

Choose your sorting algorithm based on your specific needs:

• Bubble Sort: Only for educational purposes or extremely small datasets
• Selection Sort: When memory writes are expensive (but comparisons are not)
• Insertion Sort: For small datasets or nearly sorted data
• Merge Sort: When stability is required and extra memory is available
• Quick Sort: For general-purpose sorting of large datasets
• Built-in Sort: For most practical applications

Conclusion

Sorting algorithms are essential tools for organizing data in your games. By understanding the strengths and weaknesses of different sorting algorithms, you can choose the most appropriate one for your specific needs, whether you're sorting inventory items, ranking players on a leaderboard, or determining the order in which to process game entities.

In the next section, we'll explore Big O notation, which provides a formal way to analyze and compare the efficiency of algorithms.