Принцип сортировки

Есть массив цифр, в первом проходе для каждого значения считаем индекс по значению, пишем во временный массив с учетом индекса по значению, во второй проход собираем из временного массива по порядку отсортированный массив.

Пошаговая реализация на Python:

def counting_sort(arr):
    if not arr:
        return []
    
    # Находим минимальное и максимальное значения
    min_val = min(arr)
    max_val = max(arr)
    
    # Создаём массив для подсчёта частот
    # Длина = max - min + 1, чтобы покрыть все возможные значения
    count_range = max_val - min_val + 1
    count = [0] * count_range
    
    # ПЕРВЫЙ ПРОХОД: подсчитываем частоту каждого элемента
    for num in arr:
        index = num - min_val  # нормализуем индекс
        count[index] += 1
    
    # Преобразуем count в массив префиксных сумм
    # Теперь count[i] будет содержать индекс, по которому
    # элемент со значением i+min_val должен быть записан
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # ВТОРОЙ ПРОХОД: создаём отсортированный массив
    result = [0] * len(arr)
    
    # Проходим исходный массив справа налево для стабильности
    for num in reversed(arr):
        index = num - min_val  # нормализуем индекс
        # Уменьшаем индекс на 1, так как индексация с 0
        position = count[index] - 1
        result[position] = num
        count[index] -= 1
    
    return result

# Пример использования
arr = [4, 2, 2, 8, 3, 3, 1, -1, 5]
sorted_arr = counting_sort(arr)
print("Исходный массив:", arr)
print("Отсортированный массив:", sorted_arr)

# Более простая версия (если значения неотрицательные и небольшие)
def simple_counting_sort(arr):
    if not arr:
        return []
    
    max_val = max(arr)
    count = [0] * (max_val + 1)
    
    # Подсчёт
    for num in arr:
        count[num] += 1
    
    # Сборка результата
    result = []
    for value, freq in enumerate(count):
        result.extend([value] * freq)
    
    return result

# Пример для простой версии
arr2 = [4, 2, 2, 8, 3, 3, 1, 0, 5]
sorted_arr2 = simple_counting_sort(arr2)
print("\nПростая версия:")
print("Исходный массив:", arr2)
print("Отсортированный массив:", sorted_arr2)

Объяснение работы алгоритма:

1. Определение диапазона: Находим минимальное и максимальное значения в массиве
2. Первый проход:
   • Создаём массив count размером max_val - min_val + 1
   • Для каждого элемента массива вычисляем его нормализованный индекс и увеличиваем счётчик
3. Преобразование count в префиксные суммы:
   • Каждый элемент count[i] теперь содержит количество элементов ≤ i+min_val
4. Второй проход:
   • Идём по исходному массиву справа налево (для сохранения стабильности)
   • Для каждого элемента находим его окончательную позицию в результате
   • Записываем элемент в результат и уменьшаем соответствующий счётчик

Особенности алгоритма:

• Временная сложность: O(n + k), где k = max_val - min_val
• Пространственная сложность: O(n + k)
• Стабильная сортировка (сохраняет порядок равных элементов)
• Работает только с целыми числами или объектами, которые можно привести к целым числам

Если значения в массиве всегда в разумном диапазоне (например, 0-100), этот алгоритм очень эффективен.

Варианты алгоритма для сортировки строк

1. Сортировка строк по первой букве (простая версия)

def counting_sort_strings_simple(arr):
    """Сортировка строк по первой букве"""
    if not arr:
        return []
    
    # Находим минимальный и максимальный код первой буквы
    min_code = ord(min(arr, key=lambda x: x[0])[0]) if arr else 0
    max_code = ord(max(arr, key=lambda x: x[0])[0]) if arr else 0
    
    # Создаём массив для подсчёта
    count_range = max_code - min_code + 1
    count = [0] * count_range
    
    # Подсчитываем частоту
    for s in arr:
        if s:  # Проверяем, что строка не пустая
            index = ord(s[0]) - min_code
            count[index] += 1
    
    # Преобразуем в префиксные суммы
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Создаём результат
    result = [None] * len(arr)
    
    # Заполняем результат (справа налево для стабильности)
    for s in reversed(arr):
        if s:
            index = ord(s[0]) - min_code
            position = count[index] - 1
            result[position] = s
            count[index] -= 1
    
    return result

2. Продвинутая версия - сортировка по разрядам (Radix Sort для строк)

