Перейти к содержанию

11.9   Сортировка подсчетом

Сортировка подсчетом (counting sort) реализует сортировку за счет подсчета количества элементов и обычно используется для массивов целых чисел.

11.9.1   Простая реализация

Сначала рассмотрим простой пример. Дан массив nums длины \(n\) , элементы которого являются "неотрицательными целыми числами". Общий процесс сортировки подсчетом показан на рисунке 11-16.

  1. Пройти по массиву, найти в нем максимальное число, обозначить его как \(m\) , а затем создать вспомогательный массив counter длины \(m + 1\) .
  2. С помощью counter подсчитать, сколько раз каждое число встречается в nums; при этом counter[num] хранит число вхождений значения num . Делается это просто: достаточно пройти по nums (пусть текущее число равно num ) и на каждом шаге увеличить counter[num] на \(1\) .
  3. Поскольку индексы массива counter изначально упорядочены, можно считать, что все числа уже отсортированы. Далее остается пройти по counter и в соответствии с числом вхождений записать значения обратно в nums в порядке возрастания.

Процесс сортировки подсчетом

Рисунок 11-16   Процесс сортировки подсчетом

Код приведен ниже:

counting_sort.py
def counting_sort_naive(nums: list[int]):
    """Сортировка подсчетом"""
    # Простая реализация, не подходит для сортировки объектов
    # 1. Найти максимальный элемент массива m
    m = max(nums)
    # 2. Подсчитать число появлений каждой цифры
    # counter[num] обозначает число появлений num
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. Обойти counter и заполнить исходный массив nums элементами
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1
counting_sort.cpp
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
void countingSortNaive(vector<int> &nums) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.java
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
void countingSortNaive(int[] nums) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    for (int num : nums) {
        m = Math.max(m, num);
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    int[] counter = new int[m + 1];
    for (int num : nums) {
        counter[num]++;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.cs
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
void CountingSortNaive(int[] nums) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    foreach (int num in nums) {
        m = Math.Max(m, num);
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    int[] counter = new int[m + 1];
    foreach (int num in nums) {
        counter[num]++;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.go
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
func countingSortNaive(nums []int) {
    // 1. Найти максимальный элемент массива m
    m := 0
    for _, num := range nums {
        if num > m {
            m = num
        }
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    counter := make([]int, m+1)
    for _, num := range nums {
        counter[num]++
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    for i, num := 0, 0; num < m+1; num++ {
        for j := 0; j < counter[num]; j++ {
            nums[i] = num
            i++
        }
    }
}
counting_sort.swift
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
func countingSortNaive(nums: inout [Int]) {
    // 1. Найти максимальный элемент массива m
    let m = nums.max()!
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    var counter = Array(repeating: 0, count: m + 1)
    for num in nums {
        counter[num] += 1
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    var i = 0
    for num in 0 ..< m + 1 {
        for _ in 0 ..< counter[num] {
            nums[i] = num
            i += 1
        }
    }
}
counting_sort.js
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
function countingSortNaive(nums) {
    // 1. Найти максимальный элемент массива m
    let m = Math.max(...nums);
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    const counter = new Array(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.ts
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
function countingSortNaive(nums: number[]): void {
    // 1. Найти максимальный элемент массива m
    let m: number = Math.max(...nums);
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}
counting_sort.dart
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
void countingSortNaive(List<int> nums) {
  // 1. Найти максимальный элемент массива m
  int m = 0;
  for (int _num in nums) {
    m = max(m, _num);
  }
  // 2. Подсчитать число появлений каждой цифры
  // counter[_num] обозначает число появлений _num
  List<int> counter = List.filled(m + 1, 0);
  for (int _num in nums) {
    counter[_num]++;
  }
  // 3. Обойти counter и заполнить исходный массив nums элементами
  int i = 0;
  for (int _num = 0; _num < m + 1; _num++) {
    for (int j = 0; j < counter[_num]; j++, i++) {
      nums[i] = _num;
    }
  }
}
counting_sort.rs
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
fn counting_sort_naive(nums: &mut [i32]) {
    // 1. Найти максимальный элемент массива m
    let m = *nums.iter().max().unwrap();
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    let mut counter = vec![0; m as usize + 1];
    for &num in nums.iter() {
        counter[num as usize] += 1;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    let mut i = 0;
    for num in 0..m + 1 {
        for _ in 0..counter[num as usize] {
            nums[i] = num;
            i += 1;
        }
    }
}
counting_sort.c
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
void countingSortNaive(int nums[], int size) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    int *counter = calloc(m + 1, sizeof(int));
    for (int i = 0; i < size; i++) {
        counter[nums[i]]++;
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
    // 4. Освободить память
    free(counter);
}
counting_sort.kt
/* Сортировка подсчетом */
// Простая реализация, не подходит для сортировки объектов
fun countingSortNaive(nums: IntArray) {
    // 1. Найти максимальный элемент массива m
    var m = 0
    for (num in nums) {
        m = max(m, num)
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    val counter = IntArray(m + 1)
    for (num in nums) {
        counter[num]++
    }
    // 3. Обойти counter и заполнить исходный массив nums элементами
    var i = 0
    for (num in 0..<m + 1) {
        var j = 0
        while (j < counter[num]) {
            nums[i] = num
            j++
            i++
        }
    }
}
counting_sort.rb
### Сортировка подсчетом ###
def counting_sort_naive(nums)
  # Простая реализация, не подходит для сортировки объектов
  # 1. Найти максимальный элемент массива m
  m = 0
  nums.each { |num| m = [m, num].max }
  # 2. Подсчитать число появлений каждой цифры
  # counter[num] обозначает число появлений num
  counter = Array.new(m + 1, 0)
  nums.each { |num| counter[num] += 1 }
  # 3. Обойти counter и заполнить исходный массив nums элементами
  i = 0
  for num in 0...(m + 1)
    (0...counter[num]).each do
      nums[i] = num
      i += 1
    end
  end
end
Визуализация кода

Связь между сортировкой подсчетом и блочной сортировкой

Если посмотреть на сортировку подсчетом с точки зрения блочной сортировки, то каждый индекс массива counter можно рассматривать как отдельный блок, а процесс подсчета - как распределение элементов по соответствующим блокам. По сути, сортировка подсчетом является частным случаем блочной сортировки для целочисленных данных.

11.9.2   Полная реализация

Внимательный читатель мог заметить, что если входные данные представлены объектами, то описанный выше шаг 3. перестает работать. Например, если входными данными являются объекты товаров и мы хотим отсортировать их по цене (полю класса), то описанный алгоритм сможет выдать только отсортированный ряд цен, но не исходные объекты в нужном порядке.

Как же получить корректный порядок исходных данных? Сначала вычислим "префиксную сумму" массива counter . Как следует из названия, префиксная сумма в индексе i , обозначаемая как prefix[i] , равна сумме первых i элементов массива:

\[ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} \]

Префиксная сумма имеет четкий смысл: prefix[num] - 1 обозначает индекс последнего вхождения элемента num в результирующем массиве res. Это очень важная информация, потому что она указывает, в какую позицию результирующего массива должен попасть каждый элемент. Далее мы проходим исходный массив nums в обратном порядке и на каждой итерации для очередного элемента num выполняем два действия.

  1. Записать num в массив res по индексу prefix[num] - 1 .
  2. Уменьшить префиксную сумму prefix[num] на \(1\) , чтобы получить индекс следующего размещения элемента num .

После завершения прохода массив res будет содержать отсортированный результат; остается только переписать res обратно в nums . Полный процесс сортировки подсчетом показан на рисунке 11-17.

Шаги сортировки подсчетом

counting_sort_step2

counting_sort_step3

counting_sort_step4

counting_sort_step5

counting_sort_step6

counting_sort_step7

counting_sort_step8

Рисунок 11-17   Шаги сортировки подсчетом

Код реализации сортировки подсчетом приведен ниже:

counting_sort.py
def counting_sort(nums: list[int]):
    """Сортировка подсчетом"""
    # Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
    # 1. Найти максимальный элемент массива m
    m = max(nums)
    # 2. Подсчитать число появлений каждой цифры
    # counter[num] обозначает число появлений num
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    # То есть counter[num]-1 — это индекс последнего появления num в res
    for i in range(m):
        counter[i + 1] += counter[i]
    # 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    # Инициализировать массив res для хранения результата
    n = len(nums)
    res = [0] * n
    for i in range(n - 1, -1, -1):
        num = nums[i]
        res[counter[num] - 1] = num  # Поместить num по соответствующему индексу
        counter[num] -= 1  # Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    # Перезаписать исходный массив nums массивом результата res
    for i in range(n):
        nums[i] = res[i]
counting_sort.cpp
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
void countingSort(vector<int> &nums) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    int n = nums.size();
    vector<int> res(n);
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // Поместить num по соответствующему индексу
        counter[num]--;              // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    nums = res;
}
counting_sort.java
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
void countingSort(int[] nums) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    for (int num : nums) {
        m = Math.max(m, num);
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    int[] counter = new int[m + 1];
    for (int num : nums) {
        counter[num]++;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    int n = nums.length;
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // Поместить num по соответствующему индексу
        counter[num]--; // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    for (int i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.cs
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
void CountingSort(int[] nums) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    foreach (int num in nums) {
        m = Math.Max(m, num);
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    int[] counter = new int[m + 1];
    foreach (int num in nums) {
        counter[num]++;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    int n = nums.Length;
    int[] res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // Поместить num по соответствующему индексу
        counter[num]--; // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    for (int i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.go
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
func countingSort(nums []int) {
    // 1. Найти максимальный элемент массива m
    m := 0
    for _, num := range nums {
        if num > m {
            m = num
        }
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    counter := make([]int, m+1)
    for _, num := range nums {
        counter[num]++
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for i := 0; i < m; i++ {
        counter[i+1] += counter[i]
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    n := len(nums)
    res := make([]int, n)
    for i := n - 1; i >= 0; i-- {
        num := nums[i]
        // Поместить num по соответствующему индексу
        res[counter[num]-1] = num
        // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
        counter[num]--
    }
    // Перезаписать исходный массив nums массивом результата res
    copy(nums, res)
}
counting_sort.swift
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
func countingSort(nums: inout [Int]) {
    // 1. Найти максимальный элемент массива m
    let m = nums.max()!
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    var counter = Array(repeating: 0, count: m + 1)
    for num in nums {
        counter[num] += 1
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for i in 0 ..< m {
        counter[i + 1] += counter[i]
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    var res = Array(repeating: 0, count: nums.count)
    for i in nums.indices.reversed() {
        let num = nums[i]
        res[counter[num] - 1] = num // Поместить num по соответствующему индексу
        counter[num] -= 1 // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    for i in nums.indices {
        nums[i] = res[i]
    }
}
counting_sort.js
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
function countingSort(nums) {
    // 1. Найти максимальный элемент массива m
    let m = Math.max(...nums);
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    const counter = new Array(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (let i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    const n = nums.length;
    const res = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
        const num = nums[i];
        res[counter[num] - 1] = num; // Поместить num по соответствующему индексу
        counter[num]--; // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    for (let i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.ts
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
function countingSort(nums: number[]): void {
    // 1. Найти максимальный элемент массива m
    let m: number = Math.max(...nums);
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (let i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    const n = nums.length;
    const res: number[] = new Array<number>(n);
    for (let i = n - 1; i >= 0; i--) {
        const num = nums[i];
        res[counter[num] - 1] = num; // Поместить num по соответствующему индексу
        counter[num]--; // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    for (let i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}
counting_sort.dart
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
void countingSort(List<int> nums) {
  // 1. Найти максимальный элемент массива m
  int m = 0;
  for (int _num in nums) {
    m = max(m, _num);
  }
  // 2. Подсчитать число появлений каждой цифры
  // counter[_num] обозначает число появлений _num
  List<int> counter = List.filled(m + 1, 0);
  for (int _num in nums) {
    counter[_num]++;
  }
  // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
  // То есть counter[_num]-1 — это индекс последнего появления _num в res
  for (int i = 0; i < m; i++) {
    counter[i + 1] += counter[i];
  }
  // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
  // Инициализировать массив res для хранения результата
  int n = nums.length;
  List<int> res = List.filled(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    int _num = nums[i];
    res[counter[_num] - 1] = _num; // Поместить _num по соответствующему индексу
    counter[_num]--; // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения _num
  }
  // Перезаписать исходный массив nums массивом результата res
  nums.setAll(0, res);
}
counting_sort.rs
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
fn counting_sort(nums: &mut [i32]) {
    // 1. Найти максимальный элемент массива m
    let m = *nums.iter().max().unwrap() as usize;
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    let mut counter = vec![0; m + 1];
    for &num in nums.iter() {
        counter[num as usize] += 1;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for i in 0..m {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    let n = nums.len();
    let mut res = vec![0; n];
    for i in (0..n).rev() {
        let num = nums[i];
        res[counter[num as usize] - 1] = num; // Поместить num по соответствующему индексу
        counter[num as usize] -= 1; // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    nums.copy_from_slice(&res)
}
counting_sort.c
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
void countingSort(int nums[], int size) {
    // 1. Найти максимальный элемент массива m
    int m = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    int *counter = calloc(m, sizeof(int));
    for (int i = 0; i < size; i++) {
        counter[nums[i]]++;
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    int *res = malloc(sizeof(int) * size);
    for (int i = size - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // Поместить num по соответствующему индексу
        counter[num]--;              // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    memcpy(nums, res, size * sizeof(int));
    // 5. Освободить память
    free(res);
    free(counter);
}
counting_sort.kt
/* Сортировка подсчетом */
// Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
fun countingSort(nums: IntArray) {
    // 1. Найти максимальный элемент массива m
    var m = 0
    for (num in nums) {
        m = max(m, num)
    }
    // 2. Подсчитать число появлений каждой цифры
    // counter[num] обозначает число появлений num
    val counter = IntArray(m + 1)
    for (num in nums) {
        counter[num]++
    }
    // 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
    // То есть counter[num]-1 — это индекс последнего появления num в res
    for (i in 0..<m) {
        counter[i + 1] += counter[i]
    }
    // 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
    // Инициализировать массив res для хранения результата
    val n = nums.size
    val res = IntArray(n)
    for (i in n - 1 downTo 0) {
        val num = nums[i]
        res[counter[num] - 1] = num // Поместить num по соответствующему индексу
        counter[num]-- // Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
    }
    // Перезаписать исходный массив nums массивом результата res
    for (i in 0..<n) {
        nums[i] = res[i]
    }
}
counting_sort.rb
### Сортировка подсчетом ###
def counting_sort(nums)
  # Полная реализация, позволяет сортировать объекты и является стабильной сортировкой
  # 1. Найти максимальный элемент массива m
  m = nums.max
  # 2. Подсчитать число появлений каждой цифры
  # counter[num] обозначает число появлений num
  counter = Array.new(m + 1, 0)
  nums.each { |num| counter[num] += 1 }
  # 3. Вычислить префиксные суммы counter и преобразовать «число появлений» в «конечный индекс»
  # То есть counter[num]-1 — это индекс последнего появления num в res
  (0...m).each { |i| counter[i + 1] += counter[i] }
  # 4. Обойти nums в обратном порядке и поместить элементы в результирующий массив res
  # Инициализировать массив res для хранения результата
  n = nums.length
  res = Array.new(n, 0)
  (n - 1).downto(0).each do |i|
    num = nums[i]
    res[counter[num] - 1] = num # Поместить num по соответствующему индексу
    counter[num] -= 1 # Уменьшить префиксную сумму на 1, чтобы получить индекс следующего размещения num
  end
  # Перезаписать исходный массив nums массивом результата res
  (0...n).each { |i| nums[i] = res[i] }
end
Визуализация кода

11.9.3   Характеристики алгоритма

  • Временная сложность равна \(O(n + m)\), алгоритм не является адаптивным : необходимо пройти по nums и по counter , а оба этих прохода занимают линейное время. Обычно выполняется \(n \gg m\) , поэтому временная сложность стремится к \(O(n)\) .
  • Пространственная сложность равна \(O(n + m)\), сортировка не выполняется на месте: используются массивы res и counter длины \(n\) и \(m\) соответственно.
  • Стабильная сортировка: порядок заполнения res идет "справа налево", поэтому обратный проход по nums позволяет сохранить относительный порядок равных элементов и тем самым реализовать стабильную сортировку. Вообще говоря, прямой проход по nums тоже даст правильный результат сортировки, но он будет нестабильным.

11.9.4   Ограничения

На этом этапе сортировка подсчетом может показаться очень изящной: она позволяет эффективно сортировать данные, опираясь только на подсчет числа вхождений. Однако условия ее применения довольно строгие.

Сортировка подсчетом применима только к неотрицательным целым числам. Чтобы использовать ее для других типов данных, нужно убедиться, что эти данные можно преобразовать в неотрицательные целые числа и что при преобразовании относительный порядок элементов не изменится. Например, для массива целых чисел с отрицательными значениями можно сначала прибавить ко всем числам константу, превратив их в положительные, затем выполнить сортировку и после этого преобразовать значения обратно.

Сортировка подсчетом подходит для случаев, когда объем данных велик, но диапазон значений невелик. Например, в приведенном выше примере \(m\) не должно быть слишком большим, иначе будет занято слишком много памяти. А когда \(n \ll m\) , сортировка подсчетом использует \(O(m)\) времени и может оказаться медленнее, чем алгоритмы сортировки с \(O(n \log n)\) .

Оставляйте свои идеи, вопросы и предложения в комментариях