Como embaralhar um array em Swift: otimização e desempenho

Treinador Online de Python para Iniciantes

Aprenda Python facilmente sem sobrecarga teórica. Resolva tarefas práticas com verificação automática e escreva código diretamente no navegador.

Start Course

Como embaralhar um array em Swift corretamente: do iniciante ao profissional

Você já pensou em como criar uma playlist aleatória no seu aplicativo? Ou talvez precisasse embaralhar perguntas em um quiz para que elas aparecessem sempre em uma ordem diferente? Se você trabalha com Swift, mais cedo ou mais tarde enfrentará a tarefa: como embaralhar um array (shuffle array). Esta pergunta no Stack Overflow acumulou milhares de visualizações, e não é à toa — há mais armadilhas aqui do que parece à primeira vista.

Neste artigo, não vamos apenas mostrar como chamar shuffle(). Vamos olhar sob o capô: analisar algoritmos, comparar desempenho, aprender a fazer um embaralhamento otimizado e entender quando o método padrão é um problema e quando é a melhor coisa que a humanidade já inventou. Vamos lá!

\n\n

Por que simplesmente "random" é uma má ideia?

Suponha que você tenha um array:

var cards = ["Ás", "Rei", "Dama", "Valete"]

A maneira mais ingênua é criar um novo array e inserir elementos em posições aleatórias. Parece lógico, certo?

func naiveShuffle(_ array: [String]) -> [String] {\n    var shuffled = [String]()\n    for element in array {\n        let randomIndex = Int.random(in: 0...shuffled.count)\n        shuffled.insert(element, at: randomIndex)\n    }\n    return shuffled\n}

Em arrays pequenos (4-10 elementos) isso funciona. Mas assim que o número de elementos ultrapassa uma centena, você sentirá a dor. Por quê? Porque insert(at:) tem complexidade O(n) — cada vez que você insere um elemento no início ou no meio, todos os elementos subsequentes são deslocados. Complexidade final: O(n²). Para um array de 1000 elementos, são 500.000 operações. Para 10.000, já são 50 milhões. O aplicativo começará a "engasgar", o usuário irá embora, a classificação cairá. Não faça isso.

\n\n

Método nativo shuffle(): seu novo melhor amigo

A partir do Swift 4.2, temos o método nativo shuffle() (para arrays mutáveis) e shuffled() (retorna um novo array). Veja como funciona:

var numbers = [1, 2, 3, 4, 5]\nnumbers.shuffle()  // modifica o array original\nprint(numbers)     // exemplo: [3, 1, 5, 2, 4]\n\nlet shuffledNumbers = numbers.shuffled()  // novo array\nprint(shuffledNumbers)                    // [4, 2, 1, 5, 3]

Sob o capô, a Apple usa o algoritmo de Fisher-Yates (também conhecido como algoritmo de Knuth). Este é o padrão ouro de embaralhamento. Como funciona? Percorremos o array do último elemento ao primeiro, para cada um escolhemos um índice aleatório de 0 até a posição atual e trocamos os elementos de lugar. Complexidade: O(n). Para um array de 10.000 elementos — apenas 10.000 operações. 5000 vezes mais rápido que a abordagem ingênua!

\n\n

Algoritmo de Fisher-Yates: explicação simplificada

Vamos implementá-lo manualmente para entender a mágica:

extension Array {\n    mutating func customShuffle() {\n        for i in stride(from: count - 1, through: 1, by: -1) {\n            let j = Int.random(in: 0...i)\n            swapAt(i, j)\n        }\n    }\n}\n\nvar deck = Array(1...10)\ndeck.customShuffle()\nprint(deck) // [6, 2, 9, 1, 8, 4, 7, 3, 10, 5]

O que está acontecendo aqui? Suponha um array de 5 elementos. Começamos pelo índice 4 (o último). Escolhemos um número aleatório de 0 a 4, trocamos os elementos. Depois passamos para o índice 3, escolhemos de 0 a 3, trocamos. E assim até o índice 1. Cada elemento tem a garantia de estar em uma posição aleatória exatamente uma vez. Sem deslocamentos, sem reinserções — matemática pura.

Uma nuance importante: no algoritmo de Fisher-Yates, não se pode escolher um índice aleatório de 0 a count-1 em cada etapa. Por quê? Porque então alguns elementos podem permanecer em seus lugares, enquanto outros podem ser movidos várias vezes, o que quebra a uniformidade da distribuição. Confie na implementação padrão da Apple — ela é otimizada.