def counting_sort_strings_by_char(arr, char_index):
    """Вспомогательная функция для сортировки по конкретному символу"""
    if not arr:
        return []
    
    # Создаём 256 элементов для всех возможных символов ASCII
    # Можно увеличить до 65536 для поддержки Unicode
    COUNT_SIZE = 256
    count = [0] * COUNT_SIZE
    
    # Подсчитываем частоту символов на позиции char_index
    for s in arr:
        if char_index < len(s):
            char_code = ord(s[char_index])
        else:
            char_code = 0  # Для строк короче, чем char_index
        count[char_code] += 1
    
    # Преобразуем в префиксные суммы
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Создаём результат
    result = [None] * len(arr)
    
    # Заполняем результат (справа налево для стабильности)
    for s in reversed(arr):
        if char_index < len(s):
            char_code = ord(s[char_index])
        else:
            char_code = 0
            
        position = count[char_code] - 1
        result[position] = s
        count[char_code] -= 1
    
    return result

def radix_sort_strings(arr):
    """Radix Sort для строк (сортировка по разрядам справа налево)"""
    if not arr:
        return []
    
    # Находим максимальную длину строки
    max_len = max(len(s) for s in arr)
    
    # Сортируем по каждому символу, начиная с последнего
    result = arr[:]
    for char_index in range(max_len - 1, -1, -1):
        result = counting_sort_strings_by_char(result, char_index)
    
    return result

3. Полная сортировка строк с учётом всех символов

def counting_sort_strings_full(arr):
    """Полная сортировка строк с использованием кортежей"""
    if not arr:
        return []
    
    # Преобразуем строки в последовательности кодов
    coded_strings = [tuple(ord(c) for c in s) for s in arr]
    
    # Находим минимальный и максимальный коды
    all_codes = [code for codes in coded_strings for code in codes]
    if not all_codes:
        return arr  # Все строки пустые
    
    min_code = min(all_codes)
    max_code = max(all_codes)
    
    # Создаём массив для подсчёта
    count_range = max_code - min_code + 1
    count = [0] * count_range
    
    # Подсчитываем частоту каждого кода
    for codes in coded_strings:
        for code in codes:
            count[code - min_code] += 1
    
    # Преобразуем в префиксные суммы
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Создаём временный массив
    temp = [None] * len(arr)
    
    # Заполняем временный массив
    for i in range(len(arr) - 1, -1, -1):
        codes = coded_strings[i]
        # Суммируем позиции всех кодов строки
        total_position = sum(count[code - min_code] - 1 for code in codes) // len(codes) if codes else 0
        temp[total_position] = arr[i]
        
        # Уменьшаем счётчики
        for code in codes:
            count[code - min_code] -= 1
    
    return temp

4. Оптимизированная версия с использованием словаря

def counting_sort_strings_dict(arr):
    """Сортировка строк с использованием словаря для частот"""
    if not arr:
        return []
    
    # Создаём словарь для частот
    freq = {}
    
    # Подсчитываем частоту каждой строки
    for s in arr:
        freq[s] = freq.get(s, 0) + 1
    
    # Получаем уникальные строки и сортируем их
    unique_strings = sorted(freq.keys())
    
    # Собираем результат
    result = []
    for s in unique_strings:
        result.extend([s] * freq[s])
    
    return result

def bucket_sort_strings(arr):
    """Bucket sort для строк по первой букве"""
    if not arr:
        return []
    
    # Создаём 26 корзин для букв (или больше для всех символов)
    buckets = [[] for _ in range(26)]
    
    # Распределяем строки по корзинам
    for s in arr:
        if s:  # Если строка не пустая
            first_char = s[0].lower()  # Приводим к нижнему регистру
            if 'a' <= first_char <= 'z':
                index = ord(first_char) - ord('a')
                buckets[index].append(s)
    
    # Сортируем каждую корзину и объединяем
    result = []
    for bucket in buckets:
        if bucket:
            # Сортируем строки в корзине
            bucket.sort()
            result.extend(bucket)
    
    return result

Пример использования:

# Тестируем разные реализации
strings = ["apple", "banana", "apricot", "cherry", "blueberry", "avocado", "березка", "яблоко"]

print("Исходный массив:", strings)
print("\n1. Сортировка по первой букве:")
print(counting_sort_strings_simple(strings))

print("\n2. Radix sort для строк:")
print(radix_sort_strings(strings))

print("\n3. Сортировка через словарь:")
print(counting_sort_strings_dict(strings))

print("\n4. Bucket sort:")
print(bucket_sort_strings(strings))

# Встроенная сортировка для сравнения
print("\nВстроенная сортировка Python:")
print(sorted(strings))

Рекомендации:

1. Для простых случаев (латинские буквы) используйте первую или вторую версию
2. Для полной сортировки строк лучше использовать Radix Sort (вторая версия)
3. Если строк много и они повторяются - используйте версию со словарем
4. Для Unicode строк увеличьте размер массива count до 65536

Важные моменты:

• Строки сортируются лексикографически (по кодам символов)
• Регистр имеет значение ('A' < 'a' в ASCII)
• Для сортировки без учета регистра нужно нормализовать строки
• Для не-ASCII символов учитывайте кодировку

Выбор реализации зависит от конкретных требований к производительности и обрабатываемых данных.