--- title: "Counting Sort em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/counting-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/counting-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo Counting Sort implementado em Zig. Ordenação linear para inteiros com intervalo limitado, com código funcional e análise." date: "2026-02-21" author: "Zig Brasil" --- # Counting Sort em Zig — Implementação e Explicação Aprenda o algoritmo Counting Sort implementado em Zig. Ordenação linear para inteiros com intervalo limitado, com código funcional e análise. # Counting Sort em Zig — Implementação e Explicação O **Counting Sort** (ordenação por contagem) é um algoritmo de ordenação não-comparativo que funciona contando o número de ocorrências de cada valor distinto. É extremamente eficiente quando o intervalo de valores (k) é pequeno em relação ao número de elementos (n). ## Como Funciona 1. **Contar**: conte quantas vezes cada valor aparece no array original 2. **Acumular**: calcule as posições finais usando soma acumulada 3. **Posicionar**: coloque cada elemento em sua posição correta no array de saída ### Visualização do Processo ``` Array original: [4, 2, 2, 8, 3, 3, 1] Valores de 0 a 8 (k = 9) Passo 1 — Contagem: Índice: 0 1 2 3 4 5 6 7 8 Contagem: [0, 1, 2, 2, 1, 0, 0, 0, 1] ↑ ↑ ↑ ↑ ↑ ↑ 0× 1× 2× 2× 1× 1× Passo 2 — Soma acumulada: Contagem: [0, 1, 3, 5, 6, 6, 6, 6, 7] Posição do último elemento de cada valor Passo 3 — Posicionar (da direita para estabilidade): Original[6] = 1 → contagem[1]=1 → saída[0] = 1, contagem[1]=0 Original[5] = 3 → contagem[3]=5 → saída[4] = 3, contagem[3]=4 Original[4] = 3 → contagem[3]=4 → saída[3] = 3, contagem[3]=3 ... Resultado: [1, 2, 2, 3, 3, 4, 8] ✓ ``` ## Implementação em Zig ```zig const std = @import("std"); const Allocator = std.mem.Allocator; /// Counting Sort para inteiros não-negativos. /// k é o valor máximo + 1 no array. pub fn countingSort( allocator: Allocator, items: []u32, k: usize, ) !void { if (items.len <= 1) return; // Array de contagem const contagem = try allocator.alloc(usize, k); defer allocator.free(contagem); @memset(contagem, 0); // Array de saída const saida = try allocator.alloc(u32, items.len); defer allocator.free(saida); // Passo 1: contar ocorrências for (items) |valor| { contagem[valor] += 1; } // Passo 2: soma acumulada var i: usize = 1; while (i < k) : (i += 1) { contagem[i] += contagem[i - 1]; } // Passo 3: posicionar (percorrendo de trás para frente = estável) var j: usize = items.len; while (j > 0) { j -= 1; const valor = items[j]; contagem[valor] -= 1; saida[contagem[valor]] = valor; } // Copia de volta para o array original @memcpy(items, saida); } /// Counting Sort para inteiros com valores negativos. /// Ajusta o intervalo para trabalhar com índices positivos. pub fn countingSortComNegativos( allocator: Allocator, items: []i32, ) !void { if (items.len <= 1) return; // Encontra min e max var min_val: i32 = items[0]; var max_val: i32 = items[0]; for (items[1..]) |v| { if (v < min_val) min_val = v; if (v > max_val) max_val = v; } const intervalo: usize = @intCast(@as(i64, max_val) - @as(i64, min_val) + 1); const contagem = try allocator.alloc(usize, intervalo); defer allocator.free(contagem); @memset(contagem, 0); const saida = try allocator.alloc(i32, items.len); defer allocator.free(saida); // Conta ocorrências (ajustando pelo mínimo) for (items) |v| { const idx: usize = @intCast(@as(i64, v) - @as(i64, min_val)); contagem[idx] += 1; } // Soma acumulada var i: usize = 1; while (i < intervalo) : (i += 1) { contagem[i] += contagem[i - 1]; } // Posiciona (estável) var j: usize = items.len; while (j > 0) { j -= 1; const idx: usize = @intCast(@as(i64, items[j]) - @as(i64, min_val)); contagem[idx] -= 1; saida[contagem[idx]] = items[j]; } @memcpy(items, saida); } pub fn main() !void { const stdout = std.io.getStdOut().writer(); var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); // Exemplo com inteiros não-negativos var numeros = [_]u32{ 4, 2, 2, 8, 3, 3, 1 }; try stdout.print("Original: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); try countingSort(allocator, &numeros, 9); try stdout.print("Ordenado: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); // Exemplo com negativos var negativos = [_]i32{ -5, 3, -1, 0, 2, -3, 1 }; try countingSortComNegativos(allocator, &negativos); try stdout.print("Negativos: ", .{}); for (negativos) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Todos os casos** | O(n + k) | O(n + k) | Onde `n` é o número de elementos e `k` é o intervalo de valores. ### Quando é Eficiente? - **k = O(n)**: complexidade total é O(n) — **linear!** - **k >> n**: o algoritmo se torna ineficiente (ex: ordenar 10 números entre 0 e 1.000.000) ## Características - **Estável**: Sim — preserva a ordem de elementos com mesmo valor - **In-place**: Não — precisa de O(n + k) memória adicional - **Não-comparativo**: não compara elementos entre si - **Limitação**: funciona apenas com inteiros (ou valores mapeáveis a inteiros) ## Quando Usar - **Inteiros com intervalo limitado**: notas de 0 a 100, idades, caracteres ASCII - **Estabilidade necessária**: como sub-rotina do [Radix Sort](/algoritmos/radix-sort/) - **Desempenho linear**: quando k = O(n) ## Recursos Relacionados - [Radix Sort em Zig](/algoritmos/radix-sort/) — Usa Counting Sort como sub-rotina - [Bubble Sort em Zig](/algoritmos/bubble-sort/) — Algoritmo comparativo simples - [Quick Sort em Zig](/algoritmos/quick-sort/) — Algoritmo comparativo eficiente - [Hash Map](/estruturas-dados/hash-table/) — Estrutura que também conta ocorrências - [Array Dinâmico](/estruturas-dados/array-dinamico/) — Alocação dinâmica de arrays