Convém entender diferentes métodos para resolver o mesmo problema, como ordenar registros e, depois, buscar com eficiência. A aula apresenta fundamentos de ordenação, tipos de ordenação e dois algoritmos clássicos: Bubble Sort e Insertion Sort.
A ordenação é o ato de reorganizar uma sequência de elementos para que sigam uma relação de ordem. Quando a lista é grande, pode haver vantagens em ordenar uma vez e realizar várias buscas usando técnicas eficientes, como a busca binária, após a ordenação.
Exemplos de algoritmos discutidos:
Observação prática: embora Bubble Sort e Insertion Sort sejam intuitivos, sua complexidade pode ser O(n^2) no pior caso, tornando-se inadequados para grandes volumes de dados em aplicações reais. Em muitos contextos, é útil ordenar uma vez e depois aplicar buscas mais eficientes, como a busca binária, especialmente se houver várias consultas.
O Lá pessoal bem-vindo novamente nossa disciplina de algoritmos e programações computadores 2 para o Niverspe.
Nesta semana, a gente vai aprender os algoritmos de originação e busca.
Esse assunto, pessoal, é bastante discutido, bastante estudado, principalmente nos cursos de computação, porque permitem que você entenda que, primeira coisa, que existem vários algoritmos para resolver o mesmo problema, no caso, nesse caso, o que a gente está vendo é fazer a originação de registros.
E outra coisa também é que você consegue comparar algoritmos com outros para poder verificar qual que é melhor, qual que é pior, em quais situações um funciona melhor do que o outro.
A gente já viu, em aulas passadas, o uso da função sort que a linguagem Python oferece para a gente, que realiza, de fato, uma ordenação de uma lista que você passa ali para esta função.
Então, ela vai fazer uma ordenação que pode ser crescente ou decrescente, mas é importante, como eu falei, verificar quais são as possíveis implementações para esta função sort, que daí você pode replicar isso em outras linguagens, você pode criar sua própria função.
Então, a ordenação é bastante utilizada, então, se você tem lá listas telefónicas, dicionários, etc.
, você procurar um telefone numa lista que não está ordenada pelos nomes das pessoas, sistemas de banco de dados, processamento de dados, entre inúmeras outras aplicações.
Então, como eu falei, os algoritmos de originação são ilustrativos, na verdade você vai sempre escolher um melhor na sua aplicação, mas eles são bastante estudados para verificar como a gente resolve problemas computacionais, como a gente consegue lidar com diferentes estruturas de dados, como árvores que eu falei nas aulas passadas, e como desenvolver também algoritmos elegantes, dependendo de determinar os paradigmas, e como analisar e comparar os seus desempenhos.
Então, vamos ver uma definição do que é a ordenação.
Então, a ordenação é organizar uma sequência de elementos de modo que os mesmos estabeleçam uma relação de ordem.
Então, a gente diz que os elementos de ca 1 até ca 1 estarão dispostos de modo que ca 1 seja menor ou igual a ca 2, ca 2 menor ou igual a ca 3 até o último elemento.
De às vezes, pessoal, da menos trabalho fazer uma busca por um elemento, não conjunto que está desordenado do que comparado a você fazer uma ordenação neste conjunto e depois realizar a busca.
Se você fizer uma única busca neste conjunto, acaba sendo de fato mais rápido ou da menos trabalho você fazer isso.
Então, você vai a partir do primeiro elemento, comparar ele com o que você está buscando, se não for você parte por prós, depois por prós, até você encontrar ele ou chegar no final deste conjunto.
Só que, se você fizer várias buscas, você fizer várias chamadas a uma função de busca, aí a coisa pode ficar complicada.
Então, aí vale a pena você ordenar primeiro este conjunto, e essa ordenação pode ser feita somente uma vez.
E depois você consegue fazer a busca usando outros métodos mais eficientes, como a busca binária, entre outras estratégias que podem ser aplicadas.
Então, depende da circunstância de você aplicar ou não uma ordenação dependendo do teu domínio.
Vamos ver, então, uma terminologia, a gente vai realizar a ordenação de registros, cada registro é ordenado por sua chave.
Existem dois tipos de ordenação, a ordenação interna e a externa.
A interna é quando todos registros cabem na memória principal, e a externa é quando você tem um conjunto de dados muito grande, que não cabe na memória principal, e você precisa fazer uma ordenação por blocos.
Então, você faz a ordenação de um bloco, depois faz o bloco seguinte, e assim por diante, depois você faz uma combinação desses blocos que já estão ordenados.
A gente tem também a ideia de ordenação estável, que se você tiver, por exemplo, chaves iguais num conjunto, então, imagina que você tem um conjunto 2, 3, 3, 5, 6, 1, aqui eu vou colocar mais um 7 desse lado, então, imagina que você quer, e mais um 3 aqui também.
Então, imagina que você quer fazer uma ordenação deste conjunto, que vai virar 1, 2, 3, 3, 3, 5, 6 e 7.
O que acontece aqui? Esse 3 aqui tem que ser igual a esse 3, tem que ser esse 3, tem que ser esse.
Então, a ordem dos registros iguais que estão no conjunto desorlinado, vai ser igual a esses registros após a ordenação.
Então, isso é a ordenação estável, e alguns algoritmos realizam isso, eles fazem a ordenação estável, enquanto outros algoritmos realizam uma ordenação instável.
Então, vamos ver o primeiro algoritmo de ordenação, que é o Bobaussort, que é um dos métodos mais conhecidos intuitivos.
A ideia básica dele é essa, a gente vai percorrer o conjunto várias vezes, e a cada iteração a gente vai comparar um elemento com seu sucessor, quer dizer, o elemento na posição I com o elemento da posição I mais um.
Esse o V de forma maior do que o V de I mais um quer dizer que o maior elemento está lá do esquerdo, e o elemento menor está lá direito, e a gente vai realizar a troca entre eles de posição.
Então, vamos ver um exemplo aqui, tem um veturo inicial, que é esse cara que está aqui.
A gente vai começar, então, comparando o primeiro par, que é esse par que está aqui.
Bom, como 25 é menor do que 57, não ocorre nenhuma permutação, nenhuma troca, então a gente passa para o par seguinte, que é esse de com isso.
Nesse caso, o 57 é maior do que o 48, então é necessário realizar uma troca entre eles.
Então, é exatamente o que eu faço aqui, 48 com o 57.
Continuando, eu vou fazer agora a comparação, ou a comparação no par seguinte, que é 57 com o 37.
Como existe uma maior estado lá do esquerdo, eu vou fazer a troca entre eles, então, 37 vem para cá, 57 vem para cá, e passo para a comparação do par seguinte, 57 com o 12.
Também ocorre permutação, o 12 vem para cá, os 57 vem para cá, e aí faço a comparação com o par seguinte, que não ocorre permutação, então 57 permanece 57, 92 permanece lá na posição corretta.
Faço a comparação com entre os par seguinte, 92 com 86, vai ocorre uma permutação, e depois 92 com 33 também fazendo esta permutação.
Então, no final das contas, pessoal, a gente vai ter este vetor aqui final, isso para o passo 1, repare aqui no final deste passo o maior elemento de todo o conjunto, assume a sua posição corretta, que é a última posição do vetor.
Então, a gente vai ter que fazer agora este processo novamente para os elementos anteriores, o N menos 1 elementos anteriores.
E aí, para o passo 2, vamos fazer a mesma coisa, só que agora chegando até o penúltimo elemento, e até chegar ao final do passo 2, o penúltimo elemento que é o maior elemento após 92 também está na sua posição corretta.
Então, a gente vai fazendo isso n vezes, o N menos 1 vezes até que o todo vetor esteja ordenado.
Então, para um vetor de N elementos são necessárias n menos 1 interações, fazer este processo n menos 1 vezes, e a cada ter essa interação, os elementos vão assumindo suas posições corretas, primeiro na última posição, depois na penúltima, e assim por diante até que chega nas duas primeiras.
Aqui, eu tenho uma implementação do BoboSort, na linguagem Python, eu vou deixar como exercícios para vocês implementarem esta função na ideia de vocês, e rodarem com um conjunto de elementos desordenados, e verificar o funcionamento deste algoritmo.
Então, repare aqui este fora, aqui de fora, o for que vai ter os passos de 1 até N menos 1, e aí, esse for de baixo aqui, é o que vai fazer com que você percorra os pares, onde os pares de elementos que vão ser comparados entre si, vai da primeira posição até a penúltima posição.
E se o videojota for maior do que o videojota mais 1, quer dizer, o elemento da esquerda, for maior do que o elemento da direita, é realizada a troca entre esses dois elementos que estão aí.
Tudo bem? Aí, a gente tem um segundo algoritmo, pessoal, que é o IncessionSort, ordinação por inserção.
Qualquer ideia desse algoritmo.
A gente vai ordenar o conjunto inserindo os elementos em um subconjumpo já ordenado.
Então, no Ismo passo, a gente vai inserir esse Ismo elemento na sua posição correta dos elementos anteriores, que vai dizer, até o I menos 1, que já devem estar ordenados.
E para fazer isso, é necessário realocar os elementos, se necessário.
Então, vamos ver um exemplo aqui.
Então, imagina que eu tenho um vetor aqui original, que está desordenado.
E então, o que eu vou fazer? Eu vou primeiro comparar o segundo elemento com o primeiro.
Se esse segundo elemento for maior do que o de trás, a gente não faz nada.
A gente parte por próximo elemento.
Então, a gente vai comparar o 31 com o 30 também.
Não tem que fazer nada.
Eles estão ordenados até esse momento.
Agora, quando chega aqui no elemento 15, ele está desordenado e não está na posição correta.
Então, é necessário realocar os elementos para inserir o elemento 15 na sua posição correta.
Como fazemos isso? A gente armazena esse 15 temporariamente numa variável auxiliar e vai deslocando os elementos anteriores até que esse 15 seja maior do que o elemento que eu estou com.
Então, aqui eu vou colocar o 31 na posição do 15, depois o 30 na posição do 31.
E aí, como 15 não deve ir à esquerda do 10, a gente para e en serio 15 naquela posição aqui, que foi desocupada.
E aí, a gente vai ter essa situação aqui dos elementos 10, 15, 30 e 31, ordenados.
E aí, a gente vai fazendo esse processo até o final do vetor.
Então, por exemplo, aqui a gente vai comparar depois de 50 com 21, depois de 60 com 50.
E aí, quando chega na vez do 5, a gente vai fazer esse mesmo processo, que é armazenar o 5 numa variável auxiliar.
E aí, vai fazer o deslocamento desses elementos.
Então, 60 vai vir para cá, o 50 vai vir para cá, o 31 vai vir para cá, 30, 15, 10.
E aí, como não tem mais nada para lá, a gente encerre o 5 naquela posição.
E aí, continue esse processo, comparando aí o 22 com 60 e assim por diante.
Tá legal? Aqui, eu tenho o passo a passo para um outro vetor, que vai fazer também a organização.
Vou deixar para vocês estudarem isso daí por conta.
Tá legal.
E aqui, eu também tenho a implementação do insertion, que eu vou deixar também como tarefim para vocês rodarem ele na ideia de vocês.
E verificar também o funcionamento.
Então, olha só, eu vou ter esse for que para eu percorrer o vetor da posição 1 até o tamanho deste vetor.
Desta lista, né? O X vai receber o elemento que eu quero, inserir no meu na minha lista.
Então, repare que esse range ele começa com 1.
Então, o elemento na posição 0 fica ali, como se ele já tivesse ordenado.
Então, o X recebe o segundo elemento, tá? O segundo elemento.
E o J é o que eu vou fazer a comparação com o X.
Então, enquanto esse J for maior do que 0 e o X for menor do que o V de J, eu vou precisar fazer esse deslocamento.
Então, é onde eu vou fazer o V de J mais 1 recebe o V de J, né? Decremento o J e vou fazendo esse processo enquanto esse I do R.
Após esse I do R, terminar, eu faço a inserção aqui embaixo do X na sua posição correta.
Tá? Então, pessoal, essa foi a nossa primeira videoaula sobre algoritmos de orinação.
A gente não entrou em muitos detalhes sobre esses algoritmos como o custo computacional ou detalhes de implementação, porque realmente a ideia desta videoaula é só apresentar para vocês uma visão mais geral dos funcionamentos desses algoritmos, pessoal da computação, da engenharia da computação, provavelmente vai aprender melhor sobre esses algoritmos, quando vocês aprenderem a complexidade de algoritmos e outros assuntos que são mais avançados, mas a gente vai continuar vendo alguns desses algoritmos ainda nas próximas videoaulas.
Então, eu aguardo vocês e obrigado pela atenção.
Até lá!