10-Algoritmo de Intercalação 2

Introdução

O que acontece quando eu recebo cinco cartas de baralho? Em diversos jogos é interessante que as cartas menores fiquem separadas em uma parte, enquanto as maiores fiquem em outra. Assim, fica mais fácil encontrar os elementos que tenho na mão. Como é costume trabalhar desta maneira, é comum que as pessoas façam esta ordenação manualmente.

Mas isso quando o número de elementos é pequeno. Se foram 15 cartas já começa a complicar um pouco, a dificuldade aumenta. Quanto maior for a quantidade de itens para serem ordenamos, mais trabalhoso será o processo.

Por quê? Porque os algoritmos que as pessoas usam são o Ordenação por Seleção ( Selection Sort ) e o Ordenação por Inserção ( Insertion Sort), e à medida que o número de elementos cresce, eles começam a ficar muito lentos. Serão muitas operações e trocas, e isto justifica a demora.

Dividir para Conquistar

Quando temos muitos elementos para ordenar ninguém quer ser a pessoa que executará a tarefa de ordenação. No fim do jogo de baralho ninguém quer ficar responsável por ordenar, porque são muitos elementos. É trabalhoso fazer um Selection Sort e um Insertion Sort, porque teremos que executar muitas operações. Será que não existe outros algoritmos ou processos mais rápidos?

O que nós fazemos? Quebramos o nosso problema em pedaços para serem ordenados e depois de ordenados, juntamos as partes. É a tática conhecida como Dividir para Conquistar onde dividimos o problema em partes menores que podem ser executadas por diferentes pessoas ou máquinas.

Podemos fazer o mesmo processo com as provas de alunos. Por exemplo, vamos corrigir as provas do Enem e precisamos ordenar 1 milhão delas. Que trabalhoso executar o Insertion Sort! E se encontrássemos uma outra maneira de fazer a ordenação?

Vamos usar a maneira que já conhecemos ao organizarmos as cartas de baralho, o dinheirinho do Jogo da Vida... Vamos usar o exemplo das provas dos nove alunos:

Ao invés de ordenar todos os itens, eu divido os alunos entre duas pessoas: o Aniche e o Alberto. Então, cada um deles será responsável pela ordenação considerando as notas dos alunos. Vamos observar como ficam os grupos do Aniche e do Alberto ordenados:

Agora que já temos os dois grupos ordenados, o nosso trabalho será uni-los. A sacada quando trabalhamos com um número grande de elementos, é dividir a tarefa entre as pessoas. No nosso exemplo, o grupo de aluno foi dividido entre o Aniche e o Alberto e cada um teve que organizar a metade.

Então, o problema que quero resolver é: considerando o grupo do Aniche e o grupo do Alberto já ordenados - ou seja, dados os arrays ordenados dos dois - o que teremos que fazer é intercalar os elementos das duas sequências gerando um novo array todo organizado.

Então, dado o grupo do Aniche e o do Alberto, o que farei é intercalar todos os objetos para que eles fiquem ordenados em um único array. Dado dois arrays ordenados, intercale os elementos e monte um array ordenado. Se formos capazes de fazer isto, será um enorme avanço, porque basta dividir a ordenação entre as pessoas e depois, unir os elementos ordenados - tarefa que já sabemos fazer.

Vamos tentar unir dois arrays de uma maneira mais rápida do que faríamos com outros algoritmos. E assim conseguir ordenar uma quantidade de dados muito maiores. Com o algoritmos que estamos montando, nós seremos capazes. O primeiro passo será: considerando que os grupos do Aniche e do Alberto já estão ordenados, como iremos unir estes dois?

Como juntar ou intercalar duas listas ordenadas

Baseado no que usamos cotidianamente, no jogo de truco, no buraco, no Jogo da Vida, qualquer atividade que exija a distribuição de diversos itens. Podemos distribuir entre os participantes para que todos ajudem a organizar e depois juntamos tudo novamente. Queremos resolver o problema de reagrupar os elementos.

Considerando os alunos do Aniche e do Alberto, que já foram ordenados, como podemos intercalar os nove alunos? Teremos trabalhar com a variável de 9.

Sempre que estamos trabalhando com ordenação, em linguagem de programação que o array já nos diz qual o número total de elementos, nós conseguimos extrair o número total. Como queremos generalizar para qualquer linguagem de programação, temos que saber o total de alunos. Que no caso são 9 alunos, iremos reagrupá-los em um único array que caiba todos eles.

Então, nosso primeiro passo será criar umarray com um tamanho que caiba os 9 elementos.

Caso contrário, não teremos como juntar todos os elementos em um único array. Agora que temos um lista com tamanho 9, podemos começar.

Iremos iniciar com o primeiro elemento de cada grupo ordenado, porque começar pelo meio não faria sentido. Seguiremos a opção mais simples.

Como já colocamos o Jonas no início da lista, vamos comparar agora o próximo dos grupos do Aniche e do Alberto: o André e a Juliana. Um aluno tirou uma nota 4 enquanto o outro tirou uma nota 6,7. Qual dos dois tirou uma nota menor? O André.Vou descer o André para o array.

Seguimos comparando as próximas alunas de cada grupo: Mariana e Juliana. Qual das duas tirou uma nota menor? A Mariana. Vamos desce-la para o array.

Os próximos alunos a terem as notas comparadas serão: o Carlos e a Juliana. Quem se saiu pior na prova? A Juliana. Vamos desce-la para o novo array.

Iremos comparar as notas do Guilherme e do Carlos e repetir o processo até que ambos os vetores de Aniche e Alberto tenham sido percorridos. Ao final teremos um unico vetor contendo todos os elementos ordenados.

O que fizemos? Comparamos o elemento de um grupo com o de outro e identificamos qual era o menor. O maior permanecia e o menor descia para o novo array. Seguimos comparando as notas dos alunos e os menores eram colocados na lista abaixo.

No fim, temos um array quase completo, porém sobraram algumas alunas no grupo do Alberto. Nós simplesmente descemos as duas e o array ficou ordenado. O mesmo é feito caso existem elementos no grupo do Aniche. Descemos os elementos para a lista abaixo.

O algoritmo que acabamos de estudar chama ordenação por intercalação pois ele ordena um conjunto a partir da intercalação dos elementos de outros conjuntos já ordenados. É importante lembrar que os outros conjuntos já deverão ter sido ordenados para que a ordenação por intercalação seja feita corretamente.