Ordenação de vetores é um dos mais importantes temas associados à programação. Nas faculdades de computação, o assunto é estudado especialmente em disciplinas como “Estruturas de Dados” ou “Análise e Projetos de Algoritmos”. Existem diversos algoritmos para realizar a tarefa, como o simples, mas pouco eficiente, “Método da Bolha” e o complexo, porém eficiente, “Quicksort”.

Mas e se desejássemos fazer a operação inversa? Explicando melhor: suponha que a partir de um vetor ordenado, por exemplo [1,2,3,4,5], nosso objetivo fosse embaralhar o conteúdo do mesmo, deixando-o, por exemplo com a configuração [3,4,1,5,2]. Ou seja, imagine que a tarefa a ser executada é a de “desordenar” um vetor ordenado! Por incrível que pareça, essa tarefa possui inúmeras aplicações práticas, que vão desde o campo dos jogos de computadores (ex: embaralhar as cartas em um jogo de baralho) até a área de mineração de dados (misturar os registros de uma base de dados para poder aplicar uma rotina de particionamento aleatório de dados).

Será que existe alguma forma simples e eficiente para embaralhar o conteúdo de vetores? A resposta é: sim, existem algumas formas e as apresentaremos nesse artigo através de exemplos em Java. O texto está dividido em duas partes: a primeira apresenta uma rápida revisão sobre a classe ArrayList (a mais utilizada para a implementação de arrays) e sobre a forma de ordenar e embaralhar dados contidos em elementos desse tipo com o uso da classe Collections. A segunda parte do artigo apresenta um método mais genérico para permitir o “embaralhamento” de qualquer tipo de vetor. Este método baseia-se no uso da classe java.util.Random e pode ser facilmente adaptado para qualquer outra linguagem de programação.

Embaralhando ArrayLists

Quando programamos em Java, normalmente os arrays são implementados com o uso de classes como ArrayList, Vector ou LinkedList, que implementam a interface List. A Listagem 1 apresenta um exemplo envolvendo a classe ArrayList. No exemplo, criamos um ArrayList de inteiros chamado “numeros” e adicionamos a ele 5 elementos. A seguir, imprimimos o seu conteúdo e apresentamos exemplos de chamadas aos métodos mais comumente utilizados nos ArrayLists, que executam tarefas como retornar propriedades do ArrayList, modificar o seu conteúdo, buscar um elemento, etc.


import java.util.ArrayList;
import java.util.List;

public class RevisaoArrayList {

	public static void main(String[] args) {
		
		//cria um ArrayList chamado "numeros"
		List<Integer> numeros = new ArrayList<Integer>();

		//adiciona 5 elementos ao ArrayList com o método "add"
		//cada númeor é sempre inserido no fim da lista
		numeros.add(10);
		numeros.add(1000);
		numeros.add(500);
		numeros.add(40);
		numeros.add(-1);

		//imprime o conteúdo do ArrayList
		System.out.println("numeros: " + numeros.toString()); //imprime o conteúdo do array
		
		//alguns métodos...
		System.out.println("tamanho: " + numeros.size());
		System.out.println("primeiro elemento: " + numeros.get(0));
		System.out.println("terceiro elemento: " + numeros.get(2));
		System.out.println("ultimo elemento: " + numeros.get(numeros.size()-1));
		
		//troca o valor do terceiro elemento de 500 para 50
		numeros.set(2, 50);
		System.out.println("configuracao de numeros apos troca de valor: " + numeros.toString());

		//remove o segundo elemento
		numeros.remove(1);
		System.out.println("configuracao de numeros apos remocao: " + numeros.toString());
		
		//verifica se o array contém os elementos 40 e 15
		System.out.println("contem o elemento 40? " + numeros.contains(40));
		System.out.println("contem o elemento 15? " + numeros.contains(15));
		
	}
	
}
Listagem 1. Exemplo básico de utilização da classe ArrayList

O resultado da execução do programa é mostrado na Figura 1.

Execução do programa da Listagem 1
Figura 1. Execução do programa da Listagem 1

Para ordenar ArrayLists fazemos uso da classe Collections. Esta classe contém uma série de métodos estáticos que atuam sobre coleções. O método sort é o responsável por executar a operação de ordenação, conforme mostra o programa da Listagem 2.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class OrdenaArrayList {

	public static void main(String[] args) {
		
		//cria um ArrayList chamado "numeros"
		List<Integer> numeros = new ArrayList<Integer>();

		//adiciona 5 elementos ao ArrayList com o método "add"
		//cada númeor é sempre inserido no fim da lista
		numeros.add(10);
		numeros.add(1000);
		numeros.add(500);
		numeros.add(40);
		numeros.add(-1);

		System.out.println("antes de ordenar: " + numeros.toString());
		
		Collections.sort(numeros); //ordena o conteúdo do ArrayList
		
		System.out.println("depois de ordenar: " + numeros.toString());
		
	}
	
}
Listagem 2. Ordenação de um ArrayList com Collections.sort

Veja o resultado da execução na Figura 2.

Execução do programa da Listagem 2
Figura 2. Execução do programa da Listagem 2

