Merge Sort: Ordenação por Intercalação

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Algoritmos e Programação de Computadores II - Algoritmos clássicos de ordenação II

O Lá pessoal, bem-vindos novamente a nossa disciplina.
A gente vai dar continuidade aos algoritmos de urlinação.
A video de aula anterior a gente aprendeu o bubble sort e o insertion sort.
E na esta video a aula, a gente vai aprender mais dois algoritmos de urlinação, que são um pouquinho mais complexos, porém são mais eficientes do que os dois anteriores.
Vamos tentar entender como que eles funcionam.
Primeiro deles, pessoal, que eu quero ensinar, é o merge sort ou também chamado de urlinação por intercalação.
Como que ele funciona? Ele adota uma estratégia que a gente chama de dividir para conquistar.
É a ideia de você ter um problema para resolver.
Ao invés de você tentar resolver todo esse problema de uma vez só, você divide esse problema em subproblemas que sejam menores.
Resolve cada subproblema separadamente, que vai ser mais fácil.
Depois você tenta juntar estas soluções para gerar a solução final pro problema pro completo.
Aplicando isso no problema de urlinação, a gente vai ter um vetor, ou uma lista, que vai ser inicialmente dividida em duas partes de uma maneira recursiva.
Você vai fazer a divisão, esse vetor em duas partes.
Cada parte você divide em mais duas partes.
E assim por diante, até que você chegue num único vetor de um tamanho só de tamanho 1.
Depois você, que já vai estar ordenado, e depois você vai combinando esses vetores, já fazendo a ordinação.
Em uma característica do merge sorte, ele usa um vetor auxiliar para realizar essa intercalação, conforme a gente vai ver daqui a pouco na implementação.
Olha só um exemplo.
Eu imagino que eu tenho uma lista.
A gente vai fazer inicialmente uma divisão em duas partes iguais, ou quase iguais.
A gente vai cortar aqui no meio.
A gente vai ter então dois subvetores.
Cada subvitor vai ser ordenado separadamente, só que a gente vai aplicar essa divisão recursivamente.
A gente vai dividir novamente esse vetor no meio, e esse do lado de cá também no meio.
Depois disso, a gente vai ter então quatro subvetores.
Cada um desses quatro subvetores, a gente vai dividir novamente no meio.
Isso vai te dar um monte de subvetores, 8 subvetores, onde cada subvitor tem apenas um elemento.
Um vetor tem um elemento só, ele já é considerado ordenado.
Não tem o que você fazer.
Aqui acaba o processo de divisão.
E aí entra a fase agora de intercalação, ou de conquista, que é quando você começa a combinar esses resultados parciais em problemas em soluções maiores.
A gente vai fazer a combinação desta solução com esta solução, que vai fazer com que a gente coloque esses dois elementos juntos, só que de uma maneira ordenada, isso que vai te dar 2 e 5.
Esses dois aqui também vão ser ordenados, vão ser intercalados, combinados com 4 e 7, também, ordenado, um e 3 também vão ficar ordenados, e o 2 e 6.
Que seria essa primeira fase aqui dentro de intercalação? Após isso, você faz novamente esse mesmo processo, você vai combinar esse vetor com esse vetor, também de uma maneira ordenada.
Então, isso aqui vai te gerar os elementos 2, 4, 5 e 7.
E desse lado você vai combinar esse com esse, que vai te dar 1, 2, 3 e 6.
Tá legal? E por fim, você combina esse com esse, te dando aqui o vetor completo, ordenado.
Então, esta aqui seria a segunda parte, e aqui o vetor ordenado.
Tá legal? Esse processo, pessoal, de intercalação, acaba sendo mais fácil de se realizar, porque como que funciona? Imagina que você está nessa situação, onde você tem esses 2 vetores, e você quer combinar eles em um só.
Como cada um já está ordenado, o que você vai fazer? Você vai ter um ponteiro aqui para esse primeiro elemento, um ponteiro para esse primeiro elemento, e aí você vai escolher o menor elemento dentro esses 2.
No caso, seria 1, que vai ser colocado aqui.
E quando você escolhe um desse lado, você incrementa esse ponteiro para cá.
E aí você escolhe um dos dois, também quer dizer, o menor elemento dentro desse cara que está aqui e esse que está aqui.
2 com 2, você pode escolher qualquer um deles.
Então, você pode escolher, por exemplo, esse cara que está aqui, vai vir para cá, e vai incrementar esse ponteiro.
Aí você vai comparar esse 2 com esse 4, aí você vai escolher o menor, seria esse 2 aqui, vai colocar na posição seguinte, e vai incrementar esse ponteiro.
Aí você vai comparar esse 3 com esse 4, vai colocar o menor, que é o 3, incrementa esse ponteiro, vem para cá.
Comparo o 4 com o 6, aí adiciona o menor, que é o 4, incrementa esse ponteiro, aí compara o 5 com o 6, coloca-la o menor, e assim por diante.
Então, repare, pessoal, que é só você variar uma vez só esse vetor, e uma vez só esse vetor, pegando sempre o menor, dentro dos dois, para colocar no vetor ordenado.
Tá bom? Então, essa daqui é a implementação do merge sort, eu vou passar, então, o meu vetor, uma lista comparando, e também vou passar aqui, dois variáveis, início e fim, que vai ser o início do vetor, que seria zero, na posição inicial, desta lista, que é zero, e o fim, que seria o len de V, menos um, tá na primeira chamada, aí que é o índice da última posição, desta lista.
Aqui são as chamadas secursivas, reparem que eu tô pegando o meio desse vetor, que é, faço início mais fim dividido por dois, divisão por inteiro, pego o meio, e aplico a recorção do início até o meio, e do meio mais um até o fim.
Então, essa aqui é a minha divisão.
Então, cada chamada dessa vai chamar a própria função, que vai fazer novamente uma divisão no meio, que também vai fazer uma nova chamada para as duas metades desse vetor, até que o início seja igual ou maior do que o fim.
Quando voltar a pessoal desse processo, ele entra nesta função intercala, que é a fase de conquista do algoritmo merge sorte, como que funciona esta função intercala? A gente vai usar dois vetores auxiliar o l e o r, que vai receber cada um, uma sublista do vetor original.
A primeira vai ser de início até meio mais um, excluindo o meio mais um até meio, incluindo o meio, e o r vai ser de meio mais um, incluindo, mais um até o fim mais um, também que vai incluir o valor de fim.
Aqui embaixo, pessoal, eu estou adicionando um valor de centenela para cada um desses vetores, l e r, esses valores que eu estou colocando, nove nove nove, são valores altos, ou máximo que nenhum elemento do vetor deve ser maior do que ele.
Se você quiser, pode aumentar esse valor, colocar um valor que seja mais alto do que no 119.
A ideia de adicionar esses centenelas é para facilitar o processo seguinte de evitar de você incrementar esses índices e j, que mais o que deve.
Então, eu vou fazer um valor de k, percorrer de início até fim mais um, e aqui é onde eu vou escolher, se eu vou pegar o elemento da esquerda ou da direita para inserir no vetor ordenado.
Então, se o lado esquerdo for menor do que o lado direito, eu vou pegar o da esquerda, e aí vou incrementar o ponteiro i.
Se não, eu pego o lado direito, incremento ponteiro j.
Então, é como se eu tivesse algo assim, eu vou ter um vetor aqui, outro vetor aqui, um meu í vai estar aqui, meu j vai estar aqui, eu vou ter essa última posição que é um mil centenela, então, eu vou sempre escolher o LDI, entre o LDI e o LDI, que é exatamente essa parte que está aqui.
Tá legal? Então, eu vou deixar para vocês estudarem um pouco melhor esse algoritmo, tentar entender ele, de uma maneira mais com paciência, com o tempo, para verificar o funcionamento desse algoritmo.
O próximo que a gente vê é o QuickSort.
O QuickSort, pessoal, ele também se baseia na estratégia de dividir para conquistar a ideia dele, a dividir o vetor em dois vetores menores, que vão ser ordenados, independente, independentemente, combinados para produzir o resultado final.
O primeiro passo é escolher um elemento pivô, a gente chama de x, e colocar ele na sua posição correta.
Aí, a gente vai ordenar de forma que os elementos, a esquerda desse pivô, sejam menores ou iguais a ele, e os elementos à direita, sejam maiores ou iguais a ele.
A gente vai percorrer o vetor, para fazer isso, a gente vai percorrer o vetor da esquerda para a direita, até que o verde seja maior ou igual a esse pivô, e da direita para a esquerda, até que o verde j seja menor ou igual a pivô.
Quando isso acontecer, quando chegar nessas condições de parada, a gente troca de posição o veículo com o vejô, incrementa e decrementa a j e continua esse processo, até que e j se cruzem.
Quando eles se cruzarem, essa interação vai finalizar, e aí a gente vai aplicar uma chamada recursiva, v0 até vdj, e vdy até vn-1.
Então, vamos ver um exemplo aí, como que vai funcionar.
Então, eu tenho esse vetor original, o que eu vou fazer? Eu vou ter dois ponteiros, duas variáveis, que vão receber o valor zero e vdy menos 1.
Tem o meu elemento pivô, que vai ser o meio.
Então, o que eu faço aqui? Eu pego o v do início, mais o fim de vídeo do por 2, que vai me dar o elemento 37, que é esse cara que está aqui, e esse é o pivô.
Então, eu vou começar incrementando i até que i seja maior ou igual a 37, que ele vai parar, então, exatamente nessa posição.
Depois, eu vou decrementando o j até que j seja menor ou igual a 37, que, no caso, é aqui nessa posição.
Quando o pareio i e pareio j, eu vou fazer a troca entre eles, então, 33 vai do lugar de 57, ou 57 para no lugar de 33, incremento o i para a próxima posição, decremento o j para a posição menos 1, e continua esse processo.
Então, vou procurar um x, seja maior do que pivô.
Na verdade, não é i, é v, e maior ou igual a pivô, que, no caso, é o próprio 37, que está aqui.
Vou escolher um v, e j, que seja menor ou igual a pivô, que, no caso, seria esse cara.
Aí, vou fazer a troca entre eles, então, 32 com 37, vão mudar de lugar, vou incrementar o i e decrementar o j, e aí, quando, aí, ocorre o cruzamento entre i e j, quando ocorre esse cruzamento, o que que aconteceu? O subvitor de 0 até j, já vai estar, vão ser menores ou iguais a pivô, e os elementos da posição i até n menos 1, e até a posição n menos 1, vão ser maiores ou iguais do que o elemento pivô.
E, nesse caso, a gente não precisa mais trocar nenhum elemento aqui com esse outro conjunto, nenhum elemento aqui com esse outro conjunto.
A gente pode aplicar, então, a recursão para cada subvitor desse separadamente.
E, exatamente, essa é a proposta agora do exercício, então, fazer esse mesmo processo que eu fiz, agora, para esse subvitor aqui separado, e depois, para esse subvitor aqui separado, então, vou deixar como exercício vocês fazerem aí a execução desse algoritmo.
Aqui, eu tenho a implementação, está pessoal do QuickSort, que é um pouco complexa, assim como o algoritmo, também é complexo, mas eu vou deixar para vocês também dar uma estudada, tentar entender, pelo menos identificar qual é a cada etapa, do algoritmo que eu expliquei, identificar a cada etapa desta, aí nesse algoritmo.
Então, por exemplo, aqui, a identificação do meio do vetor, a determinar qual é o pivô, o elemento central do vetor, está assim por diante, até que chega aqui na recursão para os subvitores e assim por diante.
Muito bem, gente, então, essa aqui foi mais uma videoaula sobre ordinação, como eu falei para vocês, a ideia não é que vocês sejam fiquem especialistas em algoritmos de ordinação, mas sim que vocês têm uma moção de dos diferentes tipos de algoritmos que podem se aplicados para realizar a ordinação de vetores, e a gente vai ter mais uma videoaula para a sua abro-ordinação, vou apresentar para vocês mais alguns algoritmos, e a gente se vê, então, nestas próximas videoaulas.
Obrigado e até mais.