Сортування підрахунком

Сортування підрахунком (Counting sort) – алгоритм сортування, який застосовується при невеликій кількості різних значень елементів масиву даних.

Час роботи алгоритму, лінійно залежить від загальної кількості елементів масиву і від кількості різних елементів.

Принцип роботи алгоритму сортування підрахунком

Ідея алгоритму полягає в наступному:

  • рахуємо кількість входжень кожного елемента масиву;
  • виходячи з даних отриманих на першому кроці, формуємо відсортований масив.

Реалізація алгоритму сортування підрахунком

Розглянемо просту реалізацію алгоритму, для масиву який може містити значення від 0 до k:

using System;

class Program
{
    //простий варіант сортування підрахунком
    static int[] BasicCountingSort(int[] array, int k)
    {
        var count = new int[k + 1];
        for (var i = 0; i < array.Length; i++)
        {
            count[array[i]]++;
        }

        var index = 0;
        for (var i = 0; i < count.Length; i++)
        {
            for (var j = 0; j < count[i]; j++)
            {
                array[index] = i;
                index++;
            }
        }

        return array;
    }

    //метод для отримання масиву заповненого випадковими числами
    static int[] GetRandomArray(int arraySize, int minValue, int maxValue)
    {
        var random = new Random();
        var randomArray = new int[arraySize];
        for (var i = 0; i < randomArray.Length; i++)
        {
            randomArray[i] = random.Next(minValue, maxValue);
        }

        return randomArray;
    }

    static void Main(string[] args)
    {
        var arr = GetRandomArray(10, 0, 9);
        Console.WriteLine("Вхідні дані: {0}", string.Join(", ", arr));
        Console.WriteLine("Впорядкований масив: {0}", string.Join(", ", BasicCountingSort(arr, 9)));
        Console.ReadLine();
    }
}

Узагальнення на довільний цілочисельний діапазон

Якщо діапазон можливих значень елементів масиву даних заздалегідь не відомий, проводимо пошук мінімального і максимального значення.

Оскільки індекс масиву не може бути негативним, то приводимо мінімальне значення діапазону до нуля, при цьому будемо враховувати поправку на всіх наступних кроках. Це також дозволить економити пам’ять на масивах даних, в яких мінімальне значення більше нуля.

//узагальнений варіант сортування підрахунком
static int[] CountingSort(int[] array)
{
    //пошук мінімального та максимального значень
    var min = array[0];
    var max = array[0];
    foreach (int element in array)
    {
        if (element > max)
        {
            max = element;
        }
        else if (element < min)
        {
            min = element;
        }
    }

    //поправка
    var correctionFactor = min != 0 ? -min : 0;
    max += correctionFactor;

    var count = new int[max + 1];
    for (var i = 0; i < array.Length; i++)
    {
        count[array[i] + correctionFactor]++;
    }

    var index = 0;
    for (var i = 0; i < count.Length; i++)
    {
        for (var j = 0; j < count[i]; j++)
        {
            array[index] = i - correctionFactor;
            index++;
        }
    }

    return array;
}

Дивіться також: