No mundo da programação, manipular arrays é uma habilidade fundamental. Uma matriz pode ser embaralhada, o que inclui a reorganização aleatória de seus elementos, como um processo comum. Este procedimento é essencial para coisas como construir decks de jogos aleatórios, executar simulações estatísticas ou apenas exibir dados de forma mais aleatória. Inicialmente, há muita lógica que podemos aplicar para embaralhar um array; podemos usar diferentes tipos de estruturas de coleção, como ArrayList, conjuntos de hash, listas vinculadas, etc.
Algoritmo para embaralhar um array:
A seguir está o algoritmo para embaralhar uma matriz,
PASSO 1: COMEÇAR
PASSO 2: Comece no último elemento do array e volte até o primeiro elemento.
ETAPA 3: Para cada elemento no índice i, gere um índice aleatório j tal que j esteja no intervalo [0, i].
PASSO 4: Troque os elementos nos índices i e j.
PASSO 5: Repita as etapas 2 e 3 para todos os elementos da matriz, retrocedendo do último elemento para o primeiro.
PASSO 6: FIM
Podemos embaralhar um array contendo diferentes tipos de elementos, como inteiros, caracteres, etc.
Algoritmo de embaralhamento de Fisher-yates:
O seguinte programa Java é usado para embaralhar um array composto por inteiros.
ArrayShuffle.java
import java.util.Random; public class ArrayShuffler { public static void main(String[] args) { // Sample array of integers int[] array = {1, 2, 3, 4, 5}; // Shuffle the array shuffleArray(array); // Print the shuffled array for (int num : array) { System.out.print(num + ' '); } } public static void shuffleArray(int[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { // Generate a random index between 0 and i (inclusive) int j = rand.nextInt(i + 1); // Swap the elements at indices i and j int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Saída:
1 3 2 4 5
A saída pode ser diferente se você executá-la em seu sistema porque ela organiza os elementos aleatoriamente e gera a matriz embaralhada.
Complexidades:
A complexidade espacial do algoritmo shuffle é O(1) porque ele não usa nenhuma estrutura de dados extra que dependa do tamanho do array. A complexidade de tempo do algoritmo de embaralhamento de Fisher-Yates usado no método shuffleArray() é O(n), onde n é o número de elementos na matriz.
Embaralhando array usando listas em Java:
ShuffleArray.java
import java.util.Arrays; import java.util.Collections; import java.util.List; public class ShuffleArray { public static void main(String[] args) { Integer[] intArray = {1, 2, 3, 4, 5, 6, 7}; List intList = Arrays.asList(intArray); Collections.shuffle(intList); intList.toArray(intArray); // This line will not resize the array System.out.println(Arrays.toString(intArray)); } } Saída:
[4, 1, 7, 3, 6, 5, 2]
A saída pode ser diferente se você executá-la em seu sistema porque ela organiza os elementos aleatoriamente e gera a matriz embaralhada.
Complexidades:
comentários java
A complexidade do espaço também é O(n). Isso ocorre porque o método Collections.shuffle() modifica a lista original e não usa nenhuma estrutura de dados adicional. A complexidade de tempo deste código é O(n), onde n é o número de elementos na matriz.
Matriz aleatória contendo caracteres:
ShuffleCharacters.java
import java.util.Arrays; import java.util.Random; public class ShuffleCharacters { public static void main(String[] args) { char[] charArray = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; shuffleArray(charArray); System.out.println('Shuffled Characters: ' + Arrays.toString(charArray)); } public static void shuffleArray(char[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { int j = rand.nextInt(i + 1); // Swap characters at indices i and j char temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Saída:
Shuffled Characters: [e, f, g, d, a, c, b]
A saída pode ser diferente se você executá-la em seu sistema porque ela organiza os elementos aleatoriamente e gera a matriz embaralhada.
Complexidades:
A complexidade espacial do algoritmo shuffle é O(1) porque ele não usa nenhuma estrutura de dados extra que dependa do tamanho do array. A complexidade de tempo do programa usado no método shuffleArray() é O(n), onde n é o número de caracteres no array.
Conclusão:
Embaralhar um array em Java é uma habilidade crucial que capacita os desenvolvedores a criar arranjos de dados aleatórios e imparciais. Ao longo desta exploração, cobrimos duas abordagens eficazes: usar o método Collections.shuffle() para arrays não primitivos e implementar o algoritmo de embaralhamento de Fisher-Yates para arrays primitivos. O método Collections.shuffle() simplifica o processo de embaralhamento de objetos ou matrizes não primitivas, aproveitando funcionalidades integradas. Por outro lado, o algoritmo Fisher-Yates fornece uma maneira eficiente e imparcial de embaralhar matrizes primitivas, garantindo uniformidade nas permutações.