O que é o Shuffle War?
O Shuffle War é um jogo de estratégia desenvolvido em linguagem C que combina conhecimento sobre algoritmos de ordenação com mecânicas de jogo competitivas. O jogador assume o papel de um conselheiro real que deve escolher os melhores algoritmos para ordenar vetores, competindo contra um adversário controlado pelo computador.
O objetivo principal é sobreviver às demandas do rei, acumulando mais reputação que o oponente através de escolhas inteligentes de algoritmos. Cada decisão impacta diretamente na pontuação final e determina quem será executado pelo rei ao final das cinco rodadas.
Mecânicas Principais do Jogo
Sistema de Reputação
Cada jogador acumula pontos de reputação baseados nas escolhas de algoritmos e nas preferências do rei.
Cartas de Algoritmos
O jogador possui um conjunto de cartas representando diferentes algoritmos de ordenação com características únicas.
Preferências do Rei
A cada rodada, o rei pode preferir algoritmos estáveis ou algoritmos rápidos, influenciando a pontuação.
Sistema de Desconfiança
Jogadores podem mentir sobre suas escolhas, mas isso aumenta a desconfiança e afeta jogadas futuras.
Como Funciona o Jogo
Inicialização
Cada jogador recebe cartas de algoritmos e começa com reputação zero
Geração da Rodada
Um vetor aleatório é criado e uma dica sobre a preferência do rei é revelada
Escolha do Algoritmo
Jogador e NPC escolhem qual algoritmo usar para ordenar o vetor
Avaliação
Pontos são atribuídos baseados na adequação do algoritmo às preferências do rei
Resultado Final
Após 5 rodadas, quem tiver menor reputação é executado pelo rei
Sistema de Pontuação
A pontuação é calculada com base na adequação do algoritmo escolhido às preferências do rei:
- Preferência por Estabilidade: Algoritmos estáveis (Bubble Sort, Insertion Sort, Merge Sort, Counting Sort) recebem bônus de 10 pontos
- Preferência por Velocidade: Algoritmos rápidos (Quick Sort, Heap Sort, Shell Sort) recebem bônus de 10 pontos
- Pontuação Base: Todos os algoritmos recebem pontos base independente da preferência
Características Especiais
Sistema de Dicas e Mentiras
O jogo possui 5 tipos de dicas que são realmente analisadas no vetor:
- Vetor quase ordenado (menos de 10% desordenado)
- Vetor muito desordenado (mais de 50% desordenado)
- Quantidade de elementos repetidos
- Preferência por estabilidade
- Preferência por velocidade
Sistema de Penalizações
As cartas sofrem penalizações baseadas em sua posição:
- Posições 1-3: Sem penalização
- Posições 4-6: Penalização de 5000 pontos
- Posições 7-9: Penalização forte de 10000 pontos
Comportamento do NPC
O NPC possui um sistema de decisão que:
- Tem 30% de chance de mentir quando desconfiado
- Tem 10% de chance base de mentir
- Nunca mente duas vezes seguidas
- Mantém registro de desconfiança
Tamanho dos Vetores
Cada rodada gera vetores aleatórios entre 3000 e 10000 elementos, testando realmente a eficiência dos algoritmos em grandes conjuntos de dados.
Algoritmos Disponíveis
O jogo inclui oito algoritmos de ordenação clássicos, cada um com características específicas:
Bubble Sort
Algoritmo simples e estável, ideal para vetores pequenos ou quase ordenados. Fácil de implementar mas lento para grandes volumes de dados.
Selection Sort
Realiza poucas trocas mas é instável. Útil quando o custo de escrita é alto, mas geralmente não é a melhor opção.
Insertion Sort
Estável e muito eficiente para vetores pequenos ou quase ordenados. Complexidade varia entre O(n) no melhor caso e O(n²) no pior.
Merge Sort
Sempre estável com complexidade garantida O(n log n), mas consome memória extra por não ser in-place.
Quick Sort
Muito rápido na prática com complexidade média O(n log n), mas instável e pode degradar para O(n²) no pior caso.
Heap Sort
Sempre O(n log n) e in-place, mas instável e geralmente mais lento que Quick Sort na prática.
Shell Sort
Melhoria do Insertion Sort, in-place mas instável. Performance depende da sequência de gaps escolhida.
Counting Sort
Algoritmo não comparativo, estável e muito eficiente quando os valores são pequenos e inteiros.
Visualização dos Algoritmos
Demonstração visual do funcionamento de cada algoritmo:
Bubble Sort
- Complexidade média: O(n²)
- Pior caso: O(n²)
Counting Sort
- Complexidade média: O(n + k)
- Pior caso: O(n + k)
- n = tamanho do vetor, k = valor máximo do elemento
Insertion Sort
- Complexidade média: O(n²)
- Pior caso: O(n²)
- Melhor caso (quase ordenado): O(n)
Merge Sort
- Complexidade média: O(n log n)
- Pior caso: O(n log n)
Quick Sort
- Complexidade média: O(n log n)
- Pior caso: O(n²)
Selection Sort
- Complexidade média: O(n²)
- Pior caso: O(n²)
Shell Sort
- Complexidade média: depende da sequência de gaps, geralmente O(n^(3/2))
- Pior caso: O(n²)
Estrutura do Código
O projeto está organizado em módulos bem definidos para facilitar manutenção e compreensão:
Arquivos Principais
main.c
Arquivo principal que controla o fluxo do jogo e a interação com o usuário.
jogo.h / jogo.c
Contém as estruturas de dados e funções principais do jogo, como jogadores e rodadas.
algoritmos/
Pasta contendo implementações dos algoritmos de ordenação e funções auxiliares.