A classe Collections possibilita a realização de outras duas operações interessantes relacionadas a ordenação. Um das operações consiste em inverter a ordem dos elementos do da coleção, realizada pelo método “reverse”. A outra é exatamente o tema de nosso artigo: a operação de embaralhar os dados, executada pelo método “shuffle”. Veja os exemplos na Listagem 3.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class OrdenaArrayList {

	public static void main(String[] args) {
		
		//cria um ArrayList chamado "numeros"
		List<Integer> numeros = new ArrayList<Integer>();

		//adiciona 5 elementos ao ArrayList com o método "add"
		//cada númeor é sempre inserido no fim da lista
		numeros.add(10);
		numeros.add(1000);
		numeros.add(500);
		numeros.add(40);
		numeros.add(-1);

		//ordena / reverte / embaralha o conteúdo do ArrayList
		System.out.println("antes de ordenar: " + numeros.toString());
	
		Collections.sort(numeros);
		
		System.out.println("depois de ordenar: " + numeros.toString());
		
		Collections.reverse(numeros);
		
		System.out.println("depois de reverter: " + numeros.toString());

		Collections.shuffle(numeros);
		
		System.out.println("depois de embaralhar: " + numeros.toString());

	}
	
}
Listagem 3. Embaralhando o array com o método shuffle da classe Collections

Veja o resultado da execução do programa na Figura 3.

Execução do programa da Listagem 3
Figura 3. Execução do programa da Listagem 3

Um Procedimento Genérico para Embaralhar Arrays

Na seção anterior, vimos que é muito simples embaralhar o conteúdo de coleções, pois a classe “Collections” oferece o método “shuffle” que realiza a tarefa de maneira transparente.

No entanto, em muitas situações práticas podemos nosso vetor pode estar sendo implementado de outra forma diferente de uma List. Poderíamos, por exemplo, estar utilizando um array comum, como o mostrado na implementação da Listagem 4. Neste exemplo, “numeros” é um array comum que possui 10 elementos, todos inseridos de forma ordenada.


public class EmbaralharArrayComum {

	public static void main(String[] args) {
		
		//cria e preenche o array "numeros"
		int[] numeros = { 
			    100, 200, 300,
			    400, 500, 600, 
			    700, 800, 900, 1000
			};
		
		//imprime o conteúdo do array
		for (int n: numeros) {
			System.out.println(n);
		}
		
	}
	
}
Listagem 4. Programa com um Array Comum
Execução do programa da Listagem 4
Figura 4. Execução do programa da Listagem 4

Não é possível aplicar os métodos da classe “Collections” sobre arrays comuns. Sendo assim, como faríamos para embaralhar os dados? Felizmente a tarefa não é muito difícil, mas a diferença é que desta vez teremos que implementar o nosso próprio método. No exemplo da Listagem 5, criamos o método “embaralhar” para executar a tarefa de “bagunçar” os dados do array “numeros”. A explicação sobre o funcionamento do método é apresentada logo em seguida ao código.


import java.util.Random;


public class EmbaralharArrayComum {

	//método estático que embaralha os elementos de um vetor de inteiros
	public static void embaralhar(int [] v) {
		
		Random random = new Random();
		
		for (int i=0; i < (v.length - 1); i++) {

			//sorteia um índice
			int j = random.nextInt(v.length); 
			
			//troca o conteúdo dos índices i e j do vetor
			int temp = v[i];
			v[i] = v[j];
			v[j] = temp;
		}
		
	}
	
	public static void main(String[] args) {
		
		//cria e preenche o array "numeros"
		int[] numeros = { 
			    100, 200, 300,
			    400, 500, 600, 
			    700, 800, 900, 1000
			};
	
		
		//imprime o conteúdo do array (antes de embaralhar)
		System.out.print("Antes de embaralhar: ");
		for (int n: numeros) {
			System.out.print(n + " ");
		}
		
		System.out.println();

		//embaralha o array 
		embaralhar(numeros);

		//imprime o conteúdo do array (depois de embaralhado)
		System.out.print("Depois de embaralhar: ");
		for (int n: numeros) {
			System.out.print(n + " ");
		}
		
	}
	
}
Listagem 5. Embaralhando um Array Comum
Execução do programa da Listagem 5
Figura 5. Execução do programa da Listagem 5

Explicação: a técnica utilizada pelo método “embaralhar” consiste basicamente em implementar um laço com o comando for para percorrer todo o array. A cada iteração do laço, dois elementos do array são trocados de lugar. Um dos elementos trocados é o que tiver o índice associado ao valor corrente da variável do for (variável “i”). O outro elemento terá o seu índice sorteado aleatoriamente com o uso do método “nextInt” da classe java.util.Random (classe Java que gera números aleatórios).

Conclusão

Este artigo apresentou técnicas para embaralhar dados de vetores. A primeira técnica pode ser utilizada quando o array é implementado através de uma coleção do Java, como ArrayList, consistindo simplesmente em aplicar o método shuffle da classe Collections.

A segunda técnica é um pouco mais interessante, pois pode ser aplicada sobre qualquer tipo de array e pode ser facilmente adaptada para qualquer outra linguagem de programação. Ela funciona trocando pares de elementos do array dentro de um laço for, onde um dos elementos a ser trocado é sorteado de maneira aleatória.

Embora os exemplos apresentados tenham se baseado em arrays de inteiros, é possível aplicar normalmente as técnicas sobre arrays de outros tipos.