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 III

Onde está a sua vida? Onde está a sua vida? Olá pessoal, tudo bem? Bem-vindos novamente a nossa disciplina.
A gente vai dar continuidade, a autema algoritmos de urlinação.
Nesta última visual sobre a urlinação, a gente vai ver um último algoritmo que diria que seria o mais complexo, porque ele usa uma estrutura de dados especial, que a gente já viu que são as árvores.
E aí ele usa essa estrutura para fazer a urlinação.
E ele é um dos algoritmos mais rápidos que existem atualmente.
Então, até mesmo por causa da sua complexidade, ele tem que valer a pena.
Então, ele é um dos algoritmos que, quando você faz análises de complexidade, com a comparação com outros algoritmos, ele acaba tendo um bom desempenho independente do da insuentrada.
Então, o rip sort, pessoal, é o nome do algoritmo.
Ele então usa uma estrutura ripe para ordenar esses elementos.
E o que é uma ripe? Então, uma ripe é uma estrutura de dados que é uma árvore.
E a gente usa uma árvore binária, lembrando lá das aulas de árvores.
Uma árvore binária é uma árvore que possui até dois filhos, 0 ou 2 filhos.
E então, essa aqui é uma exemplificação de uma árvore binária.
Só que a gente tem algumas particularidades desta árvore binária.
Então, existem dois conceitos que devem ser obedecidos para a gente dizer que uma árvore binária é considerada um ripe.
A primeira é a questão da orden.
Então, o item de qualquer nó deve satisfazir uma relação de orden com os nossos filhos.
Então, se a gente usa um ripe máximo, o pai, o valor do pai, tem que ser maior, ou igual, os valores dos filhos.
Essa a gente fizer um ripe mínimo, é o contrário.
No caso do ripe sorte, a gente usa um ripe máximo.
Então, o elemento pai, ele tem que ser maior, o valor tem que ser maior, do que os valores armazenados nos nossos filhos da esquerda e da direita.
E, um segundo conceito, é o conceito de forma.
Então, a árvore binária tem que ser completa até o penúltimo nível, sendo que, no último nível, nos nossos tem que estar agrupados à esquerda.
Vamos ver alguns exemplos aí.
Então, isso daqui, em relação à forma está ok.
Então, no último nível, os elementos, eles estão mais à esquerda possível desta árvore.
Nesse caso aqui não, porque esse cara aqui, esse elemento folha, ele não está mais à esquerda.
Ele poderia estar aqui desse lado, lado esquerdo, e desse nó.
Bem, também.
Em relação a mais alguns exemplos, então, isso daqui é um ripe máximo, porque o seu bedece, o conceito de forma, todos os elementos estão no último nível, tão mais à esquerda.
E, além disso, o em relação à ordem, você pode olhar aqui que cada nó, desse daqui, por exemplo, esse 16, ele é o maior elemento entre o 14 e o 10, que são os filhos.
O 14, por sua vez, é o maior elemento entre o 8 e o 7.
O 10 é o maior entre o 9 e o 3.
O 8 é o maior entre o 2 e o 4, e o 7 é o maior do que o 1.
Então, com isso, a gente considera esta árvore como um ripe máximo.
Nesse caso, aquele não é um ripe máximo, porque se ele mentou, poderia estar lá do esquerdo.
Aqui também não é um ripe máximo, porque, por causa desse elemento aqui, com esse elemento, então, o 14 é o pai, e ele é menor do que o 16, que é o filho da esquerda.
Então, você já peca nesse ponto aí, então, a gente já considera a árvore como uma árvore normal, que não é ripe.
Aqui também, ele não é ripe, porque aqui não é ripe, porque a gente tem aqui o 4, que é menor do que esse 8.
Leviça ao contrário, o 8 deveria ser o pai do 12 e do 4.
Está legal? A gente pode representar um ripe por meio de um vetor.
Então, no caso dessa árvore aqui, a gente pode representar ela como esse vetor, com os elementos de 0 a 9.
Então, o elemento raiz, o raiz, vai estar na posição 0, o segundo elemento na posição 1, e assim por diante.
Está sempre vai varrendo da esquerda para a direita, e de cima para baixo, para inserir no teu vetor.
A gente consegue, a partir desse vetor, acessar tanto o filho esquerdo a partir de um noca, então, o filho esquerdo, a gente usa 2k mais 1.
Então, por exemplo, eu quero saber quem é o meu filho do elemento 10.
10, o k é igual a 2.
Então, o filho dele vai ser 2 vezes 2 mais 1, 5.
Então, o elemento da posição 5 é 1, 9, que é esse cara aqui, o filho esquerdo do elemento 10.
E é a mesma coisa para o filho da direita.
A gente usa a forma 2k mais 2.
E o pai de onde é terminado o no, a gente usa k-1 dividido por 2.
Então, eu quero saber, por exemplo, quem é o pai do elemento 2? Então, a gente vai fazer o 7 menos 1, que vai dar 6, dividido por 2, vai me dar o 3.
Então, o elemento na posição 3 é o 8, que é exatamente esse elemento daqui, pai do 2.
E as folhas, pessoal, estão sempre em n sobre 2 em diante.
Então, como esse vetor tem 10 elementos, n igual a 10, então, a partir da Luins 5, que é esse cara aqui, daqui em diante, todos os nossos são folhas aqui em diante.
Tá legal? E como que funciona, então, o rip sort? Então, a gente vai usar essa estrutura rip máxima para ordenar um vetor como, a gente constrói um rip máxima a partir do vetor de entrada, aí, o que vai acontecer? A raiz desta árvore vai ser o maior elemento de todo o conjunto.
E aí, esse elemento vai ser trocado com o elemento da última posição desse vetor.
Aí, a gente desconsidera esse elemento.
A gente diz que ele já está na posição correta, então, a gente diz que a gente está diminuindo o tamanho do rip em uma unidade, que é dizer, a gente desconsidera esse último elemento.
Como a gente fez a troca do último elemento com o primeiro elemento que a raiz, essa raiz na árvore hip, ela vai estar.
.
.
ela precisa ser rearrangada.
E para isso, a gente faz um procedimento de rearranger o hip.
Agora, com n menos 1 elementos, isso se necessário.
E a gente vai repetir esse processo n menos 1 vez.
Depois, a gente rearranger a raiz vai ter o maior elemento, já desconsiderando aquele último que a gente já colocou na última posição.
Então, agora, a gente troca a raiz com a posição lá, a penúltima posição.
Dessa forma, a gente tem aqui a árvore hip já construída.
Esse elemento aqui vai.
.
.
é o maior elemento de todo o conjunto.
A gente vai colocar ele na posição correta, né? lá na X de 7, nesse caso.
A gente trocou e a gente vai fazer o rearrangeramento desse hip.
Então, a gente vai obter esta segunda árvore, esta segunda estrutura hip.
Esse elemento vai ser o maior elemento tirando um 92.
E a gente vai colocar ele na posição correta, que é na penúltima posição do vetor.
E vai considerar os elementos anteriores na hip.
Vai fazer novamente esse processo, vai obter o maior elemento da hip, que é o 57, vai colocar ele na posição correta e assim até finalizar todo o vetor.
Bom, o processo termina até que todos os elementos têm sido incluídos no vetor, na forma ordenada.
E para fazer esse processo, pessoal, é necessário duas coisas.
Primeira delas é saber construir um hip a partir de um vetor qualquer.
E a segunda coisa é saber como rearranger o hip, o procedimento esse que é realizado após você trocar raiz com o último elemento lá do vetor.
Então, vamos ver como que é feito este processo.
Olha só, exemplificando o rearrangeramento de um elemento, supondo que eu quero, eu tenho esse elemento 4, ele precisa ser colocado na posição correta.
Então, o que a gente vai fazer? A gente vai comparar ele com os filhos dele.
E a gente vai escolher o maior elemento dentro dos dois filhos para trocar com esse 4.
Então, entre o 14 e o 7, o maior é o 14.
Então, a gente sobe o 14 e desce o 4.
Então, ficaria aqui o 4 para baixo e o 14 lá para cima.
Só que esse 4 aqui, ele continua na posição correta.
Então, a gente vai fazer esse processo recursiva agora com os filhos, os novos filhos deste 4.
Então, entre o 2 e o 8, o maior é o 8.
Então, a gente troca, vai sobe o 8 e desce o 4.
Então, sobe o 8 e desce o 4.
E aí, quando chegou na folha, a gente para.
Então, quer dizer que agora a estrutura hip ela está correta.
Como quer dizer, a gente rearranjou o elemento 4 na sua posição correta da árvore.
Esse processo, pessoal, pode ser feito na forma de vetores.
Então, para a gente poder acessar os filhos da esquerda, da direita, a gente usa aquela forma que eu já falei para vocês que está aí fazendo essa troca até chegar nos nossos folhas aqui embaixo.
Legal.
E a construção do hip envolve a gente chamar esse procedimento de rearranjar a hip na forma ascendente, da indireção arraíspa em principal.
A partir, então, do n sobre 2 menos 1, que são os nossos não folhas.
Como eu falei para vocês, as folhas estão a partir do n sobre 2, na posição n sobre 2.
Então, a gente vai fazer da n sobre 2 menos 1, que é a partir daqui, onde você vai ter os elementos não folhas.
E aí, esse processo de rearranjava esse feito, a cada elemento aqui, até chegar na raiz.
E com isso, ao chamar pela última vez esse procedimento na raiz, a gente vai ter o hip construído, já pronto, para ser utilizado no HipSort.
Então, olha um exemplo.
Eu vou pegar que cor que é o último nó, não folha da minha hip.
É o n sobre 2 menos 1.
Como o n aqui é 10, eu faço n sobre 2, 5 menos 1, 4.
Então, esse elemento 16 que está aqui.
Então, exatamente esse cara da minha hip.
Então, eu vou aplicar o algoritmo de rearranjar a hip, a partir dessa posição.
Então, nesse caso, ele não vai mudar, porque eu sou um filho esquerdo, que é menor do que o 16.
Então, a árvore permanece do jeito que está.
Aí, a gente faz a aplicação desse mesmo algoritmo com o elemento menos 1, que é agora com 3, que corresponde ao elemento 2.
Na posição 3 com o elemento 2, faz com que eu tenha que rearranjar esse elemento 2.
Então, eu vou escolher o maior dos filhos esquerros e direitos.
No caso é o 14, então, eu vou subir o 14 e descer o 2.
Aí, eu tenho esta árvore aqui, rearranjado.
Faça agora com a posição menos 1, que é a 2, que é o elemento 3.
Mesma coisa, escolho entre 9 e 10, então, o 10 vai subir, o 3 vai descer.
E faço com o menos 1, que é agora com 1, que é esse elemento que está aqui.
Então, vou escolher o maior entre 14 e 16, então, eu vou subir o 16 e vou descer 1.
Neste caso, aqui, pessoal, a gente vai ter mais um processo recursivo, porque o 16 vai subir, aqui vai ficar 16, aqui vai descer 1.
Só que, entre esse 1 e entre esse 7, ainda eu preciso fazer esse reajuste.
Então, aqui, o 1 vai descer e o 7 também vai subir.
Então, esta aqui vai ser a minha árvore já finalizada para esta chamada.
E a última vez é para o a raiz, né, para a raiz, que é o elemento 4.
Então, eu vou subir o maior entre 16 e 10, que é o 16.
Então, com o 16 sobe, o 4 das, agora, entre 14 e o 7, eu vou subir o 14 e descer o 4.
E entre o 2 e o 8, eu vou subir o 8 e descer o 4.
E aí, isso que é a minha árvore finalizada, que foi aplicado com a raiz, então, aqui já tem a minha estrutura, a hip pronta, que é esse vetor que está aqui embaixo.
Aí, é onde entra o algoritmo, o hip sort, que consiste no que eu pegar esse elemento aqui inicial, que é a raiz, e trocar ele com um último elemento, que é esse cara que está aqui.
Então, aqui vai ficar 16, já vai estar na sua posição correta e o 1 vem para cá.
Com esse 1, a gente tem que aplicar o rearranger hip com essa raiz, e a gente faz esse processo que eu acabei de mostrar.
E vou fazendo isso até que eu consiga fazer a ordinação de todo o conjunto.
Tá legal? Para esse algoritmo, não vou falar mostrar para vocês o código, porque é bem complicado com vocês viram na explicação.
Mas a ideia, como eu falei, é você esterem um entendimento de até mesmo que superficial desses algoritmos.
Espero que vocês possam pelo menos ter tido uma noção de como que funciona o Hip Sort.
A gente não vai ter mais a aula sobre a ordinação, esses são os algoritmos principais que eu queria passar para vocês.
E a gente vai ver na próxima a vídeo aula alguns conceitos de busca, tal, algoritmos de busca.
Então, obrigado pela atenção de vocês e a gente se vê lá.
Até mais!