Estruturas de Ordenação e Busca: Guia Completo

Estruturas ordenação e busca SENAI DEPARTAMENTO REGIONAL DE SANTA CATARINA MANTENEDORA Fabrizio Machado Pereira Diretor Regional do SENAISC e Diretor de Educação e Tecnologia da FIESC Adriana Paula Cassol Gerente Executiva de Educação Ana Luisa Mulbert Cleunisse Aparecida Rauen de Luca Canto Gestão da Educação Superior CENTRO DE EDUCAÇÃO DIGITAL Fabiano Bachmann Gerente do Centro de Educação Digital CDI Gisele Umbelino Coordenadora de Desenvolvimento de Recursos Digitais CDI Hellen Cristine Geremia Líder de Projeto Nayara Pereira Gonçalves Analista de Educação Digital João Carlos Testi Ferreira Autoria Marlow Rodrigo Becker Dickel Revisor Técnico Taynara Rúbia Campos Design Educacional Heliziane Babosa Design Gráfico Davi Leon Dias Ilustrações e Tratamento de Imagens MANTIDA Barbara Yadira Mellado Perez Proreitora de Ensino Pesquisa e Extensão do Centro Universitário Fabricio Roulin Bittencout Diretor Faculdade Senai Felipe Moisés da Silva Hintz Programação Web André Gonçalves de Freitas Isac Diniz Pedro Borrionuevo Nascimento Produção Audiovisual Michele Antunes Corrêa Stephanie Johansen Longo Basso Projeto Educacional Heliziane Barbosa Janaina da Silveira Vieira Juliana Tonietto Projeto Webgráfico Airton Júlio Reiter Revisão ortográfica gramatical e normalização MSL Traduções Revisão ortográfica gramatical e normalização IStock Photo Banco de Imagens SUMÁRIO Estruturas ordenação e busca1 Para Iniciar 5 Desafio 7 Estrutura para armazenamento e recuperação de dados de cadastro de cliente 9 Agenda Desafio Estrutura para armazenamento e recuperação de dados de cadastro de cliente 13 Estudo e Prática I Ordenação 15 Ebook I 15 Ordenação não recursiva 17 Ebook II 31 Ordenação recursiva 33 Videoflix 53 Insertion sort 53 Recursividade 53 Merge sort 53 Infocast 55 Bubble sort 57 Selection sort 59 Quero saber 61 Resumindo 63 Estudo e Prática II Busca e estruturas especiais 65 Ebook I 65 Algoritmos de busca 67 Ebook II 83 Tabela hash árvores e arquivos 85 Videoflix 107 Tabela hash de contatos 107 Operações básicas da árvore sem o remover 107 Remover da árvore e busca 107 Infocast 109 Busca fullscan versus busca com sentinela 111 Busca com sentinela versus busca binária 113 Quero saber 117 Resumindo 121 Para Concluir 123 5 Olá Tudo bem Aqui você vai conhecer alguns dos mais usados tratamentos sobre dados que envolvem a classificação e a pesquisa Afinal de nada adianta termos estruturas de dados que não permitam uma pesquisa eficiente Assim a classificação é um elemento chave para potencializar ainda mais a pesquisa Em todas as atividades em que as aplicações são empregadas estão envolvidas as estruturas de dados e por consequência também é preciso classificar e buscar esses dados Pois não se guarda dados simplesmente por guardar e sim porque eles são necessários para nossas tarefas A forma de busca nem sempre é a mesma já que depende das características da pesquisa dos dados a serem pesquisados e da infraestrutura sobre a qual os dados estão armazenados Você vai aprender também sobre outras estruturas que possuem características que as tornam muito especiais Essas estruturas são muito usadas para bancos de dados por exemplo a tabela hash e a árvore duas estruturas que possuem características que otimizam seu processo de inserção e busca e as tornam ideais para trabalhos com índices É muito rara uma aplicação que não faça uso de banco de dados Além disso quando usamos bancos de dados geralmente trabalhamos com uma quantidade significativa de dados algumas vezes extremamente grande Nesse sentido o banco de dados nos fornece meios de pesquisa otimizados sendo um desses meios os índices Assim como quando olhamos o sumário no início de um livro com objetivo de achar mais rápido algo no livro os índices servem para a mesma coisa direcionar rapidamente para o dado desejado Aproveite essa oportunidade de aprendizado para construir cada vez mais seus conhecimentos Bons estudos PARA INICIAR 7 Confira a seguir uma situação prática relacionada aos conteúdos que você estudará a partir de agora Essa é uma importante etapa de seu processo avaliativo Então dediquese ao máximo e busque em sua trajetória de estudos fundamentar os resultados esperados no desafio que está proposto a seguir Aproveite pois essa é uma grande oportunidade de praticar novos conhecimentos Desafio Estrutura para armazenamento e recuperação de dados de cadastro de cliente Aqui você vai conhecer e trabalhar em um exemplo real de criação de biblioteca para um objetivo específico situação comum na construção de aplicações profissionais Esta atividade vai demandar que você avalie o problema e identifique a melhor solução dentro dos requisitos estipulados Vamos lá Lembrese esteja atento a todos os detalhes indicados no Desafio e Agenda pois tratase de uma parte importante de seu processo avaliativo nestes estudos DESAFIO 9 Comunicação Oral e Escrita 9 Estrutura para armazenamento e recuperação de dados de cadastro de cliente Uma organização está construindo uma aplicação que vai manipular uma estrutura de dados de clientes com o objetivo de criar ações de marketing orientadas a características desses clientes O cliente é uma estrutura com as seguintes informações Nome do Cliente uma string de 40 caracteres Bairro de moradia do cliente uma string de 40 caracteres Quantidade de pessoas na sua residência inteiro Tem crianças menores de 5 anos Booleano Renda familiar bruta double 10 Comunicação Oral e Escrita 10 A estrutura deve armazenar os dados de várias formas tendo como chaves nome bairro quantidade de pessoas na sua residência ter crianças menores de 5 anos e renda familiar bruta A recuperação prevista é da seguinte forma Busca pelo nome recuperação de lista Busca por bairro recuperação de lista Busca por pessoas na sua residência recuperação de lista Busca por crianças abaixo de 5 anos recuperação de lista Busca por renda familiar recuperação de lista por faixa As quantidades de pessoas na residência a serem inseridas e recuperadas são 1 2 3 4 5 sendo que 5 representa cinco ou mais Já as faixas de renda em R a serem inseridas e recuperadas são até 200000 de 200000 a 300000 de 300001 a 500000 acima de 500000 11 Comunicação Oral e Escrita 11 A inserção e a recuperação dos dados devem ser otimizadas conforme as características citadas Não há limite de clientes a cadastrar A função de recuperação deve ter o seguinte critério 1 para clientes pelo nome 2 para clientes pelo bairro 3 para clientes por quantidade de pessoas na residência 4 para clientes com crianças abaixo de 5 anos 5 para clientes por faixa de renda A função será assim Lista recuperaclienteEstrutura estrutura int criterio int complemento char busca onde estrutura é a estrutura que mantém os clientes critério conforme apresentado complemento será 0 para quando a busca é textual nome ou bairro e caso contrário o valor conforme o critério seja ele a quantidade de pessoas se tem crianças ou faixa de renda busca é a string usada na busca textual se não for busca textual é NULL Comunicação Oral e Escrita 12 12 A construção dessa base de dados precisa ser em linguagem C utilizando tabela hash Ao final de sua elaboração você deve ter os seguintes arquivos O cabeçalho do TAD representando o cliente denominado clienteh A implementação do TAD representando o cliente denominado clientec e o compilado clienteo essa é a implementação da estrutura de cliente e sua manipulação apresentada nos requisitos O cabeçalho do TAD representando o nodo denominado nodoh A implementação do TAD representando o nodo denominado nodoc e o compilado nodoo essa é a implementação do nodo e sua manipulação O cabeçalho do TAD representando a lista denominada listah A implementação do TAD representando a lista denominada listac e o compilado listao essa é a implementação da lista encadeada e sua manipulação O cabeçalho do TAD representando a estrutura hash denominada estruturah A implementação do TAD representando a estrutura hash com o código fonte denominada estruturac e o compilado estruturao estrutura com tabela hash que permita as manipulações citadas nos requisitos Para seus testes de validação da sua implementação está sendo fornecido um exemplo de código com uma função main que pode ser usada para verificar seu funcionamento teste2c AGENDA Estrutura para armazenamento e recuperação de dados de cadastro de cliente Resultado esperado Arquivo compactado em zip com o nome do aluno contendo os arquivos produzidos por ele estruturah estruturac estruturao clienteh clientec clienteo nodoh nodoc nodoo listah listac listao Desenvolvimento Individual Confirmar com o professortutor Critérios de avaliação Desenvolver um código funcional apresentando os dados corretos no teste original proposto teste2c Fazer a correção na construção do TAD Cliente com relação aos requisitos Executar a correção da lista com relação à necessidade definida nos requisitos Apresentar funções de hash adequadas aos tipos de entrada Fazer a correção da implementação da tabela hash Forma de entrega Arquivo compactado em zip com nome do aluno contendo os arquivos produzidos por ele a ser entregue em ferramenta do Ambiente Virtual de Aprendizagem AVA 13 15 Trabalhar com grandes quantidades de dados é um desafio A busca é uma atividade muito frequente que é facilitada por algoritmos especializados em organizar os dados e realizar buscas em dados agrupados É o que você vai aprender neste bloco ESTUDO E PRÁTICA I ORDENAÇÃO Aqui você vai aprender sobre a ordenação não recursiva com algoritmos que não usam recursividade pois realizam seu processo por meio de laços Além disso vai conhecer mais sobre recursividade e dois dos mais populares algoritmos de ordenação que usam recursividade o quicksort e o mergesort que serão o tema principal Aproveite e explore ao máximo esses assuntos Nesta leitura você vai conhecer algumas das funções mais populares de ordenação Assim vai aprender seus conceitos formas de operação características de desempenho bem como poderá analisar cada uma delas nos aspectos de contexto de uso infraestrutura e consumo de recursos Boa leitura Ebook Ordenação não recursiva Ordenação não recursiva 18 Uma das estratégias para facilitar o acesso aos dados é classificálos ou ordenálos Cada estrutura conforme é implementada se beneficia de uma forma de ordenação ou outra Dessa forma esse estudo de alguns algoritmos de ordenação visa compreender seus pontos fortes e fracos as estruturas em que melhor se aplicam além de entender sua complexidade de forma que você possa ser capaz de escolher os melhores algoritmos de ordenação conforme a característica dos dados ou da implementação da estrutura desejada Ascencio e Araújo 2010 p 2 citam que há situações em que é necessário ordenar dados ou seja para que se possa usar dados é necessário organizálos de alguma forma que seja adequada ao problema que se deseja resolver As autoras complementam que essa é a razão da existência dos algoritmos de ordenação Tipicamente classificamos os dados conforme nossa necessidade Loudon 2000 p 323 nos diz que classificar quer dizer arranjar um grupo de elementos em uma ordem predeterminada No diaadia a vantagem de manipular um conjunto de dados previamente classificado é óbvia Imagine por exemplo o quão difícil seria achar o telefone de alguém ou de algum lugar em uma lista que não estivesse ordenada Ordenação não recursiva 19 ORDENAÇÃO Algoritmos de classificação são muito estudados e temos muitas formas de classificar um conjunto de dados Algumas formas são mais adequadas para determinado tipo de estrutura outras mais indicadas para a forma como os dados estão espalhados Segundo Feofiloff 2009 p 59 o problema de ordenação é um verdadeiro laboratório de projeto de algoritmos Alguns algoritmos usam laços de comparação que passam por todos os dados diversas vezes Já em outros as comparações ocorrem em uma direção deixando os dados na direção oposta ordenados Um recurso também bastante usado é a recursão que deixa o código bem menor aproveitandose do empilhamento de execução Moraes 2001 afirma que se pode classificar dados em ordem crescente ou decrescente conforme o interesse do problema Além disso precisase considerar a quantidade de dados pois se o total dos dados não couber na memória pode ser que a ordenação precise ser externa com o apoio de um meio de armazenamento Se a memória for suficiente para os dados podese usar a ordenação interna Aqui a ênfase será na ordenação interna mas um algoritmo de ordenação externa utilizado para auxiliar no entendimento em estudos será comentado Os dados que serão classificados podem não ser únicos como um número inteiro por exemplo Assim podese ordenar estruturas que contenham tipos heterogêneos registro com vários campos Ordenação não recursiva 20 A ordenação nesse caso deve estabelecer a chave que será usada Por exemplo pense em um registro de um aluno nesse registro há o número da matrícula o nome do aluno e a idade do aluno para ordenar é necessário definir qual a chave de ordenação esta poderia ser a matrícula assim ao ordenar a matrícula é que definirá em que posição o registro todo ficará Com relação aos algoritmos cada um se vale de características do tipo de estrutura em que se encontram os dados ou da forma como os dados estão dispersos Quando se tem uma lista baseada em vetor a inserção de um elemento em uma posição diferente do fim implica que os dados precisarão ser deslocados para abrir espaço para o novo elemento que será inserido Já em uma lista dinâmica a inserção de um elemento em qualquer posição se dá pelo redirecionamento dos ponteiros dos nós que serão seus vizinhos Notase que uma inserção que não seja no final em uma lista dinâmica é bem menos custosa do que em um array Outro aspecto importante que precisa ser considerado na criação de bons algoritmos envolve a dispersão dos dados Quando se tem dados muito dispersos a definição de um processo mais sistemático pode implicar em um menor número de comparações visto que teremos que comparar todos os elementos entre todos Uma forma mais sistematizada permite que essa quantidade de comparações possa ser reduzida Por outro lado quando os dados estão pouco dispersos um processo mais elaborado pode ser responsável por aumentar o número de comparações e consequentemente tornar o algoritmo mais caro Como esses dois fatores a estrutura de suporte dos dados e a sua dispersão impactam diretamente na qualidade do algoritmo é preciso considerar esses aspectos ao escolher o melhor algoritmo para resolver o problema desejado Atenção Ordenação não recursiva 21 A partir daqui você vai conhecer alguns desses algoritmos bem como suas vantagens e desvantagens de uso ALGORITMOS DE ORDENAÇÃO Uma possível primeira forma de agrupar os algoritmos pode ser separandoos em recursivos e não recursivos Neste texto serão tratados os não recursivos Bubble sort Um dos algoritmos mais simples é o bubble sort que ordena por permutação Esse algoritmo compara os vizinhos e os reposiciona enquanto se deslocam da esquerda para a direita 1º Cada elemento é comparado com o próximo 2º Se o elemento estiver fora de ordem é feita uma troca 3º Esses passos são realizados até que trocas não sejam mais necessárias Ordenação não recursiva 22 Moraes 2001 descreve o algoritmo com os seguintes passos 1 4 2 5 8 1 2 4 5 8 1 2 4 5 8 1 4 2 5 8 1 2 4 5 8 5 1 4 2 8 Troca Troca Troca Sem troca 1 4 2 5 8 1 4 2 5 8 1 5 4 2 8 1 4 5 2 8 1 4 2 5 8 Troca Sem troca Sem troca Sem troca Sem troca 1 2 4 5 8 1 2 4 5 8 1 4 2 5 8 1 2 4 5 8 Sem troca Sem troca Sem troca Ordenação do Bubble Sort Primeiro passo Segundo passo Terceiro passo Figura 1 Os passos da ordenação do bubble sort Fonte Adaptado de w3resource 2023 Na construção do código usamos uma variável trocou que inicia como falsa Se durante a navegação entre os elementos houver uma troca a variável é classificada como verdadeira Assim ao chegar no final da estrutura depois de realizar todas as comparações é verificado se a variável trocou é verdadeira ou falsa Se for falsa a estrutura está ordenada se não o processo é reiniciado voltando a variável trocou para falsa Implemente o algoritmo bubble sort para ordenar um array de inteiros e uma lista encadeada de inteiros Compare os códigos e identifique qual é o mais complexo Avalie seu código e identifique o que é necessário para transformar esse código de ordenação crescente em decrescente Mão na massa Ordenação não recursiva 23 Análise Todas as repetições são realizadas sobre toda a estrutura Desse modo no melhor dos casos seria preciso ler todos os elementos uma vez Se a estrutura estivesse ordenada não aconteceriam trocas e o algoritmo encerraria resultando em n comparações Por outro lado esse processo pode se repetir n vezes conforme o embaralhamento dos elementos na estrutura Assim a análise de pior caso é On2 Outro elemento de análise importante é o custo de manipular os dados durante o processo A leitura é sequencial o que é simples em arrays e em listas dinâmicas Quando há trocas o que se tem é só a substituição de um pelo outro nesse caso em um array não há necessidade de deslocamentos para abrir espaço para o elemento o que leva a considerar esse algoritmo adequado tanto para listas dinâmicas quanto para arrays Selection sort Esse algoritmo usa a seleção como modo de ordenação Assim iniciase em uma extremidade buscando o elemento que deveria estar naquela posição Ao achálo os outros elementos são trocados da posição atual com o respectivo elemento identificado como sendo daquela posição Isso se repete até a posição final ser alcançada Ordenação não recursiva 24 Backes 2016 descreve que esse algoritmo divide o array em duas partes uma parte ordenada que fica à esquerda do elemento analisado e a parte que ainda não foi ordenada à direita do elemento Para cada elemento do array a partir do primeiro o algoritmo procura na parte não ordenada à direita o menor valor ordenação crescente e troca os dois valores de lugar Depois o algoritmo avança para a próxima posição repetindo o processo até que todo o array esteja ordenado 29 72 98 13 87 66 52 51 36 Troca Ordenação do Selection Sort 13 72 98 29 87 66 52 51 36 Troca 13 29 98 72 87 66 52 51 36 Troca 13 29 36 72 87 66 52 51 98 Troca 13 29 36 51 87 66 52 72 98 Troca 13 29 36 51 52 66 87 72 98 Sem troca Sem troca 13 29 36 51 52 66 87 72 98 Troca 13 29 36 51 52 66 72 87 98 13 29 36 51 52 66 72 87 98 13 é a menor 29 é a menor 36 é a menor 51 é a menor 52 é a menor 66 é a menor sem troca 72 é a menor 87 é a menor sem troca Ordenação completada Figura 2 Os passos da ordenação do selection sort Fonte Adaptado de w3resource 2022b Ordenação não recursiva 25 Implemente o algoritmo selection sort para ordenar um array de inteiros e para ordenar uma lista encadeada de inteiros Compare os códigos e identifique qual é o mais complexo Avalie seu código e identifique o que é necessário para transformar esse código de ordenação crescente em decrescente Mão na massa Análise A complexidade desse algoritmo é constante On2 independentemente de os dados estarem mais ou menos dispersos pois se tem dois laços um dentro do outro navegando pelos elementos e a condição de saída é quando o laço externo chegar ao final Com relação à manipulação de dados esse algoritmo troca os elementos de posição o que implica que não é necessário realizar deslocamentos isso torna esse algoritmo adequado tanto para arrays quanto para listas encadeadas Backes 2016 p 49 afirma que apesar de possuírem a mesma complexidade no caso médio na prática o selection sort quase sempre supera o desempenho do bubble sort pois envolve um número menor de comparações O quase sempre a que o autor se refere são os casos em que a lista já esteja ordenada ou pouco desordenada condição melhor para o bubblesort Nesse sentido o algoritmo bubble sort pode ser mais eficiente se os dados estiverem pouco dispersos Se os dados estiverem muito dispersos este algoritmo tem a vantagem de que o laço interno só percorre a parte não ordenada ficando com menos elementos a comparar a cada iteração do laço externo Ordenação não recursiva 26 Insertion sort O funcionamento desse algoritmo baseiase na inserção Assemelhase a ordenação de cartas de baralho na mão do jogador em que ele vai puxando uma carta e a insere na posição correta Backes 2016 descreve que esse algoritmo percorre um array e para cada posição X o valor é verificado se está na posição correta Isso é feito do começo do array a posição X movimentandose para uma posição à frente dos valores que são maiores do que o valor da posição X Desse modo há uma posição livre para inserir o valor da posição X em seu devido lugar Ordenação não recursiva 27 85 12 59 45 72 51 Ordenação do Insertion Sort 85 59 45 72 51 12 85 59 45 72 51 12 85 45 72 51 12 59 85 45 72 51 12 59 85 72 51 12 59 85 72 51 85 é o primeiro item de uma lista ordenada 8512 trocao para a direita Insere 12 no lugar 8545 trocao para a direita 5945 trocao para a direita 8559 trocao para a direita 1259 então insere 59 no lugar 12 45 59 85 72 51 12 45 59 85 51 12 45 59 72 85 51 12 45 59 72 85 12 45 59 72 85 12 45 59 72 85 12 45 51 59 72 85 1245 então insere 45 no lugar 8572 trocao para a direita 5972 então insere 72 no lugar 5951 trocao para a direita 4551 então insere 51 no lugar 8551 trocao para a direita 7251 trocao para a direita Figura 3 Os passos da ordenação do insertion sort Fonte Adaptado de w3resource 2022c Notase que a posição atual vai avançando para a direita e na medida em que avança o elemento atual retorna comparando com os anteriores para identificar sua posição Isso otimiza muito o processo reduzindo significativamente o número de comparações Implemente o algoritmo insertion sort para ordenar um array de inteiros e para ordenar uma lista encadeada de inteiros Compare os códigos e identifique qual é o mais complexo Avalie seu código e identifique o que é necessário para transformar esse código de ordenação crescente em decrescente Mão na massa Análise A complexidade desse algoritmo é On2 pois tem dois laços à semelhança dos demais algoritmos vistos até aqui A maior diferença no entanto é que o laço externo não é ponto inicial de comparação mas a posição que é avaliada para ser inserida na posição correta daquela posição para o início Isso diminui significativamente o número de comparações Um fator que precisa ser considerado é que se usar um array como infraestrutura para os dados quando se recua para identificar a sua posição será necessário deslocar os elementos para abrir a posição de inserção Em uma lista encadeada esse deslocamento não é necessário o que implica que esse método de ordenação acaba sendo beneficiado com esse tipo de estrutura Backes 2016 destaca a característica desse algoritmo que na prática é mais eficiente que a maioria dos algoritmos de ordem quadrática como os que você viu até aqui Assim tratase de um dos algoritmos mais rápidos de ordenação para conjuntos pequenos de dados até mesmo em relação ao algoritmo recursivo que você irá conhecer mais à frente chamado quick sort Nos algoritmos sem recursão vistos aqui a mesma complexidade de pior caso On2 foi observada Apesar de ter a mesma complexidade de pior caso não se pode dizer que o desempenho deles seja igual ou sequer parecido Desse modo fica clara a necessidade de se conhecer mais sobre a dispersão dos dados e de entender qual estrutura suporta os dados lista estática ou lista dinâmica A implementação desses algoritmos é simples não sendo esse então um critério de escolha de uso Com o estudo desses algoritmos já se pode ter uma boa noção sobre meios de ordenação e critérios de escolha REFERÊNCIAS ASCENCIO A F G ARAÚJO G S de Estruturas de dados algoritmos análise da complexidade e implementações em JAVA e CC São Paulo Pearson Prentice Hall 2010 BACKES A R Estrutura de dados descomplicada em linguagem C Rio de Janeiro Elsevier 2016 FEOFILOFF P Algoritmos em linguagem C Rio de Janeiro Elsevier 2009 LOUDON K Dominando Algoritmos com C Rio de Janeiro Editora Ciência Moderna 2000 MORAES C R Estruturas de dados e algoritmos uma abordagem didática São Paulo Berkeley Brasil 2001 W3RESOURCE C Sharp Searching and Sorting Algorithm Exercises Bubble sort W3resource 19 ago 2022a Disponível em httpswwww3resourcecomcsharp exercisessearchingandsortingalgorithmsearchingandsortingalgorithm exercise3php Acesso em 3 jan 2023 W3RESOURCE Python Selection sort Python Search and Sorting Exercise5 with Solution W3resource 19 ago 2022b Disponível em httpswwww3resource compythonexercisesdatastructuresandalgorithmspythonsearchand sortingexercise5php Acesso em 3 jan 2023 W3RESOURCE Python Selection sort Python Search and Sorting Exercise6 with Solution W3resource 19 ago 2022c Disponível em httpswwww3resource compythonexercisesdatastructuresandalgorithmspythonsearchand sortingexercise6php Acesso em 3 jan 2023 SENAI 31 Aqui você vai conhecer o funcionamento da recursividade e sua importância na programação Observe como os algoritmos podem se beneficiar da recursão vendo dois dos mais populares algoritmos de ordenação recursiva Bons estudos Ebook Ordenação recursiva Ordenação recursiva 34 Muitos problemas difíceis de resolver podem ser simplificados dividindoos em coisas menores e mais fáceis de serem resolvidas A ordenação se encaixa nesse tipo de problema e alguns dos algoritmos de ordenação mais famosos usam recursão A recursão é uma abordagem de programação para simplificar e tornar o código mais reduzido Aqui você vai aprender o que são e como implementar algoritmos recursivos suas vantagens e desvantagens e entender como analisar o desempenho desses algoritmos Para tal serão apresentados dois algoritmos os mais populares de ordenação que fazem uso da recursão Um deles inclusive é usado para ordenação externa como será visto RECURSÃO Loudon 2000 p29 nos diz que recursão é um princípio potente que permite que algo seja definido a partir de segmentos menores em relação a um todo A recursão não é normalmente a primeira forma de solução de um problema é mais comum pensar em soluções iterativas A alternativa pela recursividade deve ser avaliada e para isso você vai entender como pensar em um código recursivo para resolver um problema Ordenação recursiva 35 Koffman e Wolfgang 2016 definem o algoritmo recursivo geral como 1º Se o problema pode ser resolvido com o valor atual n então está resolvido 2º Se não o algoritmo é aplicado recursivamente quantas vezes forem necessárias com valores cada vez menores de n até alcançar o item 1 Para construir um algoritmo recursivo é necessário garantir algumas condições Koffman e Wolfgang 2016 descrevem essas questões como 1 Deve haver pelo menos um caso o caso base para um valor pequeno de n que pode ser resolvido diretamente 2 Um problema de tamanho n pode ser dividido em versões menores do mesmo problema caso recursivo Com isso para criar um algoritmo recursivo devese Identificar o caso base e resolvêlo Definir uma solução que divida o problema em versões menores dele mesmo de forma a em algum momento alcançar o caso base A combinação dessa solução deve resolver o problema corretamente Assim notase que um algoritmo recursivo chama a ele mesmo como se fosse um laço e deve ter uma condição de saída garantida do contrário esse laço se repetirá até consumir toda a memória travando a máquina Loudon 2000 apresenta a recursão de duas formas a recursão básica e a recursão final tail recursion Aqui serão utilizados esses mesmos para explicar a recursão Conhecer essas duas formas de recursão ajuda a avaliar qual será o desempenho do algoritmo Antes no entanto você vai conhecer dois algoritmos iterativos para depois começar a explicar as duas formas de recursão Ordenação recursiva 36 ALGORITMOS ITERATIVOS Existe uma solução algorítmica para dois problemas da matemática fatorial e maior divisor comum MDC A fatorial é muito usada em análise combinatória e seu operador de fatorial é o sinal de exclamação Por exemplo para calcular o fatorial de 5 escrevese 5 Assim observe algumas definições de fatorial 0 1 1 1 2 2 x 1 2 3 3 x 2 x 1 6 Generalizando n n x n1 Uma solução simples e direta para resolver o fatorial é por meio do uso de um laço Note o código a seguir Ordenação recursiva 37 int fatorialint n ifn 0 return 1 ifn 0 return 1 int i res 1 for i n i 0 i res i return res Para simplificar o problema é possível retornar 1 quando a entrada for inválida já que não existe fatorial de número negativo As demais condições são para atender às definições de fatorial Então notase que o algoritmo para cálculo do fatorial de forma iterativa é bem simples Já o MDC é o processo de identificar qual é o maior divisor comum entre um conjunto de números Em matemática é utilizado em vários contextos principalmente nas operações com frações Ordenação recursiva 38 Algumas regras podem ser identificadas para achar o MDC quando o menor dos valores é divisor dos maiores o menor é o maior divisor comum por exemplo 7 e 35 em que 7 é o MDC Mas quando os números são primos entre si ou seja quando não há divisores comuns por exemplo 17 e 11 o único divisor comum é o número 1 Se o menor não for divisor do maior é preciso fazer a fatoração Para saber o maior divisor comum entre 20 e 24 por exemplo fazse 20 24 2 10 12 2 5 6 2 5 3 3 5 1 5 1 1 O MDC é 2 2 ou seja 4 No lado direito são os números que são usados como divisores Assim a divisão começa pelos menores números 2 3 que são os valores da esquerda Esse processo continua enquanto houver um número que ainda seja divisível por ele Quando não mais houver vaise para o próximo número Quando só restarem valores 1 do lado esquerdo avaliase qual é o MDC Para isso usam se os divisores que foram aplicados nos números dos quais se quer descobrir o maior divisor em vermelho multiplicandoos Assim o maior divisor comum é 2 multiplicado por 2 resultando em 4 Uma solução para esse problema usando um laço é apresentado a seguir Considere que i deve ser maior que j int mdcint i int j ifi j 0 return j int resto i j int divisor resto while1 resto j divisor ifresto 0 return divisor divisor resto return divisor É possível resolver essas questões matemáticas de forma relativamente simples usando laços Agora você vai usar esses problemas para entender os tipos de recursão Ordenação recursiva 40 RECURSÃO BÁSICA O objetivo da recursividade é fazer a função chamar a própria função para achar a solução em que a cada chamada o problema é reduzido No caso do fatorial fazemos int fatorialint n ifn 0 return 1 ifn 1 n 0 return 1 return n fatorialn 1 A solução iterativa é pequena mas essa consegue ser ainda menor Observe que é usada a definição do fatorial para fazer este código Se n for 0 ou 1 o fatorial é 1 Se for maior que 1 então n n n1 Observe que a cada chamada o valor de n é menor bem como a saída garantida se n for 1 ou zero e também o caso de erro para n 0 Ao calcular o fatorial de 4 o processo realizado pela máquina será fatorial4 4 x fatorial3 fatorial3 3 x fatorial2 fatorial2 2 x fatorial1 fatorial1 1 fatorial2 2 x 1 fatorial3 3 x 2 fatorial4 4 x 6 24 Ordenação recursiva 41 Notase então que o processo de uma recursividade básica é chamar a função novamente deixando o processo anterior suspenso enquanto se aguarda o resultado da nova chamada da função Isso ocorre sucessivamente até se chegar a um resultado na nova chamada Depois o processo retorna substituindo os resultados até se chegar ao resultado final Com essa estratégia de solução muita memória é usada pois todas as operações suspensas estão empilhadas na memória não podendo ser liberadas pois fazem parte da chamada de outras funções que ainda não se completaram RECURSÃO FINAL Observe o código a seguir para esta demonstração de recursividade para calcular o MDC int mdcint i int j if i j 0 return j else return mdcj i j Ordenação recursiva 42 Neste caso o código ficou muito menor assim menos variáveis são necessárias Um ponto importante é que a função não depende da nova chamada então ela pode ser liberada e se não há empilhamento menos memória é consumida Outra questão é o tempo de execução já que a função é realizada uma vez não precisa retornar devolvendo valores Nem sempre é possível trabalhar com recursividade final mas ela é muito mais eficiente do que a recursividade básica Podese pensar em uma solução para o fatorial usando recursividade final mas é preciso passar 2 parâmetros int fatorialrfint n int res ifn 0 return 1 ifn 0 n 1 return res return fatorialrfn 1 n res Observe que agora os retornos estão prontos quando a função chegar em uma condição de saída assim não há necessidade de retornar para devolver os resultados para operações suspensas A chamada da função pelo usuário no entanto não é tão intuitiva e precisa ser feita da seguinte forma fatorialrf5 1 Ordenação recursiva 43 ORDENAÇÃO RECURSIVA Uma vez que você já aprendeu sobre a recursividade acompanhe alguns algoritmos de ordenação recursiva como o quick sort e o merge sort Quick sort O criador desse algoritmo foi C A Hoare em 1962 sendo considerado o método mais rápido dos apresentados até aqui MORAES 2001 Isso faz dele o preferido para soluções de classificação Loudon 2000 argumenta que mesmo esse algoritmo sendo considerado como um dos melhores para uso geral na análise de pior caso ele se mostra pior do que o algoritmo por inserção insertion sort A possibilidade do pior caso no entanto pode ser minimizada Devido à característica desse algoritmo é dito que ele usa como estratégia dividir para conquistar Dado um conjunto de dados a ideia é estabelecer um valor médio arbitrado denominado pivô e formar dois conjuntos de dados um com os valores maiores e outro como os valores menores que o pivô Isso é aplicado recursivamente Moraes 2001 destaca que o ponto mais crítico é a decisão de como fazer o particionamento Backes 2016 descreve que o algoritmo quick sort rearranja os valores de array de modo que os valores menores que o pivô fiquem na parte esquerda enquanto os valores maiores ficam na parte direita Assim considere um array de tamanho N com o pivô na posição X O processo vai criar duas partições 0X 1 e X 1 N 1 Depois o algoritmo é aplicado recursivamente a cada partição e o processo se repete até que cada partição fique com um único elemento Ordenação recursiva 44 10 15 1 2 6 12 5 7 1 1 2 5 6 10 12 15 2 6 5 7 12 15 10 Pivô Pivô Pivô Figura 4 Processo do quick sort Fonte Adaptado de Megan 2020 Veja o código para o quick sort proposto por Backes 2016 int particionaint V int inicio int final int esq dir pivo aux esq inicio dir final pivo Vinicio whileesq dir whileVesq pivo esq whileVdir pivo dir ifesq dir aux Vesq Vesq Vdir Vdir aux Ordenação recursiva 45 Vinicio Vdir Vdir pivo return dir void quicksortint V int inicio int fim int pivo iffim inicio pivo particionaV inicio fim quicksortV inicio pivo 1 quicksortV pivo 1 fim O código é dividido em duas funções uma responsável por particionar o vetor e outra pela ordenação A função recursiva é a quick sort e a particionada é uma função auxiliar Observe que essa função é recursiva final pois o vetor está sempre mais ordenado a cada passo da execução não necessitando de esperas e empilhamento Backes 2016 destaca a complexidade desse algoritmo sendo a complexidade de pior caso ON2 e o melhor caso e caso médio ON log N Isso demonstra que esse algoritmo não é sempre melhor que os demais apresentados Por exemplo se ele tentar ordenar um vetor previamente ordenado ele terá um desempenho pior do que o bubble sort que terá uma complexidade ON A forma de manipulação dos elementos também é outro ponto de destaque mostrando que ele é mais indicado para arrays Ordenação recursiva 46 Merge sort Esse é outro algoritmo que usa como estratégia dividir para conquistar Uma diferença dele para o quick sort é que o quick sort faz a ordenação por troca e o merge sort faz por intercalação Backes 2016 descreve que esse algoritmo divide o array recursivamente em duas partes até que cada posição seja considerada um array de um único elemento Depois o algoritmo combina os dois arrays de forma a obter um único array maior e ordenado Essa combinação é feita intercalando os elementos de acordo com o sentido da ordenação que pode ser crescente ou decrescente Esse processo se repete até que exista apenas um array Ordenação recursiva 47 1 2 3 7 13 12 17 15 14 9 8 5 6 10 16 18 19 20 11 4 38 27 43 3 9 82 10 3 9 10 27 38 43 82 38 38 27 43 3 9 82 10 38 27 43 3 9 82 10 27 38 3 43 9 82 10 3 27 38 43 9 10 82 27 43 3 9 82 10 Esses números indicam a ordem dos passos do processo Figura 5 Processo do merge sort Fonte Adaptado de Batista 2021 O algoritmo para o merge sort proposto por Backes 2016 é o seguinte void mergeint V int inicio int meio int fim int temp p1 p2 tamanho i j k int fim1 0 fim2 0 tamanho fim inicio 1 p1 inicio p2 meio 1 temp int malloctamanho sizeofint if temp NULL fori 0 i tamanho i Ordenação recursiva 48 iffim1 fim2 ifVp1 Vp2 tempi Vp1 else tempi Vp2 ifp1 meio fim1 1 ifp2 fim fim2 1 else iffim1 tempi Vp1 else tempi Vp2 forj 0 k inicio j tamanho j k Vk tempj freetemp void mergeSortint V int inicio int fim int meio ifinicio fim meio floorinicio fim 2 mergeSortV inicio meio mergeSortV meio 1 fim mergeV inicio meio fim Similar ao quick sort existe uma função auxiliar merge que mescla os dados intercalação O quick sort é um algoritmo recursivo Apesar de ser uma recursão terminal o consumo de memória é bem maior pois ele precisa de um vetor auxiliar para a mesclagem o que não acontece com o quick sort Ordenação recursiva 49 A complexidade desse algoritmo é estável ON log N Há um bom desempenho bem como tempo de execução mas há um aumento de consumo de memória O fato de dividir o vetor mostra que esse algoritmo é mais indicado com vetores ORDENAÇÃO EXTERNA Os algoritmos apresentados até aqui só operam em memória e isso implica que a quantidade de dados não pode ser muito grande pois deve ser possível realizar todo o processo usando apenas a memória RAM Backes 2016 p49 comenta que esses métodos não são úteis quando a quantidade de dados a ser ordenada é maior do que a memória do computador Nesse tipo de situação precisamos de um método de ordenação externa Para que um método possa realizar a ordenação externa ele depende de leitura e escrita em memória secundária Para melhorar o desempenho desses algoritmos é necessário que cada leitura e escrita na memória secundária seja grande para reduzir esse custo Um algoritmo externo é o merge sort externo Basicamente ele faz a leitura de uma parte dos dados e realiza sua ordenação em memória e depois salva o resultado em memória secundária Repete esse processo para os demais dados A seguir vai fazendo a intercalação dos dados para obter o arquivo final ordenado Ordenação recursiva 50 Você aprendeu até aqui que a classificação de dados é uma atividade muito usada na criação de aplicações Conhecer algoritmos de ordenação compreender suas limitações e forças permite que o desenvolvedor seja capaz de criar código de qualidade atendendo às necessidades estabelecidas pelo cliente Não há um algoritmo que seja sempre o melhor portanto é necessário sempre avaliar o contexto do problema para identificar o melhor algoritmo A maior parte das linguagens têm bibliotecas de ordenação e cabe ao desenvolvedor entender como a biblioteca implementa seu processo de classificação para avaliar se a biblioteca poderá ser utilizada no contexto definido Continue seus estudos e até a próxima REFERÊNCIAS BACKES A R Estrutura de dados descomplicada em linguagem C Rio de Janeiro Elsevier 2016 BATISTA G Algoritmo Mergesort LinkedIn 1 mar 2021 Disponível em https ptlinkedincompulsealgoritmomergesortguilhermehenriquechavesbatista Acesso em 4 jan 2023 KOFFMAN E B WOLFGANG P AT Data Structures Abstraction and Design Using Java 3 ed Danvers Wiley 2016 LOUDON K Dominando algoritmos com C Rio de Janeiro Editora Ciência Moderna 2000 MEGAN Quick Sort in Ruby DEV Community 18 abr 2020 Disponível em https devtomwong068quicksortinruby2302 Acesso em 4 jan 2023 MORAES C R Estruturas de dados e algoritmos uma abordagem didática São Paulo Berkeley Brasil 2001 SENA I 53 Videoflix Alguns aspectos de algoritmos são mais fáceis de compreender ao se construir e testar sua execução Os vídeos disponíveis aqui são complementares ao conteúdo dos ebooks Eles apresentam e discutem o código de elementos de algoritmos e estruturas de dados demonstrando sua execução Aproveite httpsplayervimeocom video802795278h3d37511a1b Insertion sort httpsplayervimeocom video802795312h1627baf616 httpsplayervimeocom video802795341h93f3979819 Recursividade Merge sort 55 Aqui no infocast você vai aprender mais sobre duas formas simples de ordenação o bubble sort e o selection sort desde as características desses algoritmos e até alguns usos interessantes para eles Bons estudos Infocast 57 Comunicação Oral e Escrita 57 Bubble sort Olá Aqui você vai aprender mais sobre um algoritmo de ordenação bastante simples de implementar e que funciona muito bem para estruturas pouco desordenadas o bubble sort Vamos lá Como você aprendeu o bubble sort pode ser usado por exemplo para validar se a lista está ordenada ou não Outro uso bastante comum é quando se tem uma lista já ordenada que recebe um valor novo A assinatura da função apresenta dois parâmetros a lista a ordenar e o tamanho da lista Para entender melhor acompanhe a imagem de apoio com o código a seguir void bubbleSortint lista int tamanho int i aux trocou do trocou 0 fori 0 i tamanho 1 i iflistai listai 1 aux listai listai listai 1 listai 1 aux trocou 1 whiletrocou Note no início a declaração das variáveis a serem usadas O i vai ser usado como contador em um laço o for fará a navegação completa na lista o aux significa auxiliar e é usado para fazer a troca de posição de valores vizinhos e trocou é a variável que recebe zero para indicar que não houve trocas durante uma navegação completa pela lista e 1 se houver alguma troca Comunicação Oral e Escrita 58 58 Como é preciso fazer pelo menos uma navegação completa na lista usase um laço dowhile A primeira instrução é a atribuição de zero para trocou pois ainda não ocorreram trocas na navegação da lista A seguir temos o laço for que fará o controle da navegação Ele inicia em 0 e vai até o tamanho do array 1 menos um pois a comparação no corpo é do elemento atual com o próximo No corpo do laço comparase o elemento atual com o seguinte Se o atual for maior do que o seguinte eles estão fora de posição ou seja na ordem crescente então eles são trocados de posição e definese a variável trocou com 1 Isso se repete em toda a lista Ao final do for é verificado no while se houve alguma troca Se tiver o trocou recebe zero e o for se reinicia Quando sair do for com o trocou mantendo o valor 0 a ordenação foi encerrada Note que a ordenação ocorre no próprio array pois não há arrays auxiliares para realizar esse processo o que demonstra que o bubble sort consome pouca memória Encerramos por aqui e até a próxima 59 Comunicação Oral e Escrita 59 Selection sort Olá Aqui você vai aprender mais sobre um algoritmo que tem como característica a facilidade de troca de elementos fora de ordem sem necessidade de deslocamentos de outros elementos para abertura de espaço Além disso ele também apresenta tempo de execução relativamente constante Esse algoritmo é o selection sort A assinatura da função apresenta dois parâmetros a lista a ordenar e o tamanho da lista Para entender melhor acompanhe a imagem de apoio com o código a seguir void selectionSortint lista int tamanho int i j aux menor forint i 0 i tamanho 1 i menor i forj i 1 j tamanho j iflistamenor listaj menor j ifmenor i aux listai listai listamenor listamenor aux No início temse a declaração das variáveis a serem usadas Tanto o i e o j serão usados como contadores em laços for que farão a navegação completa na lista sendo que o j busca pelo elemento menor a partir da posição O aux significa auxiliar e é usado para fazer a troca de posição de valores fora de ordem Já a menor é a variável que recebe índice do menor elemento encontrado a partir da posição atual Comunicação Oral e Escrita 60 60 Há dois laços for um no corpo de outro A variável i controla a navegação completa pelo laço for externa e o j controla a navegação de busca do menor No for interno sempre que ele encontrar um elemento de valor menor do que o atual a variável menor recebe seu índice Ao final do laço for durante a busca desse valor é verificado se a variável menor foi alterada dentro do laço Se sim o elemento de índice menor é trocado com a posição atual e o atual vai para a posição do de índice menor Notase assim que na medida que o laço for externo avança a busca pelo menor vai ficando mais restrita O lado esquerdo vai sendo ordenado e ao chegar no fim do for externo a lista está ordenada Encerramos o assunto por aqui e até a próxima 61 Gostou do assunto Você pode aprender ainda mais sobre linguagens e módulos buscando novos horizontes sites links aplicativos e livros Saiba mais lendo e conferindo os materiais a seguir Quero saber httpswwwtreinawebcombrblogconhecaos principaisalgoritmosdeordenacao Principais algoritmos de ordenação Você pode conhecer os principais algoritmos de ordenação junto com animações para exemplificar cada um deles no site sugerido Acesse httpswwwfreecodecamporgportuguesenews algoritmosdeordenacaoexplicadoscomexemplosem pythonjavaec Algoritmos de ordenação em várias linguagens O site sugerido apresenta alguns algoritmos de ordenação em várias linguagens de programação Confira 62 httpsembarcadoscombrrecursividade Recursividade Você pode conferir mais sobre recursividade no site sugerido a seguir Acesse 63 Agora é o momento de conferir um resumo dos principais conhecimentos aprendidos ao longo de seus estudos até aqui Este resumo foi elaborado em formato de checklist para que você assinale os itens que considera já ter desenvolvido e caso sinta a necessidade retome os estudos Aproveite mais esta oportunidade de construção de saberes Resumindo Entendi o conceito e o funcionamento da recursividade Compreendi a diferença entre recursividade básica e final Conheci vários algoritmos de classificação de forma contextualizada ao seu uso Criei funções de classificação não recursivas Entendi o passo a passo de um algoritmo de classificação recursiva Entendi a diferença de algoritmos que classificam no próprio array e em array auxiliar Entendi o que deve ser considerado no momento de escolher qual é o melhor algoritmo de classificação para resolver o problema desejado 65 Para que os dados armazenados sejam recuperados de forma eficiente as funções de busca devem ser avaliadas para tenham o menor custo possível tais como tabelas hash e árvores Aqui você vai aprender esses aspectos de busca e as estruturas especiais Bons estudos ESTUDO E PRÁTICA II BUSCA E ESTRUTURAS ESPECIAIS Há muitas formas de recuperar dados realizar buscas ou pesquisas Cada uma dessas estratégias tem um objetivo técnico que a torna melhor do que outra Neste estudo você vai conhecer as mais comuns seus contextos de uso e quando e como cada um dos algoritmos deve ser usado Além disso também vai aprender sobre as estruturas especiais que são propostas para aumentar a eficiência que outras estruturas não conseguem obter Como exemplo temos a tabela hash que possui uma das estratégias de inserção e busca mais rápidas mas que contém diversas limitações bem como a árvore binária que é uma estrutura que se beneficia das características da busca binária Finalmente vai aprender sobre arquivos que são estruturas especiais para armazenamento de dados O tema desta leitura vai abranger a busca sequencial a busca sequencial com sentinela e a busca recursiva Esses são os modelos de busca mais usados então você vai conhecer a fundo as suas características e contexto de uso Bons estudos Ebook Algoritmos de busca Uma das operações básicas sobre um conjunto de dados é a busca Com certeza é uma das tarefas mais realizadas pelas aplicações Moraes 2001 p287 afirma que parecenos que a localização de um determinado elemento em um conjunto de elementos é algo simples porém o desenvolvimento de algoritmos eficientes de procura tem sido uma árdua tarefa para os cientistas da computação Nesse sentido o enfoque dado neste texto é de avaliação da qualidade do algoritmo dadas as restrições em que ele será aplicado Assim você vai conhecer os algoritmos entender seu funcionamento e avaliar em que contextos esses algoritmos são mais indicados Essa é a tarefa mais importante de um desenvolvedor na produção de código de qualidade Bons estudos PESQUISA A busca pode ser basicamente a busca pela existência de um dado valor em um conjunto de dados retornando verdadeiro ou falso conforme exista ou não no conjunto HEINEMAN et al 2016 bem como também pode ser uma busca por meio de uma chave sendo essa chave um elemento dentro da complexidade do valor Por exemplo o valor pode ser contato e ele possui os campos nome idade e telefone Assim a busca vai ser feita com base em um de seus campos Ainda no exemplo é possível também procurar pelo nome dentro de um conjunto de dados de valores do tipo Contato Algumas estruturas apresentam facilidades no processo de pesquisa favorecendo algoritmos mais otimizados enquanto outras dependem de maior esforço no processo Então os elementos de avaliação de uma pesquisa dependem da estrutura sobre a qual estão os dados como eles estão dispersos ordenados ou não ordenados e o tamanho do conjunto de dados Algoritmos de busca 69 Pesquisa sequencial A forma mais versátil e mais simples de ser entendida é a busca sequencial também conhecida como full scan A pesquisa sequencial tem implementação mais simples feita como uma construção básica em muitas linguagens de programação Assim esse algoritmo é utilizado quando a coleção estiver disponível somente sequencialmente como um iterador HEINEMAN et al 2016 23 4 67 8 54 90 21 23 54 4 67 8 54 90 23 4 67 8 54 90 23 4 67 8 54 90 23 4 67 8 54 90 0 1 2 3 4 5 6 0 1 2 3 4 5 6 V elem i0 i1 i2 i3 23 4 67 8 54 90 21 21 21 21 21 i4 Elemento procurado Valor diferente continua a busca Valor diferente continua a busca Valor diferente continua a busca Valor diferente continua a busca Valor igual termina a busca Figura 6 Busca sequencial Fonte Adaptado de Backes 2019 Há outras razões para se usar uma pesquisa sequencial entre elas podese destacar a busca em estruturas desordenadas ou a busca em elementos que podem ser repetidos Algoritmos de busca 70 A busca sequencial trata os dados como não ordenados assim existe a necessidade de percorrer o array inteiro BACKES 2016 Como o processo envolve ler os elementos do início ao fim comparando um a um com o padrão pesquisado isso permite pesquisas em qualquer tipo de estrutura mesmo as de acesso sequencial como as listas encadeadas Moraes 2001 apresenta o seguinte pseudocódigo para a busca sequencial inicio leia dadoproc achou F para j 1 até n faça se tabelaj dadoproc então achou V ind j fim se fim para se achou V então imprima Dado achado na posição ind senão imprima Dado não achado fim se fim Algoritmos de busca 71 Observe que o dado pesquisado dadoproc uma vez encontrado é atribuído ao índice do elemento que contém o dado procurado ou ind Uma pequena alteração aqui e podemos inserir os índices encontrados em um array de índices encontrados transformando essa busca em múltipla ou seja todos os elementos que forem compatíveis com dado procurado serão achados A complexidade dessa pesquisa é On no pior caso No melhor caso o dado procurado seria encontrado na primeira posição mas notase que no algoritmo apresentado não há uma saída quando o dado é encontrado mantendose a mesma complexidade Isso só faz sentido se o desejado é obter todos os elementos iguais ao valor procurado Se não é essa a intenção então a função deve retornar a posição do valor encontrado assim que ele for encontrado interrompendo a busca Mão na massa Implemente as alterações necessárias neste algoritmo para buscar a primeira ocorrência de um dado e para buscar todas as ocorrências desse dado Algoritmos de busca 72 Pesquisa sequencial com sentinela No processo de busca fazse a comparação do valor buscado com o elemento atual da lista para avaliar se ele foi encontrado e no laço para verificar se o elemento é o último da lista Dessa forma são duas comparações a cada iteração Contudo Moraes 2001 apresenta uma estratégia de redução de esforço na busca da primeira ocorrência de um dado valor Ele explica que há uma forma de fazer apenas uma comparação mas para isso é necessário ter certeza de que o elemento procurado está na lista Afinal o desejo é encontrar a primeira ocorrência e ao identificála há saída do laço da procura não havendo risco de tentar ler um elemento inválido depois do final Para garantir a existência do elemento na lista ele é inserido no final sendo a sentinela a responsável por não deixar que durante o processo de leitura aconteça a leitura de um elemento além do limite da lista Para saber se o elemento foi encontrado ou se parou por conta da sentinela é só verificar se a posição encontrada é menor do que o tamanho da lista pois a posição da sentinela é exatamente o tamanho da lista Com isso é reduzido em praticamente a metade o número de comparações necessárias pelo algoritmo Esse tipo de pesquisa continua sendo possível em qualquer tipo de estrutura seja ordenada ou não tanto de acesso aleatório como arrays quanto de acesso sequencial como listas encadeadas A restrição que ela tem é a de que só realiza a busca da primeira ocorrência Algoritmos de busca 73 Mão na massa Implemente este algoritmo para buscar a primeira ocorrência de um dado em vetor e em lista de encadeamento simples Pesquisa sequencial com dados ordenados Outra forma de otimizar a busca sequencial é pela realização em uma estrutura ordenada A busca sequencial ordenada assume que os dados estão ordenados Dessa forma se o elemento procurado for menor do que o valor em determinada posição do array ele não estará no restante do array Isso evita a necessidade de percorrer o array inteiro BACKES 2016 Algoritmos de busca 74 8 34 4 21 23 54 67 90 8 4 21 23 54 67 90 0 1 2 3 4 5 6 8 4 21 23 54 67 90 8 4 21 23 54 67 90 8 4 21 23 54 67 90 8 4 21 23 54 67 90 V elem i0 Valor diferente continua a busca i1 Valor diferente continua a busca i2 Valor diferente continua a busca i3 Valor diferente continua a busca i4 Valor é maior elemento não existe Elemento procurado 0 1 2 3 4 5 6 Figura 7 Busca sequencial com dados ordenados Fonte Adaptado de Backes 2019 Na busca ordenada é possível obter todos os resultados identificados ou só o primeiro Também é possível ser realizada em estruturas de acesso aleatório como os arrays ou de acesso sequencial como as listas encadeadas A única restrição é que a lista precisa estar ordenada Além disso aqui também é possível se beneficiar do uso da sentinela para não precisar avaliar se a lista chegou ao final Mas isso restringe a pesquisa de sair na primeira ocorrência Mão na massa Construa a função que realiza a pesquisa sequencial ordenada com sentinela para uma ocorrência e sem sentinela para múltiplas ocorrências Algoritmos de busca 75 Pesquisa binária Uma solução muito mais eficiente de busca pode ser conseguida com a restrição de que a lista esteja ordenada e o acesso aleatório aos elementos Com essas duas restrições a busca no pior caso passa a ser Olog n A pesquisa binária tem melhor desempenho do que a pesquisa sequencial porque começa com uma coleção de elementos já classificados Ela divide a coleção classificada pela metade até que o item procurado seja encontrado ou até que seja determinado que o item não existe na coleção HEINEMAN et al 2016 Backes 2016 p60 cita que a busca binária é uma estratégia baseada na ideia de dividir para conquistar A cada passo esse algoritmo analisa o valor do meio do array Caso o valor seja igual ao elemento procurado a busca termina Do contrário a busca continua na metade do array que condiz com o valor procurado Algoritmos de busca 76 8 5 1 4 14 21 23 54 67 90 8 4 5 1 4 14 21 23 54 67 90 8 5 1 4 14 21 23 54 67 90 8 5 1 4 14 21 23 54 67 90 8 5 1 4 14 21 23 54 67 90 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 V elem meio4 Valor é menor buscar no início meio1 Valor é maior buscar no final meio2 Valor é maior buscar no final meio3 Valor é igual terminar a busca Elemento procurado Figura 8 Busca sequencial com dados ordenados Fonte Adaptado de Backes 2019 A cada busca resta somente metade dos elementos para se buscar e isso reduz drasticamente a quantidade de elementos pesquisados Quanto maior a lista maior o ganho da pesquisa binária em relação à pesquisa sequencial Apesar de não ser feita para esse fim esse tipo de pesquisa pode trazer mais de uma ocorrência do elemento buscado com pequena alteração do algoritmo Mão na massa Implemente a busca binária de modo que permita a recuperação da posição de todas as ocorrências do elemento buscado Algoritmos de busca 77 USO DE ALGORITMOS DE PESQUISA Algoritmos de pesquisa são usados para diversas aplicações Moraes 2001 apresenta dois usos comuns a busca do menor ou maior elemento de uma coleção e a determinação da moda de uma coleção Busca do maior ou menor A busca do menor ou do maior elemento em uma coleção é muito comum e frequente Moraes 2001 propõe o seguinte pseudocódigo início maior 1 para j 2 até n faça se tabelaj tabelamaior então maior j fim se fim para fim Algoritmos de busca 78 A varredura nos elementos da coleção é feita a partir da posição do maior ou menor elemento como 1 Na medida que avança é verificado se ele é o maior ou menor se for a nova posição é garantida Isso é repetido até o final da coleção quando se tem o índice do maior ou menor elemento Mão na massa Implemente este algoritmo para identificar o menor elemento Identificando a moda de uma coleção Em estatística a moda é o elemento que mais aparece em uma coleção Este é um algoritmo proposto por Moraes 2001 apresentado pelo pseudocódigo Algoritmos de busca 79 início para i 1 até n 1 faça conta 1 para j i 1 até n faça se tabelai tabelaj então conta conta 1 fim para freqi conta fim para max 1 para i 2 até n faça se freqi freqmax então max i fim para moda tabelamax imprima Moda é igual a moda fim A primeira parte do algoritmo lê elemento a elemento e busca em todo o array o número de ocorrências deles A frequência ou seja a quantidade de ocorrências de cada elemento fica armazenado em um array freq Já a parte final do algoritmo busca em freq qual o elemento de maior ocorrência que é a moda daquela coleção Mão na massa Implemente este algoritmo de identificação da moda Algoritmos de busca 80 Dá para notar que há muitas formas de realizar buscas em coleções de dados A escolha da melhor forma depende das características envolvidas no problema Alguns algoritmos somente se aplicam para estruturas e acesso aleatório outras podem ser aplicadas a qualquer tipo de estrutura Existem ainda algoritmos que só podem ser aplicados a coleções classificadas Conhecer esses algoritmos e entender suas limitações é a forma de poder avaliar o problema e escolher o melhor conforme o caso em questão Continue seus estudos e até a próxima REFERÊNCIAS BACKES A R Busca em Arrays Aula 05 Faculdade de Computação FACOM Universidade Federal de Uberlândia UFU 2019 Disponível em httpswww facomufubrbackesgsi011Aula05Buscapdf Acesso em 4 jan 2023 BACKES A R Estrutura de dados descomplicada em linguagem C Rio de Janeiro Elsevier 2016 MORAES C R Estrutura de dados e algoritmos uma abordagem didática São Paulo Berkeley Brasil 2001 HEINEMAN G T POLLICE G SELKOW S Algorithms in a Nutshell A Practical Guide 2 ed Graveinstein Highway North OReailly Media Inc 2016 SENAI 83 Nesta leitura serão abordados três temas importantes quando falamos de busca e da estrutura de dados a tabela hash árvores e arquivos Aqui você vai aprender o que são e como são implementados na prática Boa leitura Ebook Tabela hash árvores e arquivos Tabela hash árvores e arquivos 86 As estruturas de dados servem para armazenar dados e recuperar dados Procurase sempre obter o melhor das estruturas seja quanto à inserção do dado na estrutura ou quanto à sua recuperação posterior Dessa forma vários esforços são empregados em identificar estruturas que otimizem esses aspectos e duas soluções muito eficientes são a tabela hash e a árvore Com a tabela hash a inserção e busca são baseadas no resultado de uma função que realiza acesso direto ao elemento Já a estrutura em árvore é uma solução que torna mais simples a inserção do que em uma lista ordenada e a pesquisa passa a ser uma busca binária Os arquivos são uma estrutura usada pelos sistemas operacionais para armazenamento de dados É definido por meio de uma estrutura struct que agrupa as informações relativas a ele Essas informações são usadas pelo sistema operacional para diversos fins como você vai acompanhar aqui Para compreender o problema de inserção e recuperação de dados em estruturas Backes 2016 p 269 diz que uma grande variedade de métodos de busca funciona segundo o mesmo princípio procurar a informação desejada com base na comparação de suas chaves isto é com base em algum valor que a compõe Um dos problemas disso é que para obtermos algoritmos eficientes os elementos devem ser armazenados de forma ordenada Desconsiderando o custo da ordenação que no melhor caso é ON log N temos que os algoritmos mais eficientes de busca possuem complexidade Olog N Uma forma de contornar esse problema seria mudar o modelo de armazenamento e busca Backes 2016 p269 cita que uma operação de busca ideal seria aquela que permitisse o acesso direto ao elemento procurado sem nenhuma etapa de comparação de chaves Neste caso teríamos um custo O1 Mas como isso poderia ser feito A estratégia é estabelecer uma forma com a qual a chave usada do elemento seja transformada em um índice que poderá ser usado tanto para inserir o elemento em um array quanto para buscálo Para isso usase uma função de hashing Tabela hash árvores e arquivos 87 TABELA HASH Um tipo abstrato de dados que use uma tabela hash precisa basicamente de um array para guardar os elementos e uma função de hashing para obter o índice de inserção e recuperação Existem alguns problemas no entanto que precisam ser considerados Uma questão é na escolha do tamanho do array Se o array for abrigar todos os elementos o tamanho do array deve ter o tamanho do total de elementos esperados Essa contudo não é a forma mais comum normalmente usase uma segunda estrutura A razão é que dificilmente há como garantir que o resultado da função de hashing seja sempre diferente dadas as entradas diferentes Quando entradas diferentes geram índices iguais temos uma colisão Não há como colocar dois elementos na mesma posição e por isso é preciso tratar as colisões com basicamente duas estratégias tabelas hashing encadeadas e endereçamento aberto Tabela hash árvores e arquivos 88 a Endereçamento aberto b Tabela hash encadeada Figura 9 As duas estratégias de colisão endereçamento aberto e tabela hash encadeada Fonte Do autor 2022 O endereçamento aberto usado quando ocorre uma colisão no resultado da função de hashing gera uma nova operação para identificar o próximo índice para inclusão rehash por exemplo Uma forma mais simples de fazer isso é buscar a próxima posição vaga no array a partir da posição calculada Essa estratégia apresenta como vantagem a melhor ocupação do array não deixando posições livres Contudo apresenta como desvantagem o custo das operações de inserção e recuperação Quando há restrição de memória esta pode ser uma opção viável Tabela hash árvores e arquivos 89 A estratégia de tabela hash encadeada usa uma lista encadeada com seu endereço inicial guardado em cada índice do array Quando o índice para inserção é obtido inserese um nodo na lista encadeada daquele índice e quando há colisões um novo nodo é inserido na mesma lista daquele índice Assim quando é preciso recuperar um elemento buscase no índice para ler a sua lista encadeada Essa estratégia cria de fato partições onde cada índice é uma partição da tabela que pode receber n elementos Dependendo da qualidade da função de hashing o espalhamento entre as listas encadeadas deve ser homogêneo isso faz com que as listas sejam o mais curtas possível Desse modo em um array pequeno em relação à quantidade de elementos armazenados na estrutura é possível aumentar seu fator de carregamento Por esse motivo o fator de carregamento da tabela hashing é muito importante e é definido como α Onde n é o número de elementos da tabela e m é o número de posições nas quais os elementos podem executar o hash LOUDON 2000 Assim m é o tamanho do array e n o número total de elementos inseridos na estrutura Se a distribuição da função de hashing for uniforme esse número indica a quantidade de elementos que serão encontrados em cada lista encadeada Este tipo de estrutura é muito usada em banco de dados para armazenamento de índices pois seu tempo de resposta é muito bom dependendo do tipo de chave e função de hashing utilizado o tempo de resposta pode chegar no nível de ideal O1 Mesmo quando a estrutura usa a estratégia de endereçamento aberto os elementos não devem ser guardados no array e sim um ponteiro que aponte para o elemento Afinal um ponteiro tem tamanho fixo sendo fácil de alocar mesmo sem conhecer o tamanho da estrutura do elemento representando economia de espaço pois a estrutura do elemento provavelmente será maior do que um inteiro espaço ocupado por um ponteiro Dica Tabela hash árvores e arquivos 90 Funções de hashing A função de hashing tem o objetivo de traduzir uma chave de um elemento em um índice de um array Para ficar mais claro acompanhe este exemplo Suponha que o tamanho do array seja 10 e a chave para ser aplicada na função de hashing seja um número inteiro O objetivo da função de hashing é transformar este inteiro em um valor de 0 a 9 que são os índices existentes nesse array Uma função que é capaz de fazer isso é a função divisão Essa função recebe um inteiro e o divide pelo tamanho do array retornando o resto dessa divisão O resultado dessa função será portanto um valor de 0 quando a divisão é exata a 9 pois o tamanho do array é 10 Você aprendeu sobre o problema da colisão e uma forma de reduzir esse tipo de problema é usar um número primo como tamanho da tabela BACKES 2016 Como sempre teremos envolvidas operações matemáticas para obter o valor do índice números primos apresentam menos problemas com múltiplos A função de hashing precisa ser simples o suficiente para não onerar o processo de inserção e busca Segundo Backes 2016 as características importantes dessa função são Tabela hash árvores e arquivos 91 Simples e barata de calcular Garantir que valores diferentes produzam posições diferentes Máximo espalhamento ou seja gerar uma distribuição equilibrada dos dados na tabela onde cada posição tem a mesma chance de receber uma chave O ideal é que a função não produza valores iguais a partir de entradas diferentes o que é chamado de hash perfeito Na prática isso é muito difícil de conseguir Pode acontecer quando se sabe exatamente todas as entradas possíveis e criase uma função para essas entradas Assim é possível garantir que a saída será sempre diferente Em outros casos a colisão é bastante provável Backes 2016 sugere o seguinte código para essa função int chaveDivisaoint chave int TABLESIZE return chave 0x7FFFFFFF TABLESIZE A primeira parte chave 0x7fffffff é uma operação realizada para evitar que a chave seja um número negativo Dica Observe que o autor usa TABLESIZE como nome de uma variável Essa não é uma boa prática pois usamos nomes de caixaalta para elementos de substituição com define Tabela hash árvores e arquivos 92 Essa função é leve simples e útil para chaves de números inteiros Outros métodos de cálculo do hash apresentados por Moraes 2001 são Método direto Método da subtração Extração de dígito Método quadrático Método folding Método da rotação Método pseudoaleatório Cada um deles apresenta características que podem fazer com que eles sejam mais eficientes dada uma faixa de valores de entrada possível Há possibilidade de a chave não ser numérica Nesse caso primeiro é necessário fazer uma conversão dos caracteres para números para depois calcular o índice Uma maneira de fazer isso é usar o código ASCII do caractere Um cuidado no entanto é que palavras com as mesmas letras não devem dar o mesmo hash por exemplo MALA e ALMA devem dar hashs diferentes Uma solução para isso é incluir no processo a informação posicional do caractere Atenção Tabela hash árvores e arquivos 93 Estrutura da tabela hash A estrutura da tabela hash contém os seguintes campos quantidade tamanho e o vetor que armazenará as listas encadeadas pode ser somente o vetor se a estratégia for de endereçamento aberto A quantidade é usada para armazenar o total de elementos inseridos na estrutura O tamanho é o tamanho do array Admitindo que será inserido uma estrutura contato na tabela hash temse as seguintes definições struct Contato char nome char telefone struct Lista Node inicio Node fim struct tabelahash int quantidade int tamanho struct Lista lista A estrutura definida para a tabela hash tem um ponteiro para a criação do vetor de listas encadeadas As listas podem ser de nodos simples uma vez que as inserções serão sempre pelo final Tabela hash árvores e arquivos 94 ÁRVORES As árvores são importante estruturas que se assemelham um tipo de lista encadeada com a diferença de que ela pode ter mais de dois vizinhos mais do que apenas o anterior e próximo Assim uma árvore é uma estrutura de dados não linear que tem dois componentes os nodos e as arestas onde nodos são unidos pelas arestas BHASIN 2015 Para Backes 2016 p 335uma árvore é uma abstração matemática usada para representar estruturas hierárquicas não lineares dos objetos modelados 24 10 12 5 5 12 10 32 35 29 Raiz Nível 0 Nível 1 Nível 2 Nósfolha Subárvore esquerda Subárvore direita Nósfilho de 29 35 32 Nósfilho de Nósfolha Figura 10 Estrutura de uma árvore Fonte Adaptado de Fontenelle 2020 Tabela hash árvores e arquivos 95 Backes 2016 apresenta os seguintes conceitos básicos de uma árvore Raiz é o nodo localizado na parte mais alta da árvore o único que não possui pai Pai também chamado ancestral é o nodo antecessor imediato de outro nodo Filho é o nodo sucessor imediato de outro nodo Nodo folha também chamado nodo terminal é qualquer nodo que não possui filhos Nodo interno também chamado nodo não terminal é qualquer nodo que possui ao menos um filho Caminho é uma sequência de nodos de modo que existe sempre uma aresta ligando o nodo anterior com o seguinte Note que existe um caminho entre a raiz e cada um dos nodos da árvore Assim há basicamente três caminhos préordem em ordem inorder e pósordem Na imagem a seguir os pontos ajudam a compreender a ordem percorrida em cada um destes três caminhos F B G H I D A E C F B G H I D A E C F B G H I D A E C Préordem F B A D C E G I H Ordem simétrica A B C D E F G H I Pósordem A C E D B H I G F Figura 11 Caminhos em uma árvore Fonte Adaptado de Stumm 2015 Subárvore dado um nodo da árvore cada filho seu é considerado a raiz de uma nova subárvore ou seja qualquer nodo é a raiz de uma subárvore constituindose dele e dos nodos abaixo dele Grau do nodo é dado pelo número de subárvores que ele possui Nível da árvore é dado pelo número de nodos que existem no caminho entre esse nodo e a raiz a raiz é nível 0 Altura da árvore também chamada profundidade é o número total de níveis de uma árvore ou seja é o comprimento do caminho mais longo da raiz até uma de suas folhas Árvore binária Backes 2016 p338 cita que uma árvore binária é um tipo especial de árvore em que cada nó pode possuir nenhuma uma ou no máximo duas subárvores a subárvore da esquerda e a da direita Conforme estejam os nodos nas árvores elas podem ser de alguns tipos Raiz Folha Nó Folha Nó Folha Folha Raiz Nó Folha Folha Nó Nó Folha Folha Folha Raiz Nó Nó Nó Folha Folha Folha Folha Folha Folha Folha Folha Nó Nó Nó a Árvore estritamente binária a Árvore binária completa a Árvore binária cheia Figura 12 Tipos de árvores binárias Fonte Adaptado de BSIDADOS 2015 Tabela hash árvores e arquivos 97 Conforme destaca Backes 2016 p339 uma árvore estritamente binária é aquela na qual cada nó possui sempre ou nenhum no caso do nó folha ou duas subárvores Não existe nenhum nó interno com apenas um filho Já na árvore completa todos os nós com menos de dois filhos ficam no último e no penúltimo ASCENCIO ARAÚJO 2010 7 1 3 0 5 2 6 4 10 8 11 12 9 3 1 2 0 5 6 4 Árvore binária cheia Árvore binária perfeita Figura 13 Árvore binária cheia e perfeita Fonte Adaptado de Koffman e Wolfgang 2015 Conforme afirmam Koffman e Wolfgang 2015 uma árvore cheia é aquela onde todos os nodos têm dois ou zero filhos e uma árvore perfeita é tem altura n com exatamente 2n 1 nós Árvore binárias de busca Para definir árvore binária de busca Feofiloff 2009 p 121 sugere o seguinte Considere uma árvore binária cujos nós têm um campo chave de um tipo linearmente ordenado como int ou string por exemplo Podemos supor que os nós da árvore têm a seguinte estrutura Tabela hash árvores e arquivos 98 struct cel int chave int conteúdo struct cel esq struct cel dir typedef struct cel nó Uma árvore binária deste tipo é de busca em relação ao campo chave se cada nó X tem as seguintes propriedades onde a chave de X é 1 maior ou igual à chave de qualquer nó na subárvore esquerda de X e 2 menor ou igual à chave de qualquer nó na subárvore direita de X Nesse tipo de árvore o caminho em ordem inorder apresenta os valores ordenados O processo de inserção precisa seguir essas regras e na recuperação essas regras tornam a busca similar a uma busca binária Moraes 2001 p186 apresenta as limitações de estruturas como Se um vetor tiver dados ordenados é possível obter um algoritmo de pesquisa muito eficiente denominado pesquisa binária Entretanto essa estrutura não é muito eficiente na inserção e na remoção devido à necessidade de reorganização da estrutura para a manutenção da ordenação As listas ligadas resolvem esse problema de inserção e remoção pelo uso exclusivo de ponteiros O grande problema com as listas ligadas é que os algoritmos de pesquisas são sequenciais por isso considerados ineficientes Tabela hash árvores e arquivos 99 A árvore de busca binária dado suas regras passa a usar um algoritmo de busca binária em uma estrutura ligada tornando eficiente também a inserção a remoção e a pesquisa ARQUIVOS Conforme Tanenbaum 2016 p 182 arquivos são unidades lógicas de informação criadas por processos um arquivo é um mecanismo de abstração Ele fornece uma maneira para armazenar informações sobre o disco e lêlas depois Isso deve ser feito de tal modo que isole o usuário dos detalhes de como e onde as informações estão armazenadas e como os discos realmente funcionam Na verdade arquivos são armazenados em dispositivos secundários quaisquer Seu acesso ocorre como fluxos de dados e são interpretados dessa forma pelos sistemas operacionais Em sistemas operacionais Unix há três fluxos padrão Entrada padrão stdin Saída padrão stdout Saída de erro stderr Tabela hash árvores e arquivos 100 São esses fluxos que permitem a comunicação da aplicação com o usuário A entrada padrão normalmente é o teclado e a saída padrão e saída de erro normalmente são a tela Mas se ambas as saídas normalmente são na tela os fluxos são separados Afinal na execução de programas existem erros que são gerados e se no momento houver a geração de uma saída ela seria misturada com mensagens de erro Nesse sentido é possível manipular arquivos somente com estes fluxos por exemplo cat etcpasswd Com este comando é possível ler o arquivo de cadastro de usuários de um sistema Unix e também escrever em arquivos mesmo que ainda não existentes usando estes fluxos conforme o exemplo echo exemplo de escrita exemplotxt Com esse comando é possível escrever a string ecoada no arquivo de nome exemplotxt que será criado ou sobrescrito Se quiser incluir outras strings no arquivo sem apagar o que já está lá usase o comando echo Outra linha incluida exemplotxt Isso é possível porque estes fluxos padrão estão sempre disponíveis pelo sistema operacional Assim se for necessário manipular outro arquivo fluxo será necessário que a aplicação faça isso Tabela hash árvores e arquivos 101 O sistema operacional associa o arquivo fluxo a um descritor que é um número inteiro Os descritores 0 1 e 2 já existem e são respectivamente a entrada padrão saída padrão e a saída de erro Assim se a aplicação for manipular algum arquivo usará um descritor maior que 2 O descritor é a referência que a aplicação tem relativamente ao sistema operacional Em linguagem C podese manipular arquivos usando diretamente o descritor include fcntlh include systypesh include stdioh int main int descritor modet mode OCREAT OWRONLY descritor openarquivotxt mode writedescritor Texto a ser gravado 20 closedescritor mode ORDONLY descritor openarquivotxt mode char strleitura50 readdescritor strleitura 20 printfLido do descritor d s descritor strleitura closedescritor Tabela hash árvores e arquivos 102 Este é um exemplo de criação abertura escrita e leitura de arquivos em baixo nível usando funções que acessam diretamente o descritor Nenhum cabeçalho é necessário para o uso dessas funções mas existem algumas onde eles facilitam o seu uso por exemplo O arquivo de cabeçalho fcntlh pode ser usado para converter OCREAT O WRONLY e ORDONLY por seus valores hexadecimais correspondentes O arquivo de cabeçalho systypesh pode ser usado ao usar o tipo modet para definir a variável mode em vez de usar diretamente os hexadecimais na chamada das funções O arquivo de cabeçalho stdioh pode ser usado por conta da função printf Normalmente não se trabalha com funções de baixo nível como no exemplo Para manipular arquivos há uma estrutura que define um tipo especial o FILE A linguagem C trabalha com apenas dois tipos de arquivos os arquivos texto e os arquivos binários Os arquivos texto são aqueles que os dados armazenados estão convertidos para ASCII e podem ser abertos e editados por editores de texto simples como o bloco de notas Já os arquivos binários são armazenados como sequência de bits que para serem lidos dependem do programa que os gerou Os arquivos binários ocupam menos espaço pois não passam por conversões Tabela hash árvores e arquivos 103 Ao usar o tipo abstrato FILE temos elementos em sua estrutura que permitem seu acesso sem precisarmos conhecêlos Um desses elementos é o descritor de arquivo conforme você aprendeu Há um conjunto de funções para manipulação de arquivos com o uso do ponteiro FILE Acompanhe este exemplo include stdioh int main FILE file file fopenarquivo1Textotxt w fputsEscrevendo 1000 2000 3000 4000 5000 6000 como texto file char primeiro Escrevendo int numeros 1000 2000 3000 4000 5000 6000 char segundo como texto fclosefile file fopenarquivo1Binariotxt wb fwriteprimeiro sizeofchar 11 file fwritenumeros sizeofint 6 file fwritesegundo sizeofchar 11 file fclosefile return 0 Observando o conteúdo dos dois arquivos notase que um é legível mas no outro a parte que é string é legível porém os números não são Eles foram gravados em binário assim podem ficar menor como neste exemplo em que cada número tinha 4 char e um inteiro tem o tamanho de 2 char Arquivos podem ser lidos e escritos de forma bufferizada como neste exemplo em que a escrita não é realizada caractere a caractere mas sim gravada um bloco de cada vez Tabela hash árvores e arquivos 104 Nem tudo é gravado de fato no arquivo quando a função é executada O sistema operacional pode deixar para fazer essas gravações em momentos de mais ociosidade do ambiente Ao fechar o arquivo a gravação é encerrada por isso os arquivos precisam ser sempre fechados A extensão não caracteriza de fato um arquivo O que pode permitir que tenhamos uma identificação mais adequada destes arquivos são seus números mágicos Esses números mágicos são o conjunto de caracteres que inicia o arquivo Ao usar o comando file do Linux é possível notar que ele identifica os arquivos pelos seus números mágicos Dica O uso de arquivos para transferência de dados e muitas vezes entre aplicações é muito comum no cotidiano Uma forma de fazer isso é definindo uma estrutura para esses arquivos Duas estruturas mais usadas são o XML e o JSON O XML é uma estrutura que permite muitos metadados informações sobre dados Já o JSON é mais leve mas somente permite que os dados tenham um rótulo ou nome Outros tipos de arquivos também são usados como arquivos separados por vírgulas arquivos de tamanho fixo e de tamanho variável Dessa forma notase que existem muitos tipos de estruturas de dados que permitem armazenar e recuperar dados conforme as necessidades de projeto Se desempenho é necessário no entanto algumas estruturas especiais fornecem esta característica Estas estruturas são muito usadas para indexação de banco de dados tornandoos mais rápidos na recuperação de suas informações Em resumo os dados são armazenados em arquivos que são controlados pelo sistema operacional Esses arquivos podem ser gravados de forma textual ou binária conforme a necessidade O sistema operacional vê esses arquivos como fluxos de dados Além dessas características há alguns tipos de arquivos muito usados tais como csv xml e json REFERÊNCIAS ASCENCIO A F G ARAÚJO G S de Estruturas de dados algoritmos análise da complexidade e implementações em java e cc São Paulo Pearson Prentice Hall 2010 BACKES A R Árvores e árvore binária de busca Aula 10 Faculdade de Computação FACOMUniversidade Federal de Uberlândia UFU 2021 Disponível em https wwwfacomufubrbackesgsi011Aula10Arvorespdf Acesso em 4 jan 2023 BACKES A R Estrutura de dados descomplicada em linguagem C Rio de Janeiro Elsevier 2016a BACKES A R Tabela Hash Aula 7 Faculdade de Computação FACOM Universidade Federal de Uberlândia UFU 2019 Disponível em httpswww facomufubrbackesgsi011Aula07TabelaHashpdf Acesso em 4 jan 2023 BHASIN H Algorithms analysis and designs New Delhi Oxford University Press 2015 CAROLINA A Árvore Binária Estrutura de Dados Conhecimentos de alunos do curso de Sistema de Informação BSIDADOS 15 mar 2015 Disponível em https bsidadosblogspotcom201503arvorebinariahtml Acesso em 5 jan 2023 FEOFILOFF P Algoritmos em linguagem C Rio de Janeiro Elsevier 2009 FONTENELLE R Estruturas de Dados Árvores Binárias Cod3r 23 nov 2020 Disponível em httpsblogcod3rcombrestruturasdedadosarvoresbinarias Acesso em 5 jan 2023 KOFFMAN E B WOLFGANG P A T Data Structures Abstraction and Design Using Java 3 ed Danvers Wiley 2016 LOUDON K Dominando algoritmos com C Rio de Janeiro Editora Ciência Moderna 2000 MORAES C R Estrutura de dados e algoritmos uma abordagem didática São Paulo Berkeley Brasil 2001 TANENBAUM A S Sistemas operacionais modernos São Paulo Pearson Education do Brasil 2016 STUMM JR V Árvore Binária de Busca em Python Python Help 19 jan 2015 Disponível em httpspythonhelpwordpresscom20150119arvorebinaria debuscaempython Acesso em 5 jan 2023 SENAI 107 Videoflix Estruturas especiais otimizadas para armazenamento e recuperação de dados podem ser bastante desafiadoras Tabelas hash apresentam característica de mesclar mais de um tipo de infraestrutura para atender a uma forma de armazenamento Árvores são estruturas que têm suas funções baseadas em recursividade tema também bastante desafiador Estes vídeos devem tornar o tema mais acessível pois a discussão de seu código e verificação de sua execução serão uma excelente forma de tornar o entendimento destas estruturas mais adequado Aproveite httpsplayervimeocom video802795371hcc8e6cc6e3 httpsplayervimeocom video802795406h58f1c9bc43 httpsplayervimeocom video802795423h77fa40c0a7 Tabela hash de contatos Operações básicas da árvore sem o remover Remover da árvore e busca 109 A compreensão do funcionamento e uso de estruturas de busca é fundamental para a construção de códigos robustos e eficientes Mais do que simplesmente discutir o funcionamento desses algoritmos compreender suas vantagens desvantagens e limitações de uso é que constroem as condições de um desenvolvedor tomar a decisão correta na escolha do algoritmo para um determinado problema Além disso com a avaliação desses algoritmos ficará mais fácil o entendimento da questão da complexidade algorítmica Aproveite Infocast 111 Comunicação Oral e Escrita 111 Busca fullscan versus busca com sentinela Olá Agora você vai acompanhar a comparação de dois códigos de busca sequencial um sem sentinela e um com sentinela Essa comparação vai ajudar a compreender por que dois códigos de mesma complexidade algorítmica podem apresentar desempenho diferente Vamos lá Para entender melhor acompanhe a imagem de apoio com o código a seguir include stdioh void buscasequencialint valores int tamanho int valor int i 0 int posicao 1 do ifvaloresi valor posicao i break i whilei tamanho ifposicao 0 printfValor nao encontrado else printfAchou d na posicao d valor posicao void buscacomsentinelaint valores int tamanho int valor int i 0 int posicao 1 valorestamanho valor do ifvaloresi valor posicao i break i while1 ifposicao tamanho printfValor nao encontrado else printfAchou d na posicao d valor posicao int main int vetor20 1 2 3 4 5 6 7 8 9 10 buscasequencialvetor 10 5 buscasequencialvetor 10 11 buscacomsentinelavetor 10 5 buscacomsentinelavetor 10 11 A função buscasequencial faz duas comparações uma dentro do laço no if e outra no laço final no while Já a função buscacomsentinela faz uma comparação apenas dentro de laço no if Isso implica que a quantidade de instruções executadas na segunda função é menor do que na primeira Mas nas duas funções o que se tem é uma complexidade On Comunicação Oral e Escrita 112 112 include stdioh void buscasequencialint valores int tamanho int valor int i 0 int posicao 1 do ifvaloresi valor posicao i break i whilei tamanho ifposicao 0 printfValor nao encontrado else printfAchou d na posicao d valor posicao void buscacomsentinelaint valores int tamanho int valor int i 0 int posicao 1 valorestamanho valor do ifvaloresi valor posicao i break i while1 ifposicao tamanho printfValor nao encontrado else printfAchou d na posicao d valor posicao int main int vetor20 1 2 3 4 5 6 7 8 9 10 buscasequencialvetor 10 5 buscasequencialvetor 10 11 buscacomsentinelavetor 10 5 buscacomsentinelavetor 10 11 Vamos entender isso melhor Se a primeira função receber um vetor com 1000 elementos ela terá um tempo x de execução Assim se o tamanho for 5000 elementos o tempo de execução será 5x Nesse sentido o tempo de execução cresce da mesma forma ou seja em função de n quantidade de elementos uma vez que a quantidade de elementos cresce Se a segunda função receber um vetor com 1000 elementos ela terá um tempo y de execução certamente menor do que a função anterior Assim se o tamanho for 5000 elementos o tempo de execução será 5y Dessa forma apesar do tempo da segunda função ser menor do que o da primeira a forma como o tempo cresce em função da quantidade de elementos é a mesma E isso é a interpretação de complexidade Encerramos por aqui e até a próxima 113 Comunicação Oral e Escrita 113 Busca com sentinela versus busca binária Olá Aqui você vai acompanhar a comparação de duas formas otimizadas de busca a busca sequencial com sentinela e a busca binária recursiva Vamos lá Para entender melhor acompanhe a imagem de apoio com o código a seguir include stdioh int buscacomsentinelaint valores int tamanho int valor int i 0 int posicao 1 valorestamanho valor do ifvaloresi valor posicao i break i while1 return posicao tamanho 1 posicao int buscabinariaint valores int inicio int fim int valor int meio if inicio fim return 1 else meio inicio fim 2 if valoresmeio valor return meio else if valoresmeio valor return buscabinariavalores inicio meio valor else return buscabinariavalores meio fim valor int main int vetor20 1 2 3 4 5 6 7 8 9 10 printfPosicao d buscabinariavetor 0 9 5 printfPosicao d buscabinariavetor 0 9 11 printfPosicao d buscacomsentinelavetor 10 5 printfPosicao d buscacomsentinelavetor 10 11 include stdioh int buscacomsentinelaint valores int tamanho int valor int i 0 int posicao 1 valorestamanho valor do ifvaloresi valor posicao i break i while1 return posicao tamanho 1 posicao int buscabinariaint valores int inicio int fim int valor int meio if inicio fim return 1 else meio inicio fim 2 if valoresmeio valor return meio else if valoresmeio valor return buscabinariavalores inicio meio valor else return buscabinariavalores meio fim valor int main int vetor20 1 2 3 4 5 6 7 8 9 10 printfPosicao d buscabinariavetor 0 9 5 printfPosicao d buscabinariavetor 0 9 11 printfPosicao d buscacomsentinelavetor 10 5 printfPosicao d buscacomsentinelavetor 10 11 Comunicação Oral e Escrita 114 114 Você aprendeu que a busca sequencial com sentinela tem complexidade Olog n A otimização do código foi realizada pela inserção de um elemento com o valor buscado no final do array É claro que para isso ser possível é necessário ter espaço no array para essa inserção O objetivo é reduzir uma comparação que ocorre no final do laço checando se as comparações já chegaram ao final da lista de elementos Como um elemento do valor buscado foi inserido no final do array é de certeza que o valor será encontrado o que fará a busca sair do laço do array Dessa forma não é preciso se preocupar se a lista de elementos já chegou no final A otimização se deu pela redução de instruções para a busca sem alterar sua complexidade A quantidade de execuções das instruções no pior caso ou seja quando o elemento procurado não está na lista será de n vezes Agora o código da busca binária Para usar essa forma de busca a lista deve estar ordenada Com isso a estratégia é dividir a quantidade de elementos a serem pesquisados dividindo por dois a lista de elementos a cada iteração O pior caso é quando não há o elemento procurado na lista Considere então uma lista com 10 elementos Na primeira iteração a busca possui 10 elementos na segunda iteração 5 elementos na terceira iteração 2 elementos e na quarta iteração apenas 1 Se não for encontrado a função retorna 1 ou seja foram 4 iterações assim 40 dos elementos foram pesquisados no pior caso Agora imagine uma lista com 100 elementos Na primeira iteração são 100 elementos na segunda 50 elementos na terceira 25 elementos na quarta 12 elementos na quinta 6 elementos na sexta 3 elementos e na sétima 1 Não sendo encontrado retorna 1 Dessa forma em 100 elementos foram necessárias apenas 7 iterações ou seja apenas 7 dos elementos foram pesquisados Finalmente imagine uma lista com 1000 elementos Na primeira iteração são 1000 elementos na segunda 500 elementos na terceira 250 elementos na quarta 125 elementos na quinta 62 elementos na sexta 31 elementos na sétima 15 elementos na oitava 7 elementos na nona 3 elementos e na décima 1 elemento E não encontrando retorna 1 Com isso com somente 10 iterações uma lista de 1000 elementos é verificada ou seja 1 dos elementos Uma forma de saber o número de iterações necessárias é pelo logaritmo log2n por isso sua complexidade é Olog n Independentemente de quantas instruções existam no código a quantidade de vezes que eles serão executados reduz rapidamente com base na quantidade de elementos que a lista contenha 115 Comunicação Oral e Escrita 115 Contudo seu comportamento não é linear Assim uma lista com 1000 elementos que leve x tempo para executar não levará 5x tempo se a lista aumentar para 5000 Com esse exemplo fica mais claro a questão da complexidade algorítmica Dá para notar como a melhoria no código é capaz de reduzir a quantidade de iterações no algoritmo não é Encerramos esse assunto por aqui e até a próxima 117 Gostou do assunto Você pode aprender ainda mais sobre estruturas ordenação e busca buscando novos horizontes sites links aplicativos e livros Saiba mais lendo e conferindo os materiais a seguir Quero saber httpsptwikipediaorgwikiAlgoritmode ordenaC3A7C3A3o Algoritmos de ordenação No site sugerido há uma lista com os artigos de métodos de ordenação de vetores tanto de métodos simples como mais complexos Vale a pena conferir httpsptwikibooksorgwikiAlgoritmoseEstruturasde DadosAlgoritmosdeOrdenaC3A7C3A3o Algoritmos e estruturas de dados Este site complementa o que você já aprendeu sobre algoritmos de ordenação e estrutura de dados Acesseo em 118 httpseducapescapesgovbrbitstreamcapes2040882 LivroComputacaoPesquisa20e20Ordenacao20de20 Dadospdf httpswwwimeuspbrpfestruturasdedadosaulasst hashhtml httpswwwimeuspbrpfalgoritmosaulasbinthtml Pesquisa de ordenação de dados Tabela Hash Árvores Este material da Capes é um excelente complemento aos seus estudos Confira No site sugerido você pode conferir conceitos códigos e exercícios de tabela hash para complementar os seus estudos Acesse No site sugerido você pode conferir conceitos códigos e exercícios de árvores para complementar os seus estudos Acesse 119 httpswwwcsusfcaedugallesvisualizationBSThtml Animação interativa das funções da árvore No site sugerido você pode conferir conceitos códigos e exercícios de árvores para complementar os seus estudos Acesse 121 Agora é o momento de conferir um resumo dos principais conhecimentos aprendidos ao longo de seus estudos até aqui Este resumo foi elaborado em formato de checklist para que você assinale os itens que considera já ter desenvolvido e caso sinta a necessidade retome os estudos Aproveite mais esta oportunidade de construção de saberes Resumindo Identifiquei os métodos de ordenação Compreendi a diferença entre as estratégias de ordenação Entendi as vantagens e desvantagens dos diferentes métodos de ordenação Pratiquei a construção de ordenadores Identifiquei as formas de busca em estruturas de dados Construí programas de busca binária e sequencial Compreendi as formas de acesso a arquivos Construí programas para leitura e escrita em arquivo Compreendi características fundamentais de funções hash Entendi o tratamento de colisões em funções hash Criei estruturas que usam tabelas hash Entendi os conceitos envolvendo árvores Entendi o funcionamento das funções da árvore Criei árvores binárias de busca 123 Parabéns Você chegou ao final destes estudos Clique no recurso a seguir e explore o infográfico que preparamos para você Ele traz os principais conceitos e definições que foram abordadas no decorrer de toda essa importante jornada de construção de conhecimentos Esse é um breve resumo para você consultar sempre que sentir necessidade PARA CONCLUIR 125 125 Classificação Organização ou ordem em um conjunto de dados Classificação com estratégia de permutação É a classificação que usa a troca de posição dos elementos para poder classificar uma lista Classificação com estratégia de seleção É a classificação que usa uma busca para achar o elemento que deveria estar em uma posição e o troca com sua posição correta Classificação com estratégia de inserção É a classificação que usa uma busca para achar o elemento que deveria estar em uma posição e a insere em sua posição correta Classificação por divisão e conquista É a classificação que usa a constante divisão de uma lista até chegar na unidade e ir reorganizando os dados um a um até reconstruir a lista classificada Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca 126 126 Busca sequencial ou full scan É aquela que varre uma lista em busca do elemento requisitado podendo trazer a primeira ocorrência ou todas as ocorrências desse elemento Busca sequencial com sentinela É aquela que varre uma lista em busca do elemento requisitado usando como estratégia inserir o elemento buscado na primeira posição livre final da estrutura Com isso passa a não ser necessário verificar se chegou ao final da lista a cada iteração A desvantagem é que dessa forma não é possível pegar todas as ocorrências somente a primeira Busca binária É aquela que pode ser realizada desde que a lista já esteja previamente ordenada A ordenação permite que a busca seja dividida pela metade a cada iteração tornando este algoritmo muito eficiente Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca 127 Função hash Uma função hash é aquela capaz de gerar uma saída única para cada entrada diferente oferecida a ela Usamos esta função aqui para gerar índices para uma tabela na construção da tabela hash Tabela hash É uma estrutura especial que se beneficia da característica de uma função hash especialmente escolhida para o conjunto de dados que a tabela irá abrigar permitindo que ela possua funções de inserção consulta e remoção ótimas Colisão Chamamos colisão quando entradas diferentes geram a mesma saída de uma função hash Estratégias de tratamento de colisão As estratégias mais básicas de tratamento de colisão em tabelas hash são o endereçamento aberto e as listas encadeadas No endereçamento aberto em caso de colisão a função de inserção procura a primeira célula livre após o índice obtido pela função hash Em caso de listas encadeadas colisões são tratadas pela inserção do elemento ao final da lista encadeada do índice calculado pela função hash Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca Busca sequencial ou full scan É aquela que varre uma lista em busca do elemento requisitado podendo trazer a primeira ocorrência ou todas as ocorrências desse elemento Busca sequencial com sentinela É aquela que varre uma lista em busca do elemento requisitado usando como estratégia inserir o elemento buscado na primeira posição livre final da estrutura Com isso passa a não ser necessário verificar se chegou ao final da lista a cada iteração A desvantagem é que dessa forma não é possível pegar todas as ocorrências somente a primeira Busca binária É aquela que pode ser realizada desde que a lista já esteja previamente ordenada A ordenação permite que a busca seja dividida pela metade a cada iteração tornando este algoritmo muito eficiente Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca 128 Raiz da árvore É o nó na parte mais alta de uma árvore Nó pai É o nó que antecede outro nó Nó filho É o nó que sucede a outro nó Nó folha É o nó que não possui filhos Nó interno É o nó que possui pelo menos um filho Subárvore Cada nó de uma árvore Caminho de uma árvore É a sequência de nós resultante de uma navegação na árvore Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca 129 Grau do nó Referese a quantidade de subárvores que um nó pode possuir Nível da árvore É o número de nós presentes no caminho do nó até a raiz da árvore sendo que a raiz da árvore tem nível 0 Altura da árvore A altura ou profundidade da árvore é o tamanho do caminho mais longo entre a raiz e uma de suas folhas Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca Raiz da árvore É o nó na parte mais alta de uma árvore Nó pai É o nó que antecede outro nó Nó filho É o nó que sucede a outro nó Nó folha É o nó que não possui filhos Nó interno É o nó que possui pelo menos um filho Subárvore Cada nó de uma árvore Caminho de uma árvore É a sequência de nós resultante de uma navegação na árvore Confira agora um resumo dos principais conceitos abordados e retome sempre que sentir necessidade Estruturas ordenação e busca REFERÊNCIAS 130 ASCENCIO A F G ARAÚJO G S de Estruturas de dados algoritmos análise da complexidade e implementações em JAVA e CC São Paulo Pearson Prentice Hall 2010 BACKES A R Estrutura de dados descomplicada em linguagem C Rio de Janeiro Elsevier 2016 BHASIN H Algorithms Analysis and Designs New Delhi Oxford University Press 2015 FEOFILOFF P Algoritmos em linguagem C Rio de Janeiro Elsevier 2009 LOUDON K Dominando algoritmos com C Rio de Janeiro Editora Ciência Moderna 2000 HEINEMAN G T POLLICE G SELKOW S Algorithms in a Nutshell A Practical Guide 2 ed Graveinstein Highway North OReailly Media Inc 2016 KOFFMAN E B WOLFGANG P AT Data Structures Abstraction and Design Using Java 3 ed Danvers Wiley 2016 MORAES C R Estrutura de dados e algoritmos uma abordagem didática São Paulo Berkeley Brasil 2001 TANENBAUM A S Sistemas operacionais modernos São Paulo Pearson Education do Brasil 2016 SENAI