Pesquisa sobre Ordenação Interna e Algoritmos de Armazenamento

PESQUISA ORDENACAO E TECNICAS DE ARMAZENAMENTO UNIDADE 2 ORDENACAO INTERNA E ALGORITMOS DE ORDENACAO Andrea Karina Garcia 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 234 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento ee Introducao g A informacdo e o conhecimento s4o simultaneamente causa e efeito entre si A interacdo é dindmica e a sucessdo sua produdo pode ser plenamente invertida sem gerar nenhuma contradido proporcionando expansdo benéfica a ambos Portanto disponibilizar informagao é promover a geracdo de conhecimento COSTA e XAVIER 2010 Mas como a informacdo é registrada armazenada organizada selecionada e recuperada por suportes tecnoldégicos Uma instituido financeira banco por exemplo classifica os cheques pelos nimeros de conta de modo que possa preparar extratos bancarios individuais De maneira geral todas as empresas tém a necessidade de classificar seus dados muitas vezes em volumes macicos O verdadeiro propésito de um sistema de informacgado deve ser em termos dos usos dados a informacdo e dos efeitos resultantes desses usos nas atividades dos usuarios A funcdo mais importante do sistema seria a forma como a informaao modifica a realizacdo dessas atividades LE COADIC 1994 No Brasil o Marco Legal da Ciéncia Tecnologia e Inovado de acordo com Rocha 2018 traz novas possibilidades de interagdo entre a iniciativa privada e a Administracdo Publica com vistas ao aperfeicoamento dos modelos de organizaado interna das instituides de Ciéncia Tecnologia e Inovado ICTs Segundo o autor a adocdo de ferramentas computacionais adequadas possibilita a elucidaao das possiveis interpretagées sobre o contexto politico social e econdmico e permite identificar novos rumos para o desenvolvimento de projetos estratégicos nas mais diversas areas Os resultados assim poderao ser consolidados e analisados pelas instancias de planejamento estratégico das instituigdes que implementam as tais politicas ptiblicas Azevedo Junior e Campos 2008 apud ROCHA 2018 afirmam que quanto mais rapido um negocio puder alterar seus processos e o sistema de informaao os quais servem a ele de suporte mais preparado estara para reagir a eventos de concorréncia de mercado Os sistemas de informaao portanto compreendem requisito imprescindivel em um cenario cada vez mais dinamico Classificar dados é 0 ato de colocar os dados em uma ordem particular e especifica crescente ou decrescente E uma das aplicacédes mais importantes da computacdo Vale ressaltar desde ja que independentemente da classificacdo ou seja do algoritmo utilizado para classificar o array o resultado final sera o mesmo Sera a escolha do algoritmo seu tempo de execucdo e uso de memoria do programa que fardo a diferenga Nesta unidade vocé tera a oportunidade de aprender sobre formas de ordenacdo interna e as distintas possibilidades de escolha de algoritmos de ordenacdo tais como 1 Bolha 2 Inserdo 3 Selecao 4 Shellsort e Mergesort 5 Quicksort 6 Heaps Bindarios 7 Heapsort 8 Countingsort 9 Bucketsort e Radixsort Classificar dados é um problema instigante que demanda esforcos intensos de investimento financeiro e pesquisas cientificas Convido a vocé caro aluno a mergulhar neste segmento de universo fantastico da computacdo Bons estudos 21 Ordenagao interna Do ponto de vista da memoria do computador os algoritmos de ordenacdo podem ser classificados em COELHO FELIX s d httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 334 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Quando os dados a serem ordenados estao Quando os dados a serem ordenados na memoria principal necessitam de armazenamento em memoria auxiliar como o HD Quadro 1 Conceitos de ordenado Interna e Externa Fonte Elaborado pela autora 2019 PraCegoVer A figura mostra uma tabela de duas linhas e quatro colunas Na primeira linha temos coluna 1 Ordenagao Interna e coluna 2 Ordenado Externa Na segunda linha temos coluna 1 Quando os dados a serem ordenados estaéo na memoria principal e coluna 2 Quando os dados a serem ordenados necessitam de armazenamento em memOria auxiliar como o HD Quando os dados a serem ordenados estdo na memoria principal séo chamados de ordenagao interna Quando os dados a serem ordenados necessitam de armazenamento em memoria auxiliar como o HD sao chamados de ordenacdo externa Sendo assim esta unidade tera seu foco nos métodos de ordenacao interna 22 O problema da ordenacao Em um processo de selecdo de um algoritmo de ordenado interna vocé deve considerar os seguintes aspectos o tempo gasto pela ordenacdo e 0 uso econémico da memoria disponivel Segundo Menotti s d os métodos de ordenaao in situ sao os preferidos A expressdo in situ é usada na computaao para definir uma operacao que ocorre sem interromper o estado normal do sistema Ao mesmo tempo métodos que utilizam listas encadeadas nado s4o muito utilizados E para finalizar métodos que fazem codpias dos itens a serem ordenados tém menor importancia Sobre o critério de avaliagdo sendo n o numero de registros no arquivo as medidas de complexidade relevantes sao ainda de acordo com o autor numero de comparacées C n entre chaves numero de movimentacées M n de itens A classificagdo 6 um mecanismo que ordena os dados em uma ordem crescente ou decrescente com base em uma ou mais chaves de classificacdéo Por exemplo uma lista de nomes poderia ser classificada alfabeticamente contas bancarias poderiam ser classificadas pelo numero de conta registros de folhas de pagamento de funcionarios poderiam ser classificados pelo CPF e assim por diante typedef int ChaveTipo typedef struct ChaveTipo Chave outros componentes Item httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 434 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Outras caracteristicas importantes referemse a estabilidade relativa a manutendo da ordem original de itens de chaves iguais MENOTTI s d Em outras palavras um método de ordenaga4o é estavel se a ordem relativa dos itens com chaves iguais ndo se altera durante a ordenacdo MENOTTI s d Ressaltase que na ordenaao interna o arquivo a ser ordenado cabe todo na memoria principal Os métodos de classificagdo de ordenacdo interna sdo categorizados dessa forma Adequados para pequenos arquivos Métodos simples Requerem O n2 comparacées Produzem programas pequenos Adequados para arquivos maiores Requerem O n log n comparacées Métodos eficientes Usam menos comparacées As comparagdes sao mais complexas nos detalhes Métodos simples sao mais eficientes para pequenos arquivos Quadro 2 Classificagéo dos métodos de ordenaAo interna Fonte MENOTTI s d PraCegoVer A Figura mostra uma tabela com duas linhas e duas colunas Na primeira linha temos coluna 1 Método simples e na coluna 2 Adequados para pequenos arquivos Requerem On2 comparacées Produzem programas pequenos Na segunda linha temos coluna 1 Métodos eficientes e na coluna 2 Adequados para arquivos maiores Requerem O n log n comparacées Usam menos comparacées As comparaées sdo mais complexas nos detalhes Métodos simples sdo mais eficientes para pequenos arquivos Os algoritmos de ordenacdo podem ser aplicados a diversos tipos de estrutura tais como vetores matrizes e estruturas dinamicas COELHO FELIX s d Dois algoritmos simples de classificagao sdo classificacdo por selecdo e por insercao A classificagao por intercalagao é mais eficiente e ao mesmo tempo mais complexa 23 Introducao e exemplo dos algoritmos de ordenacao Bolha Insergao Selecao Shellsort Mergesort Quicksort e oe e Heaps Binarios Heapsort Countingsort Bucketsort e Radixsort Na sociedade contemporanea o acumulo de dados tornase um problema a cada dia mais complexo a ser resolvido Aprimorar o uso de algoritmos de ordenacdo que sdo processos ldégicos para se organizar uma determinada estrutura linear é imprescindivel AGUILAR 2018 Este estudo concentrara seus esforcos em trés deles dentre os diversos métodos expostos BubbleSort InsertionSort SelectionSort Didaticamente falando introduzem ideias que servem de base para outros métodos mais eficientes Esses métodos utilizam como uma de suas operaées basicas a comparacdo de elementos da lista ou seja o foco portanto é didatico e ndo por desempenho httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 534 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento 231 Bolha BubbleSort A classificagdo por bolha é um algoritmo de classificagao simples A ideia da ordenacdo por bolhas é flutuar o maior elemento para o fim por este motivo devese repetir n vezes a flutuacdo Bubble Sort é um algoritmo de ordenaao que pode ser aplicado em arrays e listas dinamicas Nesse método os elementos da lista séo0 movidos para as posides adequadas de forma continua assim como uma bolha movese num lfquido nas palavras de Cintra et al 2015 p 24 Se um elemento esta inicialmente numa posicdo i e para que a lista fique ordenada ele deve ocupar a posiao j ele tera que passar por todas as posicées entre i e j CINTRA NOBRE VIANA 2015 p 24 Ainda de acordo com os autores em cada iteracdo do método percorrese a lista partindo de seu inicio comparando cada elemento com seu sucessor trocandoos de posicdo se houver necessidade E possivel demonstrar que se a lista tiver n elementos apds no maximo n1 iteracées a lista estara em ordem O algoritmo BubbleSort percorre o vetor muitas vezes por isso nado é recomendado o uso para aplicagées que exigem velocidade ou tratem de uma grande quantidade de dados Acompanhe o exemplo abaixo baseado em Cintra et al 2015 p 24 ALGORITMO BOLHA ENTRADA UM VETOR L COM N POSICHES SAIDAE O VETOR L EM ORDEM CRESCENTE PARA 1 1 ate nm 1 PARA 3 ate nmii SE LEj LEjt1 AUX LEj SWAP LEj LEj1 LEjtid AUK FIM 60LHA PraCegoVer A Figura mostra um trecho de cddigo de 10 linhas de programa Enumerando cada linha temos Linha 1 ALGORITMO BOLHA Linha 2 ENTRADA UM VETOR L COM N POSICOES Linha 3 SAIDA O VETOR L EM ORDEM CRESCENTE Linha 4 PARA I 1 atén 1 Linha 5 PARAj0atén1I Linha 6 SE Lj Lj Linha 7 AUX Lj SWAP Linha 8 Lj Lj1 Linha 9 Lj1 AUX Linha 10 FIM BOLHA Primeiro sera realizada a troca 0 swap de elementos da lista Depois sera feito 0 swap usando o procedimento troca Assim a chamada troca Li Lj serve para trocar 0 contetido das posiées i e j do vetor L httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 634 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Percebese que ao final da primeira iteragdo do laco mais externo do algoritmo o maior elemento da lista estara na ultima posido do vetor Ao final da segunda iterado os dois maiores valores da lista estardo nas duas Ultimas posiées do vetor L em ordem crescente Ao final da iterado k do lago mais externo os k maiores valores da lista estarao nas k ultimas posides do vetor em ordem crescente Claramente instrudo critica do algoritmo bolha é a comparagao se Em cada iteracdo do laco mais interno é feita uma comparaao A complexidade temporal desse algoritmo pertence a O n2 Além dos parametros de entrada L e n 0 algoritmo utiliza apenas trés variaveis escalares i j e aux Dessa forma a quantidade extra de memoria utilizada por ele é constante Outro aspecto importante dos métodos de ordenacdo é a estabilidade Um método de ordenacdo é estavel se ele preserva a ordem relativa existente entre os elementos repetidos da lista Por exemplo se a ordenado da lista 4 7 6 7 2 resulta em 2 4 6 7 7 a ordenagao foi estavel Observe o contetido de um vetor apds cada iteragdo do laco mais externo no quadro a seguir DEBE Renee 9 45105 8 14 iteracgdo 4595 810 24 iteracao 45599 10 3a jteragao 4559 910 44 iteracao 4559910 5a iteracao 4559910 Quadro 3 Iteracdo com BubbleSort Fonte CINTRA NOBRE VIANA 2015 p 26 PraCegoVer A figura mostra uma tabela de 7 linhas e 7 colunas Na primeira linha temos coluna 2 0 coluna 3 1 coluna 4 2 coluna 5 3 coluna 6 4 coluna 7 5 Na segunda linha temos coluna 1 Lista Original coluna 2 9 coluna 3 4 coluna 4 5 coluna 5 10 coluna 6 5 coluna 7 8 Na terceira linha temos coluna 1 1 Iteragdol coluna 2 4 coluna 3 5 coluna 4 9 coluna 5 5 coluna 6 8 coluna 7 10 Na quarta linha temos coluna 1 2 Iteracdo coluna 2 4 coluna 3 5 coluna 4 5 coluna 5 9 coluna 6 9 coluna 7 10 Na quinta linha temos coluna 1 3 Iterado coluna 2 4 coluna 3 5 coluna 4 5 coluna 5 9 coluna 6 9 coluna 7 10 Na sexta linha temos coluna 1 4 Iteracgdo coluna 2 4 coluna 3 5 coluna 4 5 coluna 5 9 coluna 6 9 coluna 7 10 Na sétima linha temos coluna 1 5 Iteragdo coluna 2 4 coluna 3 5 coluna 4 5 coluna 5 9 coluna 6 9 coluna 7 10 De acordo com o exemplo acima no final da segunda iteraao a lista ja estava ordenada Na terceira iteracao nao houve nenhuma alteraao na lista Desse fato concluise que a lista ja estava em ordem de modo que as duas Ultimas iteragées foram inuteis Ha outras formas de implementar o algoritmo BubbleSort Entendendo o funcionamento desse cdédigo vocé podera implementalo de outras formas Alias podemos testar juntos a partir do VISUALGO httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 7134 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento SSS VOCE SABIA Os softwares educativos sao amplificadores de potencialidade na capacitagdo e aperfeicoamento Eles sao considerados programas educacionais quando projetados por meio de uma metodologia que os contextualizem no processo ensinoaprendizagem O VISUALGO é um exemplo disso nele vocé podera rodar exemplos de ordenacao por bolhas Entenda a teoria a partir da pratica E sé clicar neste link httpsvisualgonetptsorting httpsvisualgonetptsorting SSS As tecnologias de informacdo e comunicado propiciam trabalhar com investigacdo e experimentacdo do conteuido teérico ampliando a sua experiéncia de modo a fomentar e construir 0 seu proprio conhecimento 232 Inserdo InsertSort A classificacdo por insergao é um algoritmo de classificacdo simples A primeira iteracdo desse algoritmo seleciona 0 segundo elemento no array e se for menor que o primeiro elemento trocao pelo primeiro elemento A segunda iteragdo examina 0 terceiro elemento e 0 insere na posiao correta com relado aos dois primeiros elementos de modo que todos os trés elementos sejam na ordem Na iésima interacdo desse algoritmo os primeiros elementos i no array original serdo classificados Observe o exemplo abaixo conforme Deitel e Deitel 2015 p 644 Array 34 56 4 10 77 51 93 30 5 52 Um programa que implementa o algoritmo de classificacdo por insergdo analisara os dois primeiros elementos do array 34 e 56 Estes ja estado em ordem Portanto 0 programa continua Caso eles estivessem fora de ordem o programa iria permutalos Na proxima iteracdo o programa examina o terceiro valor que é o nimero 4 Esse valor é menor que 56 Portanto 0 programa armazena 4 e sendo assim move o 34 uma posido para a direita O programa agora alcangou o comeco do array colocando o 4 no zeroésimo elemento 4 34 56 10 77 51 93 30 5 52 Na proxima iterado o programa armazena 10 em uma variavel temporaria Entéo compara 10 a 56 e move o 56 uma posicao para a direita porque ele é maior que 10 O programa entaéo compara 10 com 34 movendo o 34 uma posiao para a direita Quando 0 programa compara 10 com 0 4 ele observa que 0 10 é maior que 0 4 eo coloca o 10 na posido 1 4 10 34 56 77 51 93 30 5 52 Usando esse algoritmo na iésima interado os primeiros elementos i do array sao classificados Contudo podem ainda nado estar nos locais finais Valores menores podem ser localizados mais tarde no array Sobre a implementacdo da classificacdo por insercdo a classe InsertionSortTest é composta pelos métodos descritos abaixo Clique e confira httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 834 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento O método static insertionSort que serve para classificar ints usando o algoritmo de classificagao por inserao O método static printPass que serve para exibir o conteudo do array depois de cada passagem Main para testar o método insertionSort httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 934 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1034 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1134 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1234 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento 68 69 fim da classe InsertionSortTest Unsorted array 34 96 12 87 40 80 16 50 30 45 after pass 1 34 96 12 87 40 80 16 50 30 45 after pass 2 12 34 96 87 40 80 16 50 30 45 after pass 3 12 34 87 96 40 80 16 50 30 45 after pass 4 12 34 40 87 96 80 16 50 30 45 after pass 5 12 34 40 80 87 96 16 50 30 45 after pass 6 12 16 34 40 80 87 96 50 30 45 after pass 7 12 16 34 40 50 80 87 96 30 45 after pass 8 12 16 30 34 40 50 80 87 96 45 after pass 9 12 16 30 34 40 45 50 80 87 96 Sorted array 12 16 30 34 40 45 50 80 87 96 Figura 1 Classificando um array com o método de inserao Fonte DEITEL 2015 p 644 e 645 PraCegoVer A Figura mostra um cddigo de 68 linha Enumerando cada linha temos Linha 1 Figura 195 InsertionSortTestjava Linha 2 Classificando um array com a classificaao por inserao Linha 3 import java Security SecureRandom Linha 4 import javautilArrays Linha 5 Linha 6 public class InsertionSortTest httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade2ebookindexhtml 1334 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 7 Linha 8 classifica 0 array utilizando a classificagao por inserao Linha 9 public static void insertionSortint data Linha 10 Linha 11 faz um loop sobre datalength 1 elementos Linha 12 for int next1 next datalength next Linha 13 Linha 14 int insert datanext valor a inserir Linha 15 int moveltem next local para inserir elemento Linha 16 procura o local para colocar o elemento atual Linha 17 procura o local para colocar o elemento atual Linha 18 procura o local para colocar o elemento atual Linha 19 Linha 20 desloca o elemento direito um slot Linha 21 datamoveltem datamoveltem 1 Linha 22 moveltem Linha 23 Linha 24 Linha 25 datamoveltem insert local do elemento inserido Linha 26 printPassdata next moveltem passagem de saida do algoritmo Linha 27 Linha 28 Linha 29 Linha 30 imprime uma passagem do algoritmo Linha 31 public static void printPassint data int pass int index Linha 32 Linha 33 Systemoutprintdafter pass 2d pass Linha 34 Linha 35 gera saida dos elementos até o item trocado Linha 36 for int0 i Linha 37 Systemoutprintf d datai Linha 38 Linha 39 Systemoutprintf Yd dataindex indica troca Linha 40 Linha 41 termina de gerar a saida do array Linha 42 For int iindex 1 i datalength i Linha 43 Systemoutprintfd datai Linha 44 Linha 45 Systemoutprintf Yon para alinhamento Linha 46 Linha 47 indica quantidade do array que é classificado Linha 48 forint i0 ipassi Linha 49 Systemoutprint Linha 50 SystemoutprintiIn Linha 51 Linha 52 Linha 53 public static void main String args Linha 54 Linha 55 SecureRandom generator new SecureRandom Linha 56 Linha 57 int data new int10 cria o array Linha 58 Linha 59 for int i0 idatalength i preenche o array httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1434 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 60 datai 10 deneratornextInt90 Linha 61 Linha 62 SystemoutprintfUnsorted array nsnn Linha 63 ArraystoStringdata exibe o array Linha 64 insertionSortdata classifica o array Linha 65 Linha 66 SystemoutprintfSorted array nsnn Linha 67 ArraystoStringdata exibe o array Linha 68 Descriao Linhas 9 a 28 declaram o método insertionSort Linhas 12 a 27 fazem um loop por itens datalenght 1 no array Linha 14 a cada iteracdo esta linha declara e inicializa a variavel insert que contém o valor do elemento que sera inserido na parte classificada do array Linha 15 declara e inicializa a variavel moveltem que monitora onde inserir 0 elemento Linhas 18 a 23 fazem um loop para localizar a posiao correta onde o elemento deve ser inserido O loop terminara quando o programa alcangar o inicio do array ou quando alcanar um elemento menor que o valor a ser inserido Linha 21 move um elemento para a direita no array Linha 22 decrementa a posicdo na qual inserir o proximo elemento Linha 25 depois do Joop terminar esta linha insere o elemento na posiao Linhas 31 a 51 a saida do método printPass utiliza tragos para indicar a parte do array que é classificada apéos cada passagem Um asterisco é colocado ao lado da posiao do elemento que foi trocado pelo menor emento nessa passagem O algoritmo de classificacdo por inserdo é executado no tempo O n A implementagao da classificagao por inserdo linhas 9 a 28 contém dois loops for linhas 12 a 27 itera datalenght 1 vezes inserindo um elemento na posido apropriada nos elementos classificados até 0 momento Para o propdsito desse aplicativo datalenght 1 é equivalente a n 1 comparaées Cada loop individual é executado no tempo O n DEITEL DEITEL 2015 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1534 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento SSS VOCE QUER VER Ao encerrar o segundo método de ordenagao vocé ainda esta com algumas dtvidas Assista ao video romeno de danga folclorica que traz uma demonstracdo sobre o algoritmo de insercdo Produzido pela Sapientia University e dirigido por Katai Zoltan e Toth Lazl6 O nome do canal é AlgoRythmics Tenho certeza de que vocé ira soluciona las depois de assistir esses videosHa outros videos interessantissimos sobre o tema Vale a pena conferir E s6 clicar neste link httpswwwyoutubecomwatch timecontinue35 vROalU37913U httpswwwyoutubecomwatch timecontinue35vROalU37913U O recurso audiovisual é uma importante ferramenta que proporciona o aprendizado por meio do lidico As possibilidades de ensino e aprendizagem se ampliam contribuindo para a sua compreensdo e assimilacdo dos contetidos Além de solucionar suas dividas sobre 0 assunto anterior ainda teve a oportunidade de assistir um video sobre 0 préximo assunto 0 método de Seleao 233 Seledo SelectionSort A classificacdo por selecdo é outro algoritmo de classificacdo simples Dentro de uma necessidade e escolha de classificagao em ordem crescente a primeira iteragdo selecionara o menor elemento no array permutando pelo primeiro elemento A segunda iteracdo selecionara 0 segundo menor item 0 menor dos elementos restantes de modo a trocalo pelo segundo elemento O algoritmo prosseguira em seu ritmo de trabalho até que a ultima iteracdo selecione o segundo maior elemento e permuteo pelo pentltimo indice deixando o maior elemento no ultimo indice Depois da iésima iteragdo os menores itens i do array serao classificados na ordem crescente nos primeiros elementos i do array Observe o exemplo abaixo conforme Deitel e Deitel 2015 p 641 Array 34 56 4 10 77 51 93 30 5 52 Um programa que implementa a classificacdo por selecdo primeiro determina o menor valor que 0 4 neste array 0 qual esta contido no indice 2 Entao 0 programa troca 4 por 34 resultando em 4 56 34 10 77 51 93 30 5 52 O programa depois disso determina o menor valor dos elementos restantes dentre todos menos o 4 Neste caso é0 5 presente no indice 8 Entao o programa troca 5 por 56 4 5 34 10 77 51 93 30 56 52 Na terceira iteracdo o programa determina o proximo menor valor que é 0 10 trocandoo pelo 34 4 5 10 34 77 51 93 30 56 52 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1634 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento O processo continua até que o array seja completamente classificado 4 5 10 30 34 51 52 56 77 93 Sendo assim compreendese que 0 menor elemento esta na primeira posido Depois da segunda iteracdo os dois menores elementos assumirdo de acordo com a ordem as duas primeiras posiées E assim por diante Sobre a implementacao da classificagao por selecado SelectionSortTest é composto pelos seguintes métodos ométodo static SelectionSort que serve para classificar um array int usando 0 algoritmo de classificagao por selecao ométodo static swap que serve para permutar os valores dos dois elementos do array ométodo static printPass que serve para exibir o conteudo do array depois de cada passagem e main para testar o método selectionSort No exemplo de pesquisa baseado em Deitel e Deitel 2015 a seguir 0 main linhas 57 a 72 cria um array de ints nomeados data preenchendoos com ints aleatérios no intervalo 10 a 99 Sendo assim a linha 68 testa o método selectionSort httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1734 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1834 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 1934 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2034 21082023 1626 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2134 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Figura 2 Classificando um array com o método de selecao Fonte DEITEL 2015 p 643 PraCegoVer A figura mostra um cédigo de 73 linhas programa Enumerando cada linhas temos Linha 1 Figura 194 SelectionSortTestjava Linha 2 Classificando um array com classificado por seleao Linha 3 import javasecuritySecureRandom Linha 4 import javautilArrays Linha 5 Linha 6 public class SelectionSortTest Linha 7 Linha 8 classifica 0 array utilizando a classificagado por selecdo Linha 9 public static void selectionSortint data Linha 10 Linha 11 faz um loop sobre datalength 1 elementos Linha 12 for int i 0 i datalength 1 i Linha 13 Linha 14 int smallest i primeiro indice do array remanescente Linha 15 Linha 16 faz um loop para localizar o indice do menor elemento Linha 17 for int index i 1 index datalength index Linha 18 if dataindex datasmallest Linha 19 smallest index Linha 20 Linha 21 swapdata i smallest troca o menor elemento na posido Linha 22 printPassi 1 smallest passagem de saida do algoritmo Linha 23 Linha 24 finaliza o método SelectionSort Linha 25 Linha 26 método auxiliar para trocar valores em dois elementos httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2234 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 27 private static void swapint data int first int second Linha 28 Linha 29 int temporary datafirst armazena o primeiro em temporario Linha 30 datafirst datasecond substitui o primeiro pelo segundo Linha 31 datasecond temporary coloca 0 temporario no segundo Linha 32 Linha 33 Linha 34 imprime uma passagem do algoritmo Linha 35 private static void printPassint data int pass int index Linha 36 Linha 37 Systemoutprintfafter pass 2d pass Linha 38 Linha 39 saida de elementos até item selecionado Linha 40 for int i 0 i index i Linha 41 Systemoutprintfd datai Linha 42 Linha 43 Systemoutprintfd dataindex indica troca Linha 44 Linha 45 termina de gerar a saida do array Linha 46 for int i index 1 i data length i Linha 47 Systemoutprintfd datai Linha 48 Linha 49 Systemoutprintfn para alinhamento Linha 50 Linha 51 indica quantidade do array que é classificado Linha 52 for int j 0 j pass j Linha 53 Systemoutprintf Linha 54 Systemoutprintln Linha 55 Linha 56 Linha 57 public static void mainString args Linha 58 Linha 59 SecureRandom generator new SecureRandom Linha 60 Linha 61 int data new int10 cria o array Linha 62 Linha 63 for int i 0 i datalength i preenche o array Linha 64 datai 10 generatornextInt90 Linha 65 Linha 66 SystemoutprintfUnsorted arraynsnn Linha 67 ArraystoStringdata exibe o array Linha 68 electionSortdata classifica o array Linha 69 Linha 70 SystemoutprintfSorted arrayYnsnn Linha 71 ArraystoStringdata exibe o array Linha 72 Linha 73 fim da classe SelectionSortTest Descriao Linhas 9 a 24 declaram o método selectionSort httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2334 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Linhas 12 a 23 fazem um loop datalenght 1 vezes Linha 14 declara a inicializagado para o indice i atual a variavel smallest a qual armazena o indice do menor elemento no array remanescente Linhas 17 a 19 fazem um loop sobre os elementos restantes no array Linha 18 para cada um desses elementos esta linha compara seu valor com o valor do menor elemento Linha 19 se o elemento atual for menor que o menor elemento esta linha atribui 0 indice do elemento atual a smallest Quando esse loop termina smallest contera o indice do menor elemento no array restante Linha 21 esta chama 0 método swap Linhas 27 a 32 0 método swap é demonstrado nas linhas 27 a 32 para colocar o menor elemento restante na proxima area ordenada do array Linhas 52 e 53 a saida do método printPass utiliza tracos para indicar a parte do array que é classificada apés cada passagem Linha 43 um asterisco é colocado ao lado da posido do elemento que foi trocado pelo menor emento nessa passagem A cada passagem o elemento ao lado do asterisco especificado na linha 43 e o elemento acima do conjunto de tracos mais a direita foram permutados O algoritmo de classificagao por selecdo é executado no tempo O n O método selectionSort linhas 9 a 24 tem dois loops for O loop externo linhas 12 a 23 itera pelos primeiros n 1 elementos do array e colocao menor item restante na sua posicdo classificada O loop interno linhas 17 a 19 itera por cada item no array restante em busca do menor elemento Esse loop é executado n 1 vezes durante a primeira iteragado do loop externo n 2 vezes durante a segunda iteraao e entdo n 3 e assim por diante O Joop interno ira iterar portanto um total de n n 1 2 ou n n 2 DEITEL DEITEL 2015 Agora convido vocé caro aluno a colocar em pratica seus conhecimentos Vamos 1a httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2434 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento a VAMOS PRATICAR e 1 Como os algoritmos de ordenacao podem ser classificados do ponto de memoria do computador Resolucao Os algoritmos de ordenacdo podem ser classificados da seguinte 1 ordenacdo interna quando os dados a serem ordenados estado na 1 principal ordenacdo externa quando os dados a serem ordenados ne de armazenamento em meméria auxiliar como o HD 20 que é 0 Bubbles Resolucao E um método de classificagio um algoritmo de classificagio simples A ordenacao por bolhas é flutuar o maior elemento para o fim Por este devese repetir n vezes a flutuacdo O Bubble Sort é um algoritmo de or que pode ser aplicado em arrays e listas dinamicas No caso de uma or decrescente por exemplo a posicdo atual dos elementos é comparad proxima posido Se a posicdo atual for maior que a posicao posterior é rez troca dos valores nessa posido Caso contrario nado é realizada a troca passase para o préximo par de comparaées O algoritmo Bubble Sort todo o vetor diversas vezes por isso nado recomendado o uso dé aplicagdes que requerem velocidade ou trabalhem com uma grande qu de dados 30 que é 0 SelectionSort Resolucao E um método de classificacao por selecdo um algoritmo de classificacao Dentro de uma necessidade e escolha de classificagdo em ordem cres primeira iteracdo selecionaraé o menor elemento no array permutan primeiro elemento A segunda iteragdo selecionara o segundo menor menor item dos elementos restantes de modo a trocalo pelo segundo e O algoritmo prosseguira em seu ritmo de trabalho até que a Ultima selecione 0 segundo maior elemento e permuteo pelo pentltimo indice d o maior elemento no ultimo indice Depois da iésima iteracdo os menore do array serdao classificados na ordem crescente nos primeiros elemen array reer e rere eee e erence Ao finalizar as atividades vocé teve a oportunidade de fixar 0 contetido e fortalecer sua memoria além de consolidar habitos de disciplina importantes para sua vida académica Parabéns httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2534 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento 234 MergeSort e ShellSort O MergeSort é um método baseado em uma estratégia de resolucgdo de problemas conhecida como divisdo e conquista CINTRA NOBRE VIANA 2015 p 32 Essa técnica consiste em decompor a instancia a ser resolvida em instancias menores do mesmo tipo de problema e por fim utilizar as solucdes parciais para obter uma solucao da instancia original Para que seja viavel aplicar essa técnica a um problema ele deve possuir duas propriedades estruturais ele precisa se decompor em qualquer instancia nao trivial do problema assim como em instancias menores do mesmo tipo de problema CINTRA NOBRE VIANA 2015 p 32 Segundo Lima et al 2017 p 172 o MergeSort é um algoritmo de ordenacdo mediano Devido a recursividade ser sua principal ferramenta seu melhor resultado é com relacdo as estruturas lineares aleatorias Entretanto ao tratar de estrutura pequena eou ja préordenada crescente ou decrescente a recursividade passa a ser uma desvantagem Essa peculiaridade faz com que o consumo de tempo de processamento seja alto e trocas desnecessarias sejam realizadas Portanto o algoritmo é indicado para aplicagdes com estruturas lineares em que a divisdo em estruturas menores sejam o objetivo Exemplo em filas para operac6es bancarias LIMA RICARTE SOUZA 2017 SSS VOCE O CONHECE John von Neumann foi quem em 1945 criou o algoritmo de ordenacao MergeSort Neumann foi um matematico hingaro de origem judaica que se naturalizou americano Contribuiu na Teoria dos Conjuntos Andalise Funcional Teoria Ergotica Mecanica Quantica Teoria dos Jogos Analise Numérica Hidrodinamica Estatistica Ciéncia da Computacio entre outras dreas E considerado um dos mais importantes matemiaticos do século XX O método Shell Sort segundo Cintra et al 2015 p 30 é um exemplo de algoritmo facil de descrever e implementar mas dificil de analisar E considerado uma extensdo do algoritmo de ordenacdo por inserao pois permite a troca de registros distantes um do outro Segundo Lima et al 2017 6 um dos métodos que mais apresenta resultados satisfatérios sobretudo com estruturas maiores e desorganizadas Por ser considerado uma melhoria do SelectionSort o ShellSort ao ser utilizado com as mesmas finalidades que seu predecessor recursos que demandem pouca escrita ira apresentar um melhor desempenho e consequentemente expandir a vida util dos recursos LIMA RICARTE SOUZA 2017 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2634 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento 235 QuickSort O algoritmo QuickSort é 0 método de ordenacdo interna mais rapido que se conhece para uma ampla variedade de situacées Provavelmente é 0 mais utilizado Possui complexidade C n O n log n no melhor e médio caso C n O n no pior caso Por esse motivo nao é um algoritmo estavel Bem como o Mergesort o Quicksort também é baseado na estratégia de divisdo e conquista de acordo com Cintra et al 2015 p 30 Com relacgdo a esse aspecto o que os diferencia é o fato de que enquanto no Mergesort a fase de divisao é trivial e a fase de conquista é trabalhosa no Quicksort acontece exatamente o contrario Basicamente a ideia do método é dividir um conjunto com n itens Ou seja dividilo em dois problemas menores Os problemas menores sdo ordenados independentemente e os resultados sdo combinados para produzir a solucdo final A operacdo do algoritmo divide sua lista de entrada em duas sublistas a partir de um piv6 Em seguida o mesmo procedimento nas duas listas menores até uma lista unitaria é realizado ee 236 Heaps Binarios O segredo do algoritmo Heapsort é uma estrutura de dados conhecida como heap httpswwwimeuspbrpfalgoritmos aulasfootnotesheaphtml que trata o vetor como uma arvore binaria Ha dois tipos estrutura maxheap e minheap FEOFILOFF 2018 Um heap é um vetor em que o valor de todo pai é maior ou igual ao valor de cada um de seus dois filhos Portanto um vetor v 1m é um heap se v f2 vif PraCegoVer A figura mostra uma comparacao de dois valores vf2 vf Obs paraf2m 1 2 3 4 5 6 T 8 9 10 11 12 13 14 999 888 77 555 666 777 555 222 333 444 111 333 666 333 Figura 3 Ilustrado de Vetor heap Fonte FEOFILOFF 2018 PraCegoVer A figura mostra um vetor de 14 posicdes contendo valores numéricos armazenados Na posido 1 tem 999 na posido 2 tem 888 na posido 3 tem 777 na posido 4 tem 555 na posido 5 tem 666 na posido 6 tem 777 na posiao 8 tem 222 na posiao 9 tem 333 na posiao 10 tem 444 na posiao 11 tem 111 na posiao 12 tem 333 na posiao 13 tem 666 e na posiao 14 tem 333 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2734 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento E uma operacdo relativamente facil rearranjar os elementos de um vetor de inteiros v 1m para que ele se torne um heap O processo deve ser repetido enquanto o valor de um filho for maior que o de seu pai Entdo trocamse os valores de pai e filho Assim um passo em direcdo a raiz é executado Mais precisamente enquanto vf2 vf faga troca vf2 vf e em seguida f f2 FEOFILOFF 2018 A operacdo de troca é definida assim define troca A B intt A A B B t Para implementar um heap binario usando vetor considere a seguinte estrutura portanto 1 armazenamento dos dados vetor 2 indicagao do tamanho do vetor 3 indicaao da ultima posiao utilizada pelo vetor 237 HeapSort O algoritmo HeapSort tem duas fases a primeira transforma o vetor em heap e a segunda rearranja o heap em ordem crescente Observe o esboco a seguir f Rearranja os elementos do vetor vEim1 ffs de mode que fiquem em ordem crescente void heapsort Cint my int vEI constroiHeap ny vi for Cint m r m 2 m treca vil vimI3 peneira m1 w Figura 4 Fases dos vetores Fonte FEOFILOFF 2018 PraCegoVer A figura mostra um trecho de cédigo de 12 linhas de programa Enumerando cada linha temos Linha 1 Rearranja os elementos do vetor v1n Linha 2 de modo que fiquem em ordem crescente Linha 3 Linha 4 void Linha 5 heapsort int n int v Linha 6 Linha 7 constroiHeap n v Linha 8 for int m n m 2 m Linha 9 troca v1 vm Linha 10 peneira m1 v httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2834 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 11 Linha 12 No inicio de cada iteraao do for valem as seguintes propriedades invariantes e ovetorv 1m um heap e vl1mvmt1n vmt1n esta em ordem crescente vln uma permutacao do vetor original A expressdo v 1m v m1n é uma abreviatura de todos os elementos de v 1m séo menores ou iguais a todos os elementos de v m1n Dessa forma observe FEOFILOFF 2018 1 heap m crescente N 88 77 66 55 44 33 22 11 00 99 99 99 99 99 Figura 5 Exemplo de HeapSort Fonte FEOFILOFF 2018 PraCegoVer A figura mostra um vetor de 14 posides com respectivos valores da esquerda para direita 88 77 66 55 44 33 22 11 00 99 99 99 99 99 Acima do nimero 77 tem o numero 1 acima do nimero 44 tem a palavra heap acima do numero 00 tem a letra m acima do segundo 99 tem a palavra crescente e por fim acima do ultimo 99 tem a letra N Segue dai que v 1n estara em ordem crescente quando m for igual a1 Portanto o algoritmo esta correto E por falar em correto caro aluno vocé ja pensou na importancia de problematizar suas aplicacées também no contexto social que vocé esta inserido httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 2934 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento ee VOCE QUER LER e Vocé estudante de um curso de tecnologia j4 parou para pensar na importancia de problematizar suas aplicagdes Admiravel mundo novo foi escrito pelo inglés Aldous Huxley em 1931 A estéria ambientada em Londres no ano de 2540 Ele antecipa questées relacionadas a tecnologia reprodutiva hipnopedia e manipulagcao psicoldgica A obra é considerada uma das 100 melhores do século XX a O Heapsort é portanto baseado no uso de heap binario Inicialmente sdo inseridos os elementos da lista num heap binario crescente Em seguida sao feitas sucessivas remocées do menor elemento do heap colocando os elementos removidos do heap de volta na lista Entao a lista estara em ordem crescente CINTRA e VIANA 2011 238 CountingSort BucketSort e RadixSort O CountingSort é um algoritmo de ordenaao estavel e de complexidade O n Basicamente 0 ele tem o objetivo de determinar para cada entrada x o numero de elementos menor que x Essa informacao pode ser usada para colocar o elemento x diretamente em sua posiao no array de saida Clique nas setas abaixo e aprenda mais sobre o tema O método BucketSort permite ordenar listas Para uma lista com n elementos é usado um vetor de ponteiros bucket com n posicées O maior elemento é indicado por k Cada posiao do bucket apontara para uma lista encadeada a partir da qual serdo inseridos os elementos da lista que pertencem ao intervalo i k 1 n i 1 k 1 n CINTRA NOBRE VIANA 2015 Quando o vetor contém valores que sdo uniformemente distribuidos o método tem complexidade considerada linear O n O RadixSort é um algoritmo de ordenacao rapido e estavel E um método que permite ordenar listas cujos elementos sejam comparados a cada dois Ele pode ser usado para ordenar itens identificados por chaves tnicas Cada chave é uma cadeia de caracteres ou numero e o RadixSort ordena estas chaves em qualquer ordem relacionada com a lexicografia A cada iteracdo ordenase a lista por uma de suas posi6es comecando pela posiao mais significante pois os elementos da lista devem ser representados como uma mesma quantidade de posiées httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 3034 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Por esse motivo é um algoritmo de ordenado que opera sobre inteiros processando digitos individuais CINTRA NOBRE VIANA 2015 O algoritmo BubbleSort de acordo com Silva apud LIMA et al 2017 p 172 apesar de ser 0 de mais facil implementacao nado apresenta resultados satisfatérios principalmente no numero de comparacoées A ineficiéncia do algoritmo devese ao grande consumo de processamento 0 que para maquinas com poucos ou limitados recursos computacionais resulta em lentiddo e longos periodos de espera Sua aplicaao é na opinido dos autores indicada somente para fins educacionais SILVA apud LIMA RICARTE SOUZA 2017 O SelectionSort é em estruturas lineares no entanto com o numero de elementos consideravelmente maior do que o InsertSort O numero de trocas é bastante inferior ao nimero de comparacées consumindo mais tempo de leitura e menos de escrita A vantagem de seu uso ocorre quando se trata de componentes em que quanto mais se escreve ou reescreve mais se desgasta e consequentemente perdem sua eficiéncia como é 0 caso das memorias EEPROM FLASH apud LIMA RICARTE SOUZA 2017 Segundo Lima et al 2017 p 172 o InsertionSort é util para estruturas lineares pequenas geralmente entre 8 e 20 elementos E amplamente utilizado em sequéncias de 10 elementos tendo listas ordenadas de forma decrescente como pior caso listas em ordem crescente como o melhor caso Sua principal vantagem é 0 pequeno numero de comparacées O excessivo numero de trocas é a sua desvantagem Para concluir 0 InsertionSort e o SelectionSort de acordo com Lima et al 2017 p 172 sao mais utilizados em associado com outros algoritmos de ordenacdo como os MergeSort QuickSort e 0 ShellSort os quais tendem a subdividir as listas a serem organizadas em listas menores fazendo com que sejam mais eficientemente utilizados Agora convido vocé caro aluno a colocar em pratica seus conhecimentos Vamos 1a httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 3134 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento a VAMOS PRATICAR e 1 Como funciona o MergeSort Resolucao O Mergesort é um exemplo de algoritmo de ordenado que faz uso da e dividir para conquistar E um método estavel e possui complexidade C n log n para todos os casos Esse algoritmo divide 0 problema em menores de modo a resolver um pedacgo de cada vez juntando de resultados O vetor é dividido em duas partes iguais cada qual divididas partes iguais novamente e assim por diante até ficar um ou dois elemen ordenacao é trivial Para reunir as partes ordenadas os dois elementos parte sao separados e 0 menor deles é retirado de sua parte Em seg inferiores entre os restantes sdo comparados Prosseguese assim até todas as partes 2 E facil de implementar o ShellSort Resolucao O método ShellSort um exemplo de algoritmo facil de descrever e impk mas dificil de analisar E uma extensdo do algoritmo de ordenagao por i Ele permite a troca de registros distantes um do outro diferentem algoritmo de ordenacao por inserdo que possui a troca de itens adjacen determinar o ponto de insercao E um método n4o estavel 3 Descreva 0 mecanismo de funcionamento do QuickSort Resolucao Basicamente a ideia do método é dividir um conjunto com n itens dividilo em dois problemas menores Os problemas menores sao or independentemente e os resultados sdo combinados para produzir a final A operacgdo do algoritmo divide sua lista de entrada em duas sub partir de um pivé Em seguida 0 mesmo procedimento nas duas listas r até uma lista unitaria é realizado ee Ao finalizar as atividades vocé teve a oportunidade de fixar 0 contetido e fortalecer sua memoria além de consolidar habitos de disciplina importantes para sua vida académica Parabéns Sintese httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 3234 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento Ao longo dessa unidade vocé aprendeu que classificar dados é 0 ato de colocar os dados em uma ordem particular e especifica crescente ou decrescente que é uma das aplicagées mais importantes da computaao Aprendeu ainda que independentemente da classificagdo do algoritmo utilizado para classificar 0 array o resultado final sera o mesmo entretanto sera a escolha do algoritmo bem como seu tempo de execucdo e uso de memoria do programa que fardo a diferenca Nesta unidade vocé teve a oportunidade de entender o conceito de ordenacdo que é a operacao de rearranjar os dados disponiveis em uma determinada ordem A eficiéncia no manuseio desses dados pode ser aumentada se eles estiverem dispostos de acordo com algum critério de ordem conhecer os métodos de classificacdo interna que do ponto de vista da memoria do computador podem ser classificados em ordenagao interna e ordenaao externa estes classificados em métodos simples e métodos eficientes compreender as principais diferengas entre os algoritmos de ordenacao 1 Bolha 2 Insercao 3 Selecao 4 Shellsort e Mergesort 5 Quicksort 6 Heaps Binarios 7 Heapsort 8 Countingsort 9 Bucketsort e Radixsort Clique para baixar o contetido deste tema Bibliografia AGUILAR L J Fundamentos de programagcao algoritmos estruturas de dados e objetos 3 ed Porto Alegre AMGH 2018 CINTRA G FE NOBRE R H VIANA G V R Pesquisa e ordenacao de dados 2 ed Fortaleza Editora UECE 2015 CINTRA G F VIANA G V R Pesquisa e ordenacao de dados Fortaleza UECE 2011 COELHO H FELIX N Métodos de ordenacado 1 39 slides s d Disponivel em httpwwwinfufgbrhebertdiscaed1AED104ordenacao1pdfhttpwwwinfufgbrhebertdiscae d1AED104ordenacao1pdf httpwwwinfufgbrhebertdiscaed1AED104ordenacao1pdf Acesso em 14092019 COSTA R O Xavier R C M Relagées mutuas entre informado e conhecimento 0 mesmo conceito Ciéncia da Informagao Brasilia DF v 39 n 2 p7583 maioago 2010 Disponivel em httpwwwscielobrpdfciv39n206pdfhttpwwwscielobrpdfciv39n206pdf httpwwwscielobrpdfciv39n206pdf Acesso em 14092019 DEITEL P DEITEL H Java como programar 8 ed Sdo Paulo Pearson 2015 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 3334 21082023 1626 Pesquisa Ordenagao e Técnicas de Armazenamento FEOFILOFF P Heapsort IME Instituto de Matematica e Estatistica USP Universidade de Sado Paulo 2018 Disponivel em httpswwwimeuspbrpfalgoritmos aulashpsrthtmlhttpswwwimeuspbrpfalgoritmos aulas hpsrthtm httpswwwimeuspbrpfalgoritmosaulas hpsrthtml Acesso em 14092019 HUXLEY AL Admiravel Mundo Novo Sado Paulo Abril Cultural 1982 INSERTSORT WITH ROMANIAN FOLK DANCE Criado por Sapientia University Tirgu Mures Marosvasarhely Romania Dirigido por Katai Zoltan and Toth Laszl6 403 min Disponivel em httpswwwyoutubecomwatchtimecontinue35vROalU37913Uhttpswwwyoutubecomwatch timecontinue35vROalU37913U httpswwwyoutubecomwatch timecontinue35vROalU37913U Acesso em 14092019 LE COADIC Y F A Ciéncia da Informagao Brasilia Briquet de Lemos 1994 LIMA N C A RICARTE J V G SOUZA J E G Algoritmos de ordenagao um estudo comparativo Anais do Encontro de Computacao do Oeste Potiguar Pau dos FerrosRN v 1 p 166173 jun 2017 ECOP Encontro de Computaao do Oeste PotiguarUFERSA Universidade Federal Rural do Semiarido 2017 Disponivel em httpsperiodicosufersaedubrindexphpecophttpsperiodicosufersaedubrindexphpecop httpsperiodicosufersaedubrindexphpecop Acesso em 1492019 MENOTTI D Algoritmos e estrutura de dados Departamento de Informatica Universidade Federal do Parana s d 26 slides Disponivel em httpswebinfufprbrmenottici05620152 1slides aulaO RDSimplespdfhttpwwwinfufprbrcursos ci055livroalg1pdf httpwwwinfufprbrcursosci055livroalg1pdf Acesso em 14092019 ROCHA C E A L Desenvolvimento de sistema de informacdo para apoio a gestdo de projetos em sintonia com o marco legal da ciéncia tecnologia e inovaao Tese Parana Programa de PésGraduado em Engenharia Elétrica e Informatica Universidade Federal do Parana 2018 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade2ebookindexhtml 3434