Capítulo 2: Algoritmos de Ordenação

Capítulo 2 Algoritmos de Ordenação 1 Introdução Ordenar é um problema clássico da Computação Formalmente consiste em obter uma permutação de uma sequência de elementos na qual cada elemento é sucedido por um de grandeza maior No mundo real frequentemente precisamos ordenar dados ordenar os livros pelo nome ordenar pessoas pela data de nascimento ordenar os alunos pela nota da prova etc Logo o problema de ordenação ainda hoje é um problema bastante relevante Durante o estudo dos algoritmos de ordenação normalmente usamos números para demonstrar o funcionamento desses algoritmos Entretanto destacase que a adaptação dos algoritmos para ordenar datas ou palavras é bastante simples Existem vários algoritmos que podem ser usados para ordenar e esses algoritmos podem ser classificados de diversas formas A classificação mais difundida desses algoritmos leva em consideração a ideia que é utilizada para ordenar os elementos Assim normalmente os algoritmos de ordenação são classificados como sendo do tipo troca seleção inserção intercalação e distribuição 2 Algoritmos do tipo troca A ideia básica dos algoritmos do tipo troca é logicamente trocar as posições de elementos que não estão ordenados Considere por exemplo uma sequência de números qualquer Um algoritmo de ordenação do tipo troca seleciona utilizando algum critério particular dois elementos dessa sequência E em seguida esses elementos são comparados de alguma forma Caso os elementos que foram escolhidos não estejam ordenados corretamente eles trocam de posição entre si Os algoritmos mais conhecidos do tipo troca são o Bubble Sort também conhecido como Bolha e o Quicksort também conhecido como ordenação por partição 21 Bolha Bubble Sort 211 Funcionamento O algoritmo Bolha realiza a ordenação de uma sequência por meio de comparações consecutivas entre elementos vizinhos Com o passar das repetições a ideia é que elementos mais leves menores sejam empurrados para o começo da sequência enquanto elementos mais pesados sejam empurrados para o final da sequência O nome do processo faz analogia as bolhas que surgem no fundo do oceano que por serem mais leves se deslocam do fundo até a superfície Para demonstrar o funcionamento do Bolha considere a sequência de números abaixo 5 3 1 2 4 O algoritmo em questão realiza a comparação entre elementos vizinhos do início até o final da sequência No caso da sequência acima a primeira comparação seria entre 5 e 3 A comparação testa se o elemento que vem antes na sequência é de grandeza menor do que vem depois O objetivo é verificar se esses dois elementos específicos encontramse ordenados dentro da sequência 5 3 1 2 4 Não Caso o teste resulte em falso os elementos devem então ser trocados de posição pois isso significa que eles não estão na ordem correta Caso o teste resulte em verdadeiro nada acontece Conforme se pode perceber para os elementos da nossa sequência o teste em questão resultaria em falso o que levaria os elementos a terem suas posições trocadas Assim nossa sequência passaria a ser 3 5 1 2 4 Em seguida o processo se repetirá para os próximos dois vizinhos 3 5 1 2 4 Não 3 1 5 2 4 1 e 5 trocam de posição 3 1 5 2 4 Não 3 1 2 5 4 2 e 5 trocam de posição 3 1 2 5 4 Não 3 1 2 4 5 4 e 5 trocam de posição Após todas as comparações o vetor ainda não se encontra ordenado Isso porque é preciso repetir esse processo mais algumas vezes Quantas vezes O número de elementos vezes Para nossa sequência com cinco números é preciso repetir o processo de comparação entre vizinhos cinco vezes A próxima iteração repete as comparações a partir do princípio do vetor 3 1 2 4 5 Não 1 3 2 4 5 1 e 3 trocam de posição 1 3 2 4 5 Não 1 2 3 4 5 2 e 3 trocam de posição 1 2 3 4 5 Sim Logo não acontece nada 1 2 3 4 5 Sim Logo não acontece nada Agora o vetor encontrase ordenado entretanto como o algoritmo da Bolha não sabe disso ele repetirá todo o processo de comparação entre vizinhos mais três vezes 212 Pseudocódigo Para muitos programar é algo extremamente complexo Traduzir um processo como o do código bolha pode parecer uma missão impossível mas de fato não é Na verdade é bastante simples Vamos começar com o ciclo interno do algoritmo Como seria um laço para comparar elementos que são vizinhos O Quadro 1 responde essa pergunta forint i 0 ivetorlength1 i if vetori vetori1 int auxiliar vetori vetorivetori1 vetori1 auxiliar Quadro 1 Um trecho do Algoritmo Bolha Vale observar que o laço apresentado no Quadro 1 para realizar a comparação entre vizinhos vai se repetir enquanto ivetorlength1 Isso é importante para que o laço não estoure os limites dos índices do vetor visto que se compara um elemento vetori com quem vem a frente dele vetori1 Agora como se poderia fazer para garantir que esse trecho de código seja repetido a quantidade de elementos do vetor vezes Simples basta colocar o trecho inteiro dentro de outro laço que vai se repetir quantidade de elementos do vetor vezes1 void bubbleSortint vetor forint j 1 j vetorlength j forint i 0 ivetorlength1 i if vetori vetori1 int auxiliar vetori vetorivetori1 vetori1 auxiliar endif endfor endfor endfuncao Quadro 2 Código Completo do Algoritmo Bolha É importante destacar que os Algoritmos de Ordenação possuem variações Logo o próprio Bolha poderia ser programado de outras formas Essas variações consistem não somente na utilização de outras estruturas de programação mas também em otimizações que tornem o código mais eficiente O que faz todas essas variações continuarem sendo o Bolha é a ideia de realizar ordenação com base na comparação de elementos vizinhos Na demonstração de funcionamento apresentada na seção anterior Ao final da primeira iteração das comparações o maior número da sequência estará na última posição da mesma forma ao final da segunda interação o segundo maior número estará na penúltima posição E assim sucessivamente Na prática não haveria mais necessidade de realizar comparações com o número que ficou no final na iteração passada Dessa forma há por exemplo uma otimização do Bolha que vai excluindo esses elementos das próximas iterações2 Além disso no exemplo apresentado na seção anterior acabam acontecendo varias comparações desnecessárias após o vetor já estar ordenado Por essa razão há outra variação onde ao se identificar que a sequência já se encontra ordenada o algoritmo interrompe sua 1 O contador desse laço poderia começar em zero e rodar enquanto for menor que a quantidade de elementos do vetor ou começar em um e rodar enquanto for menor ou igual a quantidade de elementos do vetor Fica a seu critério usar a forma que tenha maior familiaridade 2 No algoritmo ilustrado no Quadro 2 bastaria substituir a condição do segundo laço ivetorlength1 por ivetorlengthj Isso eliminaria a cada repetição um número crescente de elementos execução3 Sendo essa variação inclusive a mais eficiente versão do algoritmo Bolha 213 Análise da Complexidade Como se pode perceber pelo código completo apresentado no Quadro 2 o Bolha é um algoritmo com um laço dentro do outro onde os dois dependem do tamanho da entrada no caso do tamanho do vetor Isso significa que o Bolha é um algoritmo de custo quadrático mais precisamente Entretanto a variação mais eficiente do algoritmo no melhor caso quando o vetor recebido já se encontra ordenado pode alcançar um tempo de execução linear Normalmente o Bolha é considerado um algoritmo extremamente ineficiente 22 Quick Sort O Quick Sort também é um algoritmo do tipo troca entretanto diferente do Bolha ele é considerado um dos melhores algoritmos de ordenação em outras palavras um algoritmo de ordenação que apresenta ótimos tempos de execução em grande parte dos casos A ideia básica do Quick Sort é dividir a sequência em duas partes Para isso escolhese um número para fazer o papel de pivô e assim à esquerda da sequência ficarão os números que são menores que esse pivô enquanto que a direita da sequência se concentrarão os números que são maiores que esse pivô Existem diversas estratégias para se escolher o pivô Podese por exemplo adotar o primeiro elemento da sequência como pivô ou ainda a média do primeiro elemento da sequência e o último o pivô não necessariamente precisa fazer parte da sequência A eficiência do Quick Sort está intrinsicamente ligada à escolha desse pivô Um bom pivô é o que vai dividir a sequência em duas partes de tamanho próximo mediana Um péssimo pivô seria escolher o menor ou maior número da sequência 221 Funcionamento Considere que desejamos ordenar a sequência a seguir utilizando o Quick Sort também conhecido como ordenação por partição 3 No algoritmo ilustrado no Quadro 2 seria necessário trocar o laço externo por outro Criarseia uma variável booleana para testar se ocorreu alguma troca na iteração do laço mais interno Antes da execução do laço interno essa variável passaria para o valor falso Caso se entrasse no laço interno essa variável passaria para o valor verdadeiro O laço interno deve ser repetido enquanto continuar havendo alguma troca 5 3 1 8 6 7 4 2 O 1º passo para realizar a ordenação da sequência é escolher uma estratégia para calcular o pivô e identificalo Considere que vamos usar como o pivô a média do primeiro e do último elemento da sequência também não vamos realizar o arredondamento desse número4 Dessa forma o primeiro pivô seria 35 Em seguida colocamos dois marcadores no vetor Na demonstração vamos chamar os marcadores de E e D O E é colocado na extremidade mais esquerda da sequência no primeiro elemento O D é colocado na extremidade mais a direita da sequência no último elemento 5 3 1 8 6 7 4 2 E D O marcador E vai se deslocar para frente na sequência parando apenas quando ele estiver em um elemento que seja maior ou igual ao pivô No exemplo apresentado 5 é maior que 35 logo o E ficará parado O marcador D vai se deslocar para trás na sequência parando apenas quando ele estiver em um elemento que seja menor ou igual ao pivô No exemplo apresentado 2 é menor que 35 logo o D ficará parado também Após E e D terem parado devese observar se eles já se cruzaram na sequência No exemplo apresentado eles ainda não se cruzaram Quando eles não se cruzaram que é o caso devemse trocar os elementos que estão na posição E e D de lugar além de avançar o E uma posição par frente e jogar o D uma posição para trás 5 3 1 8 6 7 4 2 E D 2 3 1 8 6 7 4 5 E D 2 3 1 8 6 7 4 5 E D Após a troca e a atualização dos marcadores caso E e D ainda não tenham se cruzado repetese todo o processo considerando o mesmo valor de pivô 4 Importante destacar que ao longo da execução do Quick Sort serão escolhidos outros pivôs usando a mesma estratégia A opção por não arredondar o número encontrado é uma escolha pessoal quem está demonstrando o funcionamento pode optar por arredondar ou não Nosso vetor agora se encontra nessa situação 2 3 1 8 6 7 4 5 E D O marcador E deve avançar até encontrar um elemento maior ou igual ao pivô Como 3 não é maior ou igual ao pivô o E vai para frente parando no 1 2 3 1 8 6 7 4 5 E D Só que 1 também não é maior ou igual ao pivô Assim o E continua a ir par frente parando na posição onde está o 8 2 3 1 8 6 7 4 5 E D Agora o marcador E está em uma posição com um elemento maior ou igual ao pivô Parase o avanço do E e iniciase o processo de atualização do D que atualmente está marcando o 4 O D deve se deslocar para trás até parar em um elemento que seja menor ou igual ao pivô 4 não é menor que 35 logo o D vai se deslocar uma casa para trás 2 3 1 8 6 7 4 5 E D 7 também não é menor ou igual ao pivô logo o D vai continuar a se deslocar para trás 2 3 1 8 6 7 4 5 E D 6 também não é menor ou igual ao pivô logo o D vai continuar a se deslocar para trás 2 3 1 8 6 7 4 5 E D E e D estão na mesma posição mas isso não é um problema Além disso o processo de atualização do D ainda não acabou 8 não é menor ou igual ao pivô Logo o D vai continuar a se deslocar para trás chegando ao 1 2 3 1 8 6 7 4 5 D E Nesse momento o D está em uma posição com um elemento menor ou igual ao pivô que é 35 Após E e D terem parado devese observar se eles já se cruzaram na sequência Caso eles não tivessem se cruzado os elementos da posição E e D trocariam de lugar Entretanto no exemplo apresentado eles se cruzaram Quando E e D se cruzam devese dividir a sequência que se quer ordenar em duas partes 1 uma parte que começa no início da sequência e vai até a posição D e 2 outra parte que começa na posição E e vai até o final da sequência Em outras palavras isso significa que agora desejamos ordenar duas sequências Essa 2 3 1 E essa 8 6 7 4 5 E vamos continuar usando o Quick Sort para ordenar essas duas partes Antes de continuar notese que a primeira parte da sequência a parte esquerda contém apenas elementos que são menores ou iguais ao pivô enquanto que a segunda parte a parte mais a direita contém apenas elementos que são maiores ou iguais ao pivô Essa é uma forma de se confirmar que se está aplicando o algoritmo corretamente Considerando a primeira sequência o novo pivô será 15 Colocamse então os dois marcadores de novo E e D em suas posições iniciais respectivamente no início e no final da sequência 2 3 1 E D O marcador E para no elemento que é maior ou igual ao pivô Nesse caso ele continua na posição onde está o 2 O Marcador D para no elemento que é menor ou igual ao pivô Nesse caso ele continua na posição onde está o 1 2 3 1 E D Como E e D não se cruzaram ainda o algoritmo troca os elementos nessas posições de lugar além de levar o E uma casa para frente e trazer o D uma casa para trás 2 3 1 E D 1 3 2 E D 1 3 2 E D Como E e D não se cruzaram ainda o processo continua Entretanto o marcador do E já se encontra numa posição maior ou igual ao pivô O D entretanto vai andando para trás até alcançar uma posição com um elemento menor ou igual ao pivô Isso fará com que o marcador D pare na posição onde está o 1 1 3 2 D E Nessa situação E e D se cruzaram Logo os elementos não trocam de posição A sequência é dividida em duas partes e o Quick Sort é aplicado para essas partes A primeira parte será 1 E a segunda parte será 3 2 Para a sequência com apenas um elemento o Quick Sort considerará que ela já se encontra ordenada Para a sequência com dois elementos entretanto todo o processo é repetido Dessa forma começase calculando quem será o pivô que no caso será 25 O marcador E será posto no primeiro elemento da sequência e o marcador D no último 3 2 E D O marcador E deve se mover para frente até parar em um elemento que seja maior ou igual ao pivô Ele se encontra onde está o 3 que é maior ou igual ao pivô 25 logo o marcador E não se move O marcador D deve se mover para trás até parar em um elemento que seja menor ou igual ao pivô Ele se encontra onde está o 2 que é menor ou igual ao pivô 25 logo o marcador D não se move Então observase se os dois marcadores já se cruzaram Caso eles tenham se cruzado repetese o Quick Sort para as duas subsequências resultantes No exemplo eles não se cruzaram ainda Então os elementos da posição E e D trocam de lugar após essa troca o marcador E avança uma casa e o marcador D retrocede uma casa 3 2 E D 2 3 E D 2 3 D E Nesse momento caso D e E não tenham se cruzado repetese o processo No exemplo acima os marcadores se cruzaram Assim deve se repetir o Quick Sort para as duas novas subsequências Essa 2 E essa 3 Essas subsequências já estão ordenadas pois têm tamanho um Dessa forma a subsequência composta por 2 3 1 encontrase totalmente ordenada restando utilizar o Quick Sort para a subsequência 8 7 6 4 5 Resumindo o algoritmo do Quick Sort segue os seguintes passos 1 escolhese um pivô 2 utilizase um marcador E para a partir do início encontrar um elemento que seja maior ou igual ao pivô 3 utilizase um marcador D para a partir do final encontrar um elemento que seja menor ou igual ao pivô 4 quando E e D param de se mover observase se eles já se cruzaram 5 caso não tenham se cruzado os elementos da posição E e D trocam de lugar depois o marcador E se move uma casa para frente e o marcador D se move uma casa para trás caso após essa atualização das posições do marcador E e D eles continuem a se cruzar o processo se repete a partir da etapa 3 6 caso tenham se cruzado dividese a sequência em duas partes uma do início até o marcador D e outra do marcador E até o final e aplicase o Quick Sort para essas duas partes Exercício Demonstre o funcionamento do Quick Sort para o restante da sequência utilizada no exemplo acima 8 7 6 4 5 222 Pseudocódigo O Quick Sort é um método programado de forma recursiva Para funcionar recursivamente são necessários três parâmetros de entrada o vetor a ser ordenado um valor inteiro para marcar o índice inicial da sequência e um valor inteiro para marcar o índice final da sequência void quicksortint v int i int f A primeira etapa do método recursivo deve ser calcular qual será o pivô Suponhase que se considere como pivô a média do primeiro e do último elemento como no exemplo da seção anterior int pivo vi vf2 Após o cálculo do pivô inicializamse os marcadores E e D No algoritmo eles são valores inteiros que começam respectivamente com o valor do índice inicial e final do vetor int e i int d f Em seguida começase o processo de atualização desses contadores Esse processo deve acontecer dentro de um laço que vai se repetir enquanto os marcadores não se cruzarem No algoritmo os marcadores se cruzam quando o valor de E fica maior que o valor D isso acontece porque o E incrementou tanto e o D decrementou tanto que o valor do E passa o do D while e d continua Quadro 3 Trecho do Algoritmo Quick Sort parte 1 Dentro do laço acontecerão as atualizações dos marcadores O marcador E vai continuar incrementando enquanto ele estiver numa posição onde está um elemento menor que o pivô parando quando ele estiver numa posição onde está um elemento maior ou igual ao pivô Além disso é importante conter o incremento do marcador dentro do limite superior dos índices do vetor while e d while e f ve pivo e continua Quadro 4 Trecho do Algoritmo Quick Sort parte 2 O marcador D vai continuar decrementando enquanto ele estiver numa posição onde está um elemento maior que o pivô parando quando ele estiver numa posição onde está um elemento menor ou igual ao pivô Além disso é importante conter o decremento do marcador dentro do limite inferior dos índices do vetor while e d while e f ve pivo e while d i vd pivo d continua Quadro 5 Trecho do Algoritmo Quick Sort parte 3 Para que o fluxo do código continue os laços devem ter as condições de paradas atendidas Isso aconteceu por uma dessas duas razões 1 os marcadores se cruzaram ou 2 os marcadores encontraram elementos que devem ser trocados de lugar Para descobrir se os elementos devem ser trocados de posição testase novamente se o marcador E ainda é menor ou igual ao contador D Caso sejam os elementos são trocados e os marcadores são atualizados while e d while e f ve pivo e while d i vd pivo d if e d int aux ve ve vd vd aux e d endif Quadro 6 Trecho do Algoritmo Quick Sort parte 4 O fluxo do código volta então para o laço mais externo onde se testará se os marcadores devem continuar sendo atualizados ou não Caso o laço pare devese executar o Quick Sort para as duas subsequências uma que vai do início até o marcador D e outra que vai do marcador E até o final mas apenas se essas subsequências tiverem mais de um elemento if e f quicksortv e f if d i quicksortv i d Quadro 7 Trecho do Algoritmo Quick Sort parte 5 O tamanho das subsequências é confirmado comparando o valor do marcador E com o do índice final do vetor e comparando o valor do marcador D com o do índice inicial do vetor Se os valores forem iguais quer dizer que a subsequência tem tamanho um e já se encontra ordenada Se por exemplo E for maior que f5 o índice final do vetor quer dizer que essa subsequência não existe nos limites do índice do vetor O código completo do Quick Sort está ilustrado no Quadro 8 a seguir void quicksortint v int i int f int pivo vi vf2 int e i int d f while e d while e f ve pivo e while d i vd pivo d if e d int aux ve ve vd vd aux e d endif endwhile if e f quicksortv e f if d i quicksortv i d endfuncao Quadro 8 Código Completo do Algoritmo Quick Sort 223 Análise da Complexidade A eficiência desse algoritmo está associada à escolha de bons pivôs Um bom pivô é o que vai dividir a sequência em duas partes de tamanho igual mediana Um péssimo pivô seria escolher o menor ou maior número da sequência Assim o melhor caso se forem escolhidos consecutivamente bons pivôs do Quick Sort possui complexidade e no pior caso se 5 Um ponto importante no Algoritmo do Quick Sort é fazer as comparações dos limites do vetor usando os parâmetros de entrada i e f ao invés de 0 e vlength pois nas chamadas recursivas as definições de quem é o índice inicial e o final da subsequência variam a cada nova chamada recursiva forem escolhidos sempre o pior pivô possível o custo pode chegar até Mesmo com essas características dado a baixa probabilidade de se escolher consecutivamente o pior pivô possível o Quick Sort é tido como um dos métodos de ordenação mais eficientes Inclusive quanto mais desorganizados estiverem os números da sequência que se deseja ordenar maiores as chances do desempenho do Quick Sort ser superior a dos demais 3 Algoritmos do tipo seleção A ideia básica dos algoritmos do tipo seleção é escolher um elemento e posicionálo em sua posição definitiva Considere por exemplo uma sequência de números qualquer Um algoritmo de ordenação do tipo seleção identificaria quem é o menor número e o trocaria de lugar com o que está na primeira posição Em seguida identificaria quem é o segundo menor e o trocaria de lugar com o que está na segunda posição E assim sucessivamente Os algoritmos mais conhecidos do tipo seleção são Seleção Direta em inglês Selection Sort e o Heap Sort 31 Seleção direta Selection Sort 311 Funcionamento A seleção direta é um algoritmo bastante simples Para demonstrar seu funcionamento considere a sequência de números a seguir 5 3 1 2 4 0 1 2 3 4 Na primeira iteração o algoritmo começa assumindo que o primeiro elemento é o menor de todos Essa informação pode ser guardada por uma variável inteira que representará o índice do menor elemento6 5 3 1 2 4 Índice do menor 0 0 1 2 3 4 Em seguida se comparará o elemento que está na posição índice do menor com os demais elementos da lista Cada vez que um elemento menor for identificado a variável índice do menor é atualizada 66 Na demonstração a posição destacada em amarelo marca o elemento que atualmente está sendo considerando como o menor A célula com a linha mais grossa marca de onde se começou a fazer a busca pelo menor elemento posteriormente o elemento dessa célula será trocado com o menor 5 3 1 2 4 Não Índice do menor 1 0 1 2 3 4 5 3 1 2 4 Não Índice do menor 2 0 1 2 3 4 5 3 1 2 4 Sim Índice do menor 2 0 1 2 3 4 5 3 1 2 4 Sim Índice do menor 2 0 1 2 3 4 Como 1 é o menor elemento da sequência após a variável Índice do menor passar a guardar a sua posição ela não terá mais seu valor atualizado Após as comparações com os demais elementos da sequência o elemento que está na posição Índice do menor troca de lugar com o primeiro elemento da sequência na verdade com o elemento que foi considerado como o menor primeiro que no caso é o 5 1 3 5 2 4 0 1 2 3 4 Em seguida o processo se repete para a subsequência que começa a partir do 3 1 3 5 2 4 Índice do menor 1 0 1 2 3 4 Em seguida o processo se repete para a subsequência que começa a partir do 3 1 3 5 2 4 Não Índice do menor 1 0 1 2 3 4 1 3 5 2 4 Sim Índice do menor 3 0 1 2 3 4 1 3 5 2 4 Não Índice do menor 3 0 1 2 3 4 Após a segunda iteração se identifica que o 2 é o menor elemento restante da sequência Logo ele trocará de lugar com o elemento que foi considerado como menor primeiro que no caso é 3 1 2 5 3 4 0 1 2 3 4 Em seguida o processo se repete para a subsequência que começa onde está o 5 1 2 5 3 4 Índice do menor 2 0 1 2 3 4 1 2 5 3 4 Não Índice do menor 3 0 1 2 3 4 1 2 5 3 4 Sim Índice do menor 3 0 1 2 3 4 Após a quarta iteração se identificará que 3 é o menor elemento da sequência restante ele então troca de posição com 5 1 2 3 5 4 0 1 2 3 4 Novamente o primeiro elemento da sequência restante mais uma vez o 5 será considerado como menor elemento e será comparado com os demais 1 2 3 5 4 Índice do menor 3 0 1 2 3 4 1 2 3 5 4 Não Índice do menor 4 0 1 2 3 4 Finalmente trocase mais uma vez o elemento que está no índice do menor com o elemento que foi considerado menor no início dessa iteração 1 2 3 4 5 0 1 2 3 4 Essa última troca encerra o processo de ordenação Em resumo a cada iteração devese procurar o menor elemento entre os restantes na sequência Após identificálo posicionase ele no início da sequência e repetese o processo para a subsequência que o sucede No início o objetivo é encontrar o menor para então posicionálo na primeira célula do vetor Depois o objetivo passar a ser encontrar o segundo menor para posicionálo na segunda célula do vetor Então o objetivo passar a ser encontrar o terceiro menor elemento para posicionálo na terceira posição do vetor E assim sucessivamente 312 Pseudocódigo Para codificar a Seleção Direta podese começar com o trecho que identifica o índice do menor elemento de um vetor indicemenor 0 forint j 1 jvlentgh j if vj víndicemenor índicemenor j Quadro 9 Trecho do Algoritmo Seleção Direta Começase assumindo que o menor elemento está na primeira célula do vetor por isso o valor do indicemenor começa com zero Em seguida se compara o elemento que está na posição indicemenor com os demais e sempre que um elemento menor for identificado o valor dessa variável é atualizado com o índice desse elemento Entretanto o trecho do Quadro 9 só funciona uma vez Como repetilo várias vezes Simples basta colocálo dentro de um laço void selecaodiretaint v forint i 0 i vlength i assumindo que o iésimo é o menor int indicemenor i procurando o menor entre os restantes forint j i1 j vlength j if vj vindicemenor indicemenor j endfor trocando o iésimo elemento e menor de posição int aux vi vi vindicemenor vindicemenor aux endfor endfuncao Quadro 10 Código Completo do Algoritmo da Seleção Direta Notase que o segundo laço começa da posição i 1 isso faz com que as comparações aconteçam apenas com os elementos que estão na frente daquele que foi considerado inicialmente como menor na instrução indicemenor i No algoritmo da Seleção Direta após se identificar onde está o menor elemento trocamse as posições do menor e do primeiro elemento da sequência aquele que foi considerado como menor primeiro Além disso a cada iteração do laço externo acontece apenas uma troca ao final Diferente dos algoritmos do tipo troca onde podem acontecer várias trocas a cada iteração 313 Análise da Complexidade Percebese que a Seleção Direta consiste em dois laços que dependem do tamanho do vetor Os dois laços vão até o final da sequência Isso significa que o custo da Seleção Direta é de ordem quadrática Mais especificamente tanto no pior caso quanto no melhor caso o custo do algoritmo da Seleção Direta é 32 Heap Sort 211 Funcionamento Para entender o funcionamento do Heap Sort é necessário conhecer a estrutura de dados denominada Árvore Heap em inglês Heap Tree A Árvore Heap é uma árvore binária isso significa que cada nó da árvore pode ter no máximo dois filhos em que os nós pai são maiores que os filhos7 Considere que desejamos realizar a ordenação da sequência 5 3 1 8 6 7 4 2 O primeiro passo é organizar os elementos da sequência como uma Árvore Heap Para isso inserimos os elementos na árvore na mesma ordem em que eles aparecem na sequência O primeiro elemento da sequência vira raiz da árvore O segundo elemento da sequência vai virar filho esquerdo da raiz No exemplo da nossa sequência como o 3 é menor que 5 a regra de criação da Árvore Heap o pai deve ser maior que os filhos continua sendo respeitada e nada mais acontecerá O próximo elemento da sequência vai virar filho direito da raiz Novamente a inserção do 1 mantém a regra de criação da Árvore Heap pois 1 é menor que 5 o seu nó pai logo nada mais acontecerá O próximo elemento a ser inserido vai virar filho esquerdo do 3 os elementos são sempre inseridos da esquerda para direita dentro de um mesmo nível da árvore 7 Definição da Max Heap Tree Agora entretanto a inserção do 8 quebrou a regra de criação da Árvore Heap tornando necessária a reorganização dos elementos Primeiro ele trocará de lugar com o seu pai Entretanto isso não será suficiente para manter respeitando a regra de criação da Árvore Heap pois o 8 ainda é maior que seu pai o 5 Por essa razão mais uma vez outra troca entre pai e filho será necessária A inserção do 6 como filho direito do 5 provocará um efeito parecido Assim como a inserção do 7 como filho esquerdo do 1 A inserção do 4 como filho direito do 7 não gera mudanças no restante da Árvore Heap Por último o 2 é inserido como filho esquerdo do 3 mantendo a regra de criação da Árvore Heap lembrando que ele vira filho do 3 porque os elementos são inseridos em um nível sempre da esquerda para direita Com a Árvore Heap construída podemos dar continuidade à execução do método de ordenação Heap Sort Antes de continuar entretanto é importante fazer um esclarecimento a respeito da implementação da Árvore Heap é possível construir uma Árvore Heap dentro de um vetor para isso basta considerar que a raiz da árvore é guardada no índice 0 e que o filho esquerdo e direito de um elemento que está guardado no índice estão respectivamente nos índices e conforme ilustrado na Figura 1 Relação entre os elementos de uma Árvore Heap construída dentro de um vetor Isso significa que o filho esquerdo do elemento guardado no índice zero estaria no índice um e o filho direito do elemento guardado no índice zero estaria no índice dois Da mesma forma o filho esquerdo do elemento guardado no índice um estaria no índice três e o filho direito do elemento guardado no índice um estaria no índice quatro E assim sucessivamente Ter em mente essa possibilidade de construir a Árvore Heap dentro de um vetor será essencial para codificar o Heap Sort posteriormente E dessa forma considerando que construímos a Árvore Heap dentro do vetor agora ele se encontraria com a seguinte distribuição dos elementos 8 6 7 3 5 1 4 2 0 1 2 3 4 5 6 7 O elemento que vamos selecionar para posicionar corretamente no vetor é a raiz ele ficará no final da sequência Substituímos a raiz da árvore pelo elemento no último nível que estiver mais a direita no caso o 28 2 6 7 3 5 1 4 8 0 1 2 3 4 5 6 7 Claramente se o 2 permanecer como raiz ele estará desrespeitando a regra de existência da Árvore Heap Por isso após substituir a raiz será preciso reorganizar a Árvore Heap O 2 trocará de lugar com o maior dos seus filhos mesmo assim após subir o 7 será necessário reorganizar de novo a subárvore onde o 2 virou raiz fazendo ele trocar de lugar com o 4 7 6 4 3 5 1 2 8 0 1 2 3 4 5 6 7 Nesse momento trocamos mais uma vez a raiz da árvore no caso 7 com o elemento mais a direita no último nível no caso 2 o que mais uma vez exigirá uma reorganização da Árvore Heap 6 5 4 3 2 1 7 8 0 1 2 3 4 5 6 7 O processo de substituir a raiz pelo elemento do último nível que estiver mais a direita se repete levando a ascensão do 1 e novamente a necessidade de reorganização da árvore 5 3 4 1 2 6 7 8 0 1 2 3 4 5 6 7 8 Na árvore o elemento que está no último nível mais a direita ocupa a última posição do vetor Ao trocar a raiz por ele posicionamos corretamente o maior elemento da sequência Após isso passamos a não consideralo mais como parte da sequência a ser ordenada Agora o elemento que podemos posicionar no vetor é o 5 ele troca de lugar no array com o 2 que está no último nível mais a direita novamente reorganizando os elementos da Árvore Heap 4 3 2 1 5 6 7 8 0 1 2 3 4 5 6 7 Assim o próximo elemento a ser posicionado corretamente no vetor é o 4 que trocará de lugar com o 1 o elemento no último nível que está mais a direita 3 1 2 4 5 6 7 8 0 1 2 3 4 5 6 7 Finalmente o 3 troca de lugar com o 2 que fortuitamente é uma não causa outras mudanças na organização da árvore 2 1 3 4 5 6 7 8 0 1 2 3 4 5 6 7 Por último o 2 troca de lugar com o 1 tornandoo nova raiz da árvore 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 Ao final o 1 é removido da árvore deixandoa vazia e resultando na sequência ordenada 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 Em resumo o Heap Sort faz uso da Árvore Heap para repetidamente identificar quem é o maior elemento restante da sequência e posicioná lo em sua célula definitiva dentro do vetor 212 Pseudocódigo O Heap Sort é provavelmente um dos algoritmos de ordenação mais difíceis de implementar Ele é um procedimento composto basicamente por três etapas 1 construção da Árvore Heap 2 substituição da raiz pelo elemento do último nível mais a direita em outras palavras o último elemento da sequência desordenada e 3 reorganização da Árvore Heap Para codificálo vamos começar pelo método que organiza a partir de um elemento uma parte da Árvore Heap dentro do próprio vetor void construirHeapint v int i int f A despeito do nome o método construirHeap não constrói toda a árvore dentro do vetor O que ele faz é a partir de uma posição específica organizar os filhos do elemento desta posição como se estivessem em uma árvore Heap Para isso o método recebe como entradas respectivamente o vetor o índice a partir do qual se deseja organizar uma Árvore Heap e o índice que deve ser considerado como final do vetor void construirHeapint v int i int f while i f int maior i int e 2i1 int d 2i2 if e f ve vmaior maior e if d f vd vmaior maior d if maior i int aux vmaior vmaior vi vi aux i maior else return endelse endwhile endfuncao Quadro 11 Código Completo do Algoritmo da Seleção Direta O método começa atualizando uma variável chamada de maior A variável maior guardará o índice do elemento que deveria ser a raiz da Árvore Heap que está sendo construída e portanto por ser o maior de todos deveria estar na posição Inicialmente assumissese que o elemento guardado na posição é o maior Então calculase em que posições estariam os filhos de na Árvore Heap Em seguida testase qual dentre os três elementos é o maior o elemento na posição o filho esquerdo de ou o filho direito de Após se identificar quem é o maior testase se o maior ainda é o elemento na posição que foi considerado como maior inicialmente Caso o elemento na posição seja de fato o maior o método encerra sua execução pois esses três elementos já estão organizados como uma Árvore Heap Caso o elemento da posição não seja o maior trocase os elementos da posição e da posição maior de lugar Depois dessa mudança repetese todo o processo para testar se em sua nova posição o elemento que estava anteriormente na posição e os seus novos filhos também estão organizados como uma Árvore Heap O método construirHeap encerra sua execução quando o elemento da posição é maior que seus dois filhos ou quando ele se torna um nó folha nó sem filhos Dentro do método heapsort o método construirHeap vai ser chamado para gerar a Árvore Heap Inicialmente o método vai ser chamado para cada um dos elementos que fazem parte do vetor de trás para frente Com isso garantese que uma Árvore Heap estará organizada dentro do próprio vetor void heapsortint v int f vlength 1 forint i f i 0 i construirHeapv i f while f 0 int aux vf vf v0 v0 aux construirHeapv 0 f endwhile endfuncao Quadro 12 Código Completo do Algoritmo da Seleção Direta Com a Árvore Heap completamente construída o elemento que está na raiz da árvore primeiro elemento do vetor troca de posição com o que está no nível mais baixo e mais a direita última posição do vetor Após essa troca o método construirHeap é chamada novamente para corrigir a Árvore Heap mas dessa vez o tamanho do vetor é diminuído em uma unidade f dado que o elemento que se encontra ao final já está na sua posição definitiva 213 Análise da Complexidade A maior parte do custo do método heapsort está na utilização do método construirHeap o qual apresenta um custo de ordem logarítmica Dado que esse método é chamado várias vezes pelo menos duas para cada elemento do vetor uma na construção e outra na reorganização concluise que o custo do Heap Sort no melhor caso e no pior caso é igual a 4 Algoritmos do tipo inserção Os algoritmos do tipo inserção mudam o problema de ordenação para o problema de inserir os elementos em uma sequência ordenada Considere por exemplo uma sequência com os números desorganizados Isolase um dos números dessa sequência e estabelecese que ele faz parte de uma sequência ordenada sequência esta composta no momento por apenas um número Em seguida os demais elementos da sequência desordenada um a um são inseridos na sequência ordenada mas de forma a continuar mantendo a ordenação Após esvaziar a sequência desordenada a sequência ordenada terá todos os números da sequência original mas agora organizados com base na sua grandeza Os algoritmos do tipo inserção mais conhecidos são Inserção Direta em inglês Insertion Sort e Shell Sort 41 Inserção direta Insertion Sort 211 Funcionamento O algoritmo Inserção Direta é um método de ordenação que vai dividir a sequência em duas partes uma ordenada e outra com ordem desconhecida Considere que desejamos ordenar a sequência com os números abaixo 5 3 1 2 4 Inicialmente o método considerará que há uma subsequência dentro do próprio vetor onde todos os elementos estão todos ordenados Essa subsequência é formada pelo primeiro elemento de forma isolada 5 3 1 2 4 Considerando apenas o 5 ele faz parte de uma subsequência ordenada Isso porque essa sequência contém apenas um número o próprio 5 O algoritmo da inserção direta fará a comparação entre o primeiro elemento da subsequência desorganizada que no caso é o 3 e os elementos da sequência ordenada de trás para frente O objetivo é descobrir em qual posição da subsequência ordenada o 3 deve ser inserido 5 3 1 2 4 Não Quando o elemento que está sendo testado no caso o 3 se depara com um valor maior que ele esse valor maior deve ser jogado para trás O elemento que está sendo testado deve ser inserido uma posição depois do primeiro valor menor que ele que for encontrado ou quando ele já estiver na primeira posição do vetor 5 3 1 2 4 Não Então joga o 5 para trás 3 5 1 2 4 Agora nossa subsequência ordenada é composta por 3 5 Na próxima iteração o objetivo passa a ser inserir o 1 nessa subsequência ordenada Para isso o 1 será comparado com os valores da sequência ordenada de trás para frente 3 5 1 2 4 Não Então joga o 5 para trás 3 1 5 2 4 As comparações só se encerram quando o valor que está sendo posicionado no caso o 1 encontrar um elemento menor que ele ou quando ele estiver na primeira posição do vetor Logo no nosso exemplo as comparações continuam agora entre o 3 e o 1 3 1 5 2 4 Não Então joga o 3 para trás 1 3 5 2 4 Agora nossa subsequência ordenada é composta por 1 3 5 1 3 5 2 4 Na próxima iteração o objetivo é posicionar corretamente o 2 na subsequência ordenada As comparações a exemplo das anteriores iniciamse com o último elemento da subsequência ordenada no caso o 5 e se seguem até o 2 encontrar um elemento menor com ele ou estiver ocupando a primeira posição 1 3 5 2 4 Não Então joga o 5 para trás 1 3 2 5 4 1 3 2 5 4 Não Então joga o 3 para trás 1 2 3 5 4 1 2 3 5 4 Sim Então não acontece mais nada Quando o 2 for comparado com o 1 vai ser identificado que o 1 é menor que ele Logo na subsequência ordenada o 1 deve vir antes do 2 Dessa forma o 2 ficará posicionado uma célula depois do 1 e nossa subsequência ordenada agora será composta por 1 2 3 5 1 2 3 5 4 O último passo da Inserção Direta será inclusão do 4 dentro da sequência ordenada Da mesma forma que os elementos anteriores a primeira comparação será entre o número que queremos inserir na sequência ordenada no caso o 4 e a o último elemento da sequência ordenada 1 2 3 5 4 Não Então joga o 5 para trás 1 2 3 4 5 Entretanto é importante destacar que essa iteração não para O processo de inserir o novo elemento da sequência ordenada só acaba quando 1 encontrase um elemento menor que ele ou 2 o novo elemento já se encontra na posição inicial da sequência ordenada A próxima comparação será entre o 4 e seu antecessor o 3 1 2 3 4 5 Sim Então não acontece mais nada Após essa última comparação a sequência encontrase totalmente ordenada 1 2 3 4 5 212 Pseudocódigo A princípio a implementação do Inserção Direta pode parecer bastante complexa Entretanto se isolarmos algumas partes da lógica do algoritmo de fato perceberemos que se trata de um método de ordenação bastante simples Considere por exemplo que da posição 0 até uma posição o vetor encontrase totalmente ordenado Como seria o código para posicionar o elemento que está na posição i1 dentro da parte da sequência que está ordenada de forma a mantêla a sequência resultante ainda ordenada Esse é um algoritmo consideravelmente mais simples int j i1 int n vj while j 0 n vj1 vj vj1 j vj n Quadro 13 Trecho do Algoritmo da Inserção Direta O processo começa guardando o número que se deseja posicionar numa variável chamada Então iniciase um laço comparando com o número que vem na posição j19 Caso o número que se deseja posicionar seja menor que o que está a sua frente esse que está a sua frente é deslocado para trás e o contador j é decrescido em uma unidade o código dentro do laço Esse decréscimo tem o objetivo de fazer a comparação do com o próximo número da sequência de trás para frente Caso o número que se deseja posicionar seja maior ou igual ao seu antecessor quer dizer que quem vem antes dele é um número menor o laço para e o número é guardado na posição j O código do Quadro 13 é uma parte do algoritmo Inserção Direta Mas agora vem o problema como repetir esse processo para todas as posições do vetor Simples basta colocar o trecho destacado dentro de um laço void insertionsortint v forint i 0 i vlength1 i 9 Perceba que no código como é inicializado com o valor igual a Ao subtrair do o resultado é a própria posição Essa é a posição que antecede o na sequência e é justamente com quem queremos comparar o int j i1 int n vj while j 0 n vj1 vj vj1 j endwhile vj n endfor endfuncao Quadro 14 Algoritmo da Inserção Direta Importante destacar que o laço vai até vlength1 para não levar o algoritmo a acessar uma posição fora dos limites do vetor visto que uma das primeiras instruções é acessar o elemento da posição i1 213 Análise da Complexidade O custo do algoritmo Inserção Direta é variável dependendo das características da sequência recebida O Custo do algoritmo no pior caso é consequência de ser composto de dois laços que dependem do tamanho da sequência Entretanto caso a sequência já esteja ordenada o laço interno executará rapidamente pois a condição n vj1 imediatamente resultará em falso Esse é melhor caso do algoritmo no qual seu custo fica na ordem de 42 Shell Sort 211 Funcionamento Um dos problemas da Inserção Direta é que durante a execução do algoritmo levase bastante tempo para realizar a comparação entre os elementos que estão no final do vetor com os elementos que estão no começo Caso o vetor esteja perto de ser ordenado isso contribui negativamente para o desempenho da Inserção Direta O Shell Sort também conhecido como método dos incrementes decrescentes é uma variação da Inserção Direta que promove mais cedo a comparação entre elementos que se encontram distantes dentro da sequência Considere que desejamos realizar a ordenação da sequência 11 24 12 15 78 17 95 97 55 10 99 0 1 2 3 4 5 6 7 8 9 10 Percebese que essa sequência apresenta apenas alguns elementos fora de ordem 24 17 55 e 10 Utilizando a Inserção Direta o procedimento de trazer 10 o menor elemento para o início da sequência só vai acontecer no último passo do algoritmo Enquanto que com o Shell Sort isso aconteceria bem mais cedo Basicamente o Shell Sort divide o vetor a ser ordenado em segmentos menores e aplica o método de Inserção Direta em cada um deles Para estipular quais elementos fazem parte de um segmento é necessário utilizar uma informação chamada de incremento de shell ou gap a qual costuma ser denotada pela letra No Shell Sort a ordenação é realizada em vários passos A cada passo um valor diferente de é utilizado Essa sequência de valores 1 deve ser decrescente e é essencial que 2 o último valor de utilizado seja um para garantir que a sequência esteja ordenada ao final do procedimento Assim antes de iniciar a execução do Shell Sort se faz necessário propor uma sequência de s plural de Essa sequência pode ser proposta de várias formas desde que respeitados os dois requisitos previamente apresentados Inclusive existe uma série de estudos que associam a eficiência do Shell Sort à escolha de uma boa sequência de s de forma semelhante ao pivô do Quick Sort Para o nosso exemplo vamos escolher como estratégia para obter a sequência de s o resultado da divisão consecutiva do tamanho do vetor que queremos ordenar por dois a predileção por essa estratégia é justificada apenas pelo caráter pedagógico para esse exemplo nesse momento vamos ignorar se essa estratégia seria eficiente ou não Como o vetor em questão tem tamanho igual a onze a sequência de s seria 10 Isso implica que o primeiro valor de a ser considerado é cinco A construção do seguimento um pedaço da sequência tem início a partir da primeira posição do vetor A essa posição vai se somando o valor de até estourar os limites dos índices do vetor Todos os elementos que estiverem a posições entre si na sequência são agrupados em um seguimento e ordenados separadamente Partindo do índice zero os elementos do primeiro seguimento seriam 10 e Por coincidência a sequência termina em um entretanto se esse não fosse o caso adicionaríamos o um ao final da sequência 11 17 99 0 5 10 1º segmento O próximo seguimento se iniciaria a partir da primeira posição que não faz parte do seguimento anterior Nesse exemplo o primeiro índice do vetor que não faz parte da sequência anterior é o índice 1 Assim o próximo seguimento teria início do índice um e os seus elementos seriam 24 95 1 6 2º segmento Repetindo esse processo para os demais elementos da sequência todos os seguimentos iniciais do nosso vetor considerando seriam 11 17 99 0 5 10 24 95 1 6 12 97 2 7 15 55 3 8 78 10 4 9 1º segmento 2º segmento 3º segmento 4º segmento 5º segmento Perceba que nenhum índice do vetor faz parte de mais de um segmento Além disso a quantidade de elementos de um segmento dependerá do tamanho do vetor e do valor atual de incremento de shell isto é o No nosso exemplo se somássemos cinco valor atual de ao índice 9 último índice do 5º seguimento chegaríamos ao valor 14 Mas não há um índice 14 no vetor por isso ele não é incluído no 5º seguimento Por outro lado ao somar cinco valor atual de ao índice 5 obtemos o valor 10 O vetor possui índice 10 logo ele é incluído como parte do primeiro seguimento Ao continuar somando O vetor não possui índice 15 logo ele não é incluído dentro do primeiro seguimento que termina no índice 10 Essas são os segmentos que serão considerados na primeira etapa do Shell Sort Em cada um desses segmentos será utilizado o algoritmo da Inserção Direta para realizar a ordenação Após esse processo o qual não será detalhado aqui para não estender ainda mais a explicação os segmentos passarão a ficar assim os elementos destacados em amarelo são aqueles que mudaram de posição 11 17 99 0 5 10 24 95 1 6 12 97 2 7 15 55 3 8 10 78 4 9 1º segmento 2º segmento 3º segmento 4º segmento 5º segmento Como os segmentos são apenas visões separadas do vetor original no vetor os elementos estarão dispostos assim 11 24 12 15 10 17 95 97 55 78 99 0 1 2 3 4 5 6 7 8 9 10 Agora repetese o processo de criação dos segmentos considerando o próximo valor de incremento de shell da sequência de s Com temos os seguintes seguimentos 11 12 10 95 55 99 0 2 4 6 8 10 24 15 17 97 78 1 3 5 7 9 1º segmento 2º segmento Para cada seguimento aplicase mais uma vez o algoritmo da Inserção Direta Dessa vez entretanto vamos detalhar esse processamento Para o primeiro seguimento a ordenação aconteceria da seguinte forma 11 12 10 95 55 99 0 2 4 6 8 10 1º segmento Sim Então incluise o 12 na sequência considerada ordenada 11 12 10 95 55 99 0 2 4 6 8 10 1º segmento Não Então joga o 12 para trás e continuase a comparar o 10 com quem vem à frente 11 10 12 95 55 99 0 2 4 6 8 10 1º segmento Não Então joga o 11 para trás Como o 10 passa a estar no início do vetor essa iteração se encerra A próxima iteração considerará como sequência ordenada 10 11 12 95 55 99 0 2 4 6 8 10 1º segmento Sim Então incluise o 95 na sequência considerada ordenada 10 11 12 95 55 99 0 2 4 6 8 10 Não Então jogase o 95 para trás e continuase a 1º segmento comparar o 55 com quem vem à frente 10 11 12 55 95 99 0 2 4 6 8 10 1º segmento Sim Então a nova subsequência ordenada expande se para 10 11 12 55 95 99 0 2 4 6 8 10 1º segmento Sim Então incluise o 99 na sequência considerada ordenada e o processo se encerra para esse segmento 10 11 12 55 95 99 0 2 4 6 8 10 1º segmento Disposição final dos elementos do 1º seguimento Exercício Demonstre o funcionamento do algoritmo da Inserção Direta para o 2º segmento do nosso exemplo 24 15 17 97 78 1 3 5 7 9 2º segmento Ao aplicar o algoritmo da Inserção Direta no 2º segmento as partes da nossa sequência original passarão a estar organizadas assim 10 11 12 55 95 99 0 2 4 6 8 10 15 17 24 78 97 1 3 5 7 9 1º segmento 2º segmento Reforçando que toda essa reorganização acontece dentro do vetor original que passará a estar com a seguinte disposição dos elementos 10 15 11 17 12 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Note que os elementos continuam fora de ordem Entretanto os elementos menores que faziam estavam localizados no final da sequência já se deslocaram um pouco mais para o começo Teoricamente esse deslocamento prematuro traz a vantagem de tornar a aplicação da Inserção Direta no último passo do algoritmo mais eficiente Agora aplicase o algoritmo da Inserção Direta considerando o segmento criado com isto é o vetor inteiro Em outras palavras a última etapa do Shell Sort é utilizar normalmente o algoritmo da Inserção Direta O detalhamento desse processo é apresentando a seguir 10 15 11 17 12 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Logo incluise o 15 na sequência ordenada 10 15 11 17 12 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Não Então jogase o 15 para trás e continuase a comparar o 11 com quem vem à frente 10 11 15 17 12 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então a nova subsequência ordenada é 10 11 15 17 12 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Logo incluise o 17 na sequência ordenada 10 11 15 17 12 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Não Então jogase o 17 para trás e continuase a comparar o 12 com quem vem à frente 10 11 15 12 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Não Então jogase o 15 para trás e continuase a comprar o 12 com quem vem a frente 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então a nova subsequência ordenada passa a ser 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então incluise o 24 na sequência ordenada 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então incluise o 55 na sequência ordenada 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então incluise o 78 na sequência ordenada 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então incluise o 95 na sequência ordenada 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então incluise o 97 na sequência ordenada 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 Sim Então incluise o 99 na sequência ordenada 10 11 12 15 17 24 55 78 95 97 99 0 1 2 3 4 5 6 7 8 9 10 A sequência encontra se ordenada Dessa forma fica evidente o porquê de qualquer sequência d incrementos de shell terminada em 1 garantir a ordenação correta e como é estreita a relação entre os algoritmos Inserção Direta e Shell Sort Exercício Considerando a sequência abaixo descreva a sua ordenação utilizando 1 o algoritmo Shell Sort e a seguinte sequência de incrementos de shell e o algoritmo da Inserção Direta Ao final dê sua opinião sobre qual algoritmo que pareceu realizar a ordenação de forma mais rápida 11 24 12 15 78 17 95 97 55 10 99 212 Pseudocódigo O Shell Sort é uma variação do algoritmo da Inserção Direta onde se aplica as comparações entre elementos que estão a algumas posições de distância Essa distância é chamada de incremento de shell ou gap Em resumo aplicase a Inserção Direta considerando vários valores de incrementos de shell Assim uma forma simples de codificar esse algoritmo de ordenação poderia ser void shellsortint v int hs forint h hs adaptação da inserção direta considerando elementos com h casas de distância Quadro 15 Trecho do Algoritmo Shell Sort parte 1 Mas como seria essa adaptação Ao observar o código do Quadro 14 percebese alguns trechos onde fica expressa a distância entre os elementos que estão sendo comparados Por exemplo o trecho int j i1 int n vj Guarda o elemento que está na posição j dentro da variável n com o objetivo de comparálo com todos os elementos que vem antes dele que estão no intervalo entre zero e i O próximo trecho vai realizar a comparação entre N e quem vem imediatamente antes dele conforme trecho destacado a seguir while j 0 n vj1 Além disso caso os elementos precisem trocar de posição a variável j é decrementada em uma unidade para permitir a comparação com outro elemento que viria antes dele na sequência como pode ser observado no próximo trecho vj vj1 j São essas distâncias de uma unidade que devem ser revistas na adaptação que vai mudar o algoritmo da Inserção Direta e transformá lo no Shell Sort Por exemplo ao determinar qual elemento deve ser posicionado isto é qual elemento será guardado na variável n ao invés de colocar o elemento da posição i1 colocarseia o elemento da posição ih Assim se compararia esse elemento com elementos que vem h posições antes dele ou seja ao invés de comparar n com vj1 compararseia n com vjh Dessa forma uma possível implementação do Shell Sort está apresentada no Quadro 16 void sortint v int hs forint h hs forint i 0 ih vlength i int j i h int elem vj while jh 0 elem vjh vj vjh jjh vj elem endfor endfor endfuncao Quadro 16 Algoritmo do Shell Sort Além do que já foi comentado é importante destacar outras duas mudanças que essa implementação do Shell Sort traz 1 a condição de repetição do laço do for passa a ser ih vlength com o objetivo de evitar que ao somar a índice atual com o incremento de shell se estoure os limites do vetor 2 e a condição de repetição do laço while inclui também jh 0 para evitar que ao realizar a comparação com os elementos que vem antes do que queremos posicionar vj acessemos uma posição fora dos limites do vetor 213 Análise da Complexidade A análise da eficiência do Shell Sort é um problema matemático bastante complexo Principalmente por que o seu desempenho varia dependendo das características da sequência recebida e principalmente da estratégia utilizada para obter a sequência de incrementos de shell Conforme já comentado há vários estudos que propõe estratégias diferentes que tornam o algoritmo eficiente Sabese por exemplo que sequências que incluem valores múltiplos ou que não habilitam a comparação prematura de elementos em posições pares e ímpares costumam apresentar desempenho aquém do ideal Entretanto a melhor sequência possível ainda é desconhecida O criador original do método propôs a progressão geométrica descrita pela fórmula para gerar a sequência onde N seria o tamanho do vetor Essa foi inclusive a estratégia que utilizamos no nosso exemplo na seção 211 Funcionamento Entretanto é sabido que ela induz o Shell Sort a apresentar um desempenho de ordem quadrática considerado ruim para um algoritmo de ordenação Em 1973 Knuth11 demonstrou experimentalmente que sua sequência era muito difícil de ser batida por mais de 20 em eficiência Embora de lá para cá tenham surgido outras estratégias que se mostraram objetivamente melhores não necessariamente refutando Knuth seu método ainda é um dos mais famosos Supõese que utilizando o método proposto por Knuth12 o Shell Sort apresentaria desempenho igual à Sedgewick13 propôs outra estratégia que apresentaria desempenho igual à Embora uma análise geral do Shell Sort esteja além do escopo deste texto o consenso é que o desempenho está entre e 11 Knuth Donald E 1997 Shells method The Art of Computer Programming Volume 3 Sorting and Searching 2nd ed Reading Massachusetts AddisonWesley pp 8395 12 A sequência é obtida através da função recursiva cuja entrada seria um contador começando de um a ser incrementado a cada novo cômputo A sequência começada em um terminaria quando o resultado de for maior que o tamanho do vetor excluindose esse último Dado como o tamanho do vetor uma forma simples de gerar os termos dessa sequência é através do seguinte laço forint h 1 h N h 3 h 1 13 Sedgewick Robert 1986 A New Upper Bound for Shellsort Journal of Algorithms 7 2 159173 e que dentre os algoritmos ditos de complexidade quadrática o Shell Sort é o que mais se destaca 5 Algoritmos do tipo intercalação 51 Merge Sort 211 Funcionamento O Merge Sort é um algoritmo do tipo intercalação Na verdade ele é o único algoritmo de ordenação desse tipo A característica principal do Merge Sort é fazer uso de uma técnica chamada de intercalação que realiza a combinação de sequências ordenadas em uma única sequência ordenada Considere por exemplo que desejamos gerar uma terceira sequência ordenada a partir da união das duas sequências ordenadas a seguir 1 3 5 6 8 9 0 1 2 3 4 5 0 2 4 5 6 7 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 A intercalação realiza esse processo colocando um marcador no início de cada sequência ordenada onde estão os menores elementos de cada sequência 1 3 5 6 8 9 0 1 2 3 4 5 0 2 4 5 6 7 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 O algoritmo de intercalação compara os dois elementos marcados e posiciona o menor deles dentro da sequência resultado na posição 0 que marca o número dessa comparação após a primeira comparação o menor número irá para a posição 0 após a segunda comparação o menor número irá para a posição 1 após a terceira comparação o menor número irá para posição 2 e assim sucessivamente Além disso o marcador do número que foi posicionado passa para frente dentro do vetor onde está esse número O resultado ao fim da primeira iteração do algoritmo de intercalação é o seguinte 1 3 5 6 8 9 0 1 2 3 4 5 0 2 4 5 6 7 0 1 2 3 4 5 0 0 1 2 3 4 5 6 7 8 9 10 11 O processo então irá se repetir dessa vez comparando 1 e 2 e posicionando o menor na posição 1 do vetor resultante 1 3 5 6 8 9 0 1 2 3 4 5 0 2 4 5 6 7 0 1 2 3 4 5 0 1 0 1 2 3 4 5 6 7 8 9 10 11 Exercício Continue o processo de intercalação do exemplo até a sequência resultante estar completa Quando todos os elementos de uma das sequências ordenadas já estiverem presentes no vetor resultante os demais elementos da outra sequência ordenada são adicionados na mesma ordem em que aparecem neste outro vetor Isso ocorrerá quando o processo de intercalação inserir o 7 do segundo vetor dentro da sequência resultante 1 3 5 6 8 9 0 1 2 3 4 5 0 2 4 5 6 7 0 1 2 3 4 5 0 1 2 3 4 5 5 6 6 0 1 2 3 4 5 6 7 8 9 10 11 Após o 7 ser incluído na sequência combinada todos os elementos do segundo vetor terão sido incluídos Então o restante da primeira sequência será incluído na sequência combinada na mesma ordem em que aparecem no primeiro vetor 1 3 5 6 8 9 0 1 2 3 4 5 0 2 4 5 6 7 0 1 2 3 4 5 0 1 2 3 4 5 5 6 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 11 4 5 0 1 2 3 4 5 5 6 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 11 Voltando ao estudo do Merge Sort ele é um algoritmo de ordenação que faz uso da técnica de intercalação para ordenar qualquer tipo de sequência Mas como isso funciona visto que a intercalação só funciona para sequências ordenadas A resposta é simples basta construir sequências ordenadas a partir da sequência que queremos ordenar O Merge Sort divide a sequência original em partes menores até que as partes estejam ordenadas Então intercalamse consecutivamente essas partes ordenadas até se ter como resultado uma sequência ordenada com a mesma quantidade de elementos da sequência original Considere que queremos ordenar a sequência a seguir usando o Merge Sort 8 6 7 3 5 1 4 2 0 1 2 3 4 5 6 7 A primeira coisa que acontece é dividir a sequência ao meio 8 6 7 3 5 1 4 2 0 1 2 3 4 5 6 7 8 6 7 3 0 1 2 3 5 1 4 2 4 5 6 7 O processo de dividir cada subsequência ao meio continuará até se ter subsequências com apenas um elemento considerase que uma sequência composta por um único número está ordenada 8 6 7 3 5 1 4 2 0 1 2 3 4 5 6 7 8 6 7 3 0 1 2 3 5 1 4 2 4 5 6 7 8 6 0 1 7 3 2 3 5 1 4 5 4 2 6 7 8 0 6 1 7 2 3 3 5 4 1 5 4 6 2 7 Ao se obter sequências ordenadas o processo recursivo volta aplicando o método de intercalação unindo os elementos que faziam parte de uma mesma subsequência Isso significa que primeiro os elementos individuais serão intercalados com quem era seu par depois os pares serão intercalados com outros pares e assim sucessivamente 8 0 6 1 7 2 3 3 5 4 1 5 4 6 2 7 6 8 0 1 3 7 2 3 1 5 4 5 2 4 6 7 3 6 7 8 0 1 2 3 1 2 5 4 4 5 6 7 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 Ao final como resultado das consecutivas intercalações obteremos uma sequência ordenada 212 Pseudocódigo A princípio o Merge Sort também pode parecer um método de implementação complexa principalmente por envolver recursão A base desse algoritmo é conforme já comentado a técnica de intercalação Considere por exemplo a implementação do método de intercalação que vamos chamar de merge para unir dois vetores ordenados O método receberia os dois vetores ordenados como entrada e retornaria um vetor ordenado resultante da combinação dessa entrada int mergeint v1 int v2 int vetor new intv1length v2length int i 0 int j 0 int pos 0 while i v1length j v2length if v1i v2j vetorpos v1i i else vetorpos v2j j endelse pos endwhile while i v1length vetorpos v1i while j v2length vetorpos v2j return vetor endfuncao Quadro 17 Método de Intercalação que combina dois vetores recebidos como parâmetros Os contadores i e j método marcarão as posições a serem comparados respectivamente dos vetores v1 e v2 O contador pos marca a posição em que se deve inserir no vetor resultado que no código é chamado apenas de vetor A cada iteração do laço se compara o elemento de v1 que está na posição i com o elemento de v2 que está na posição j O menor entre esses elementos é guardado na posição pos do vetor resultante Ao final do laço pos é incrementado O laço continua até os contadores i e j saírem dos limites do vetor Além disso após o laço é feito o teste para adicionar os elementos remanescentes do outro vetor aqueles que ainda não foram adicionados ao vetor resultado Esses testes verificarão se i ou j estão dentro dos limites dos seus vetores v1 e v2 Quais adaptações seriam necessárias para que o método de intercalação reorganizasse elementos dentro de um mesmo vetor Imagine que temos um vetor onde do início até o meio dele há elementos ordenados e do meio até o final também há elementos ordenados Entretanto o vetor em si não está ordenado14 Primeiro a entrada do algoritmo seria apenas um vetor mas dessa vez combinado com três valores inteiros um marcador inteiro para a posição inicial do vetor um marcador inteiro para a posição do meio do vetor e um marcador para s posição final do vetor Além disso ao invés de retornar um novo vetor a ordenação ocorre dentro do próprio vetor que contém as metades ordenadas void mergeint v int inicio int meio int fim int auxiliar ArrayscopyOfv vlength int i inicio int j meio1 int pos i while i meio j fim if auxiliari auxiliarj vpos auxiliari i else vpos auxiliarj j endelse pos endwhile while i meio vpos auxiliari while j fim vpos auxiliarj 14 Isso pode parecer um pouco confuso mas um exemplo de sequência com essas características seria 3 6 7 8 1 2 5 4 Tanto a primeira metade da sequência quanto a segunda metade estão ordenadas Mas ao considerar a sequência como um todo o vetor não se encontra ordenado endfuncao Quadro 18 Método de Intercalação que combina as duas metades ordenadas dentro do próprio vetor O método começa criando uma cópia do vetor recebido a fim de poder modificalo posteriormente Em seguida os marcadores i e j são inicializados com as posições iniciais das duas metades Dado que a variável meio marca a última posição da primeira metade meio1 corresponderá a primeira posição da segunda metade De resto o método se assemelha bastante a outra versão com a diferença que o vetor que está sendo editado é o próprio v recebido como parâmetro de entrada ao invés de outro e que ele está recebendo os números da cópia dele Outra diferença significativa é que a variável pos começa da posição inicio e não da posição 0 Com o método de intercalação programado desta maneira podemos finalmente iniciar a codificação do Merge Sort O método recebe como entradas o vetor a ser ordenado e as indicações dos índices iniciais e finais do vetor void mergesortint v int i int f if if int meio if2 mergesortv i meio mergesortv meio1 f mergev i meio f endif endfuncao Quadro 19 Algoritmo Merge Sort Inicialmente é testado se if com o objetivo de confirmar se o vetor que está sendo considerado tem mais de um elemento ou não Caso o vetor tenha mais de um elemento é calculado o índice que deve ser considerado como meio Em seguida o método mergesort é chamado para as duas metades do vetor uma que vai do índice inicial até o meio e outra que vai de uma posição depois do meio até o índice do final Ao final o método mergesort realiza a intercalação das duas metades por meio da chamada do método merge Quando o método merge for chamado as duas metades do vetor já estarão ordenadas Por quê Durante a recursão o método mergesort continuará se chamando até considerar que o tamanho da entrada é igual a um isso vai acontecer quando a chamada recursiva não entrar na condição do if Quando o tamanho da entrada já for igual a um o código de intercalação vai unir as metades depois unir os pares depois unir as quadras e assim sucessivamente completando a execução do algoritmo 213 Análise da Complexidade O Merge Sort é um algoritmo recursivo que recebe um problema de tamanho e reduz a dois problemas de tamanho esse processo tem um custo de ordem logarítmica O custo para unir as metades é de ordem linear Assim o Merge Sort é um algoritmo que tem o custo igual a seja no melhor ou no pior caso 6 Algoritmos do tipo distribuição Os algoritmos do tipo distribuição não realizam a ordenação por meio da comparação direta entre os elementos mas por meio de uma análise distribuída sobre os elementos da sequência Esses algoritmos se baseiam em dois princípios 1 embora haja infinitos números o conjunto de dígitos que podem compor um número é limitado e a sua ordenação correta é conhecida 2 e dentro de um número com vários dígitos a posição em que um dígito aparece altera a sua importância Basicamente por meio dessas técnicas inicialmente realizase a ordenação da sequência apenas pela casa das unidades o dígito menos significativo em seguida pela casa da dezena depois pela casa da centena e assim sucessivamente até a primeira casa decimal do maior número da sequência o dígito mais significativo Os algoritmos de ordenação do tipo distribuição mais conhecidos são o Radix Sort e a Counting Sort 61 Radix Sort 211 Funcionamento O Radix Sort é um algoritmo que realiza a ordenação da sequência por partes Com o auxílio de um vetor de listas a cada iteração a sequência é reorganizada considerando uma casa decimal adicional primeiro a unidade depois a unidade e a dezena em seguida a unidade a dezena e a centena e assim sucessivamente Considere que desejamos realizar a ordenação da seguinte sequência utilizando o Radix Sort 20 31 11 83 36 37 44 156 O primeiro passo para realizar a ordenação será reorganizar os números dentro de um vetor de listas de tamanho igual a 10 0 1 2 3 4 5 6 7 8 9 Cada posição desse vetor vai reunir os elementos que tem um mesmo número para a casa decimal que estará sendo analisada Na primeira iteração do método é feita a alocação usando a casa da unidade Assim a posição 0 reunirá os elementos que tem unidade igual a 0 a posição 1 reunirá os elementos que tem unidade igual a 1 e assim sucessivamente Os números são analisados na ordem em que aparecem no vetor original Considere o 20 por exemplo A unidade do vinte é o 0 Assim inserimos o 20 na lista da posição 0 20 0 1 2 3 4 5 6 7 8 9 O próximo número da sequência é 31 cuja unidade é 1 Dessa forma ele será alocado na lista da posição 1 20 31 0 1 2 3 4 5 6 7 8 9 Em seguida o 11 também tem unidade 1 Por essa razão ele também é alocado na lista da posição 1 mas depois do 31 20 31 11 0 1 2 3 4 5 6 7 8 9 Esse processo se repete para cada um dos elementos que fazem parte da sequência Ao final da primeira iteração o vetor de listas estará da seguinte forma 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 8 9 Depois disso os elementos são retirados do vetor de listas na ordem em que aparecem e reorganizados dentro do vetor original Assim o 20 ocupará a posição 0 o 31 a posição 1 o 11 a posição 2 e assim sucessivamente 20 20 31 20 31 11 20 31 11 83 20 31 11 83 44 20 31 11 83 44 36 20 31 11 83 44 36 156 20 31 11 83 44 36 156 37 Perceba que ao final os elementos encontramse ordenados pela casa da unidade 20 31 11 83 44 36 156 37 Em seguida o processo se repete mas agora considerando a casa da dezena Os números são analisados na ordem em que aparecem na sequência atualmente Nessa segunda iteração o 20 ocupará a posição 2 destinada aos elementos cuja casa da dezena é o dois 20 0 1 2 3 4 5 6 7 8 9 Ao final da segunda iteração os elementos estão dispostos da seguinte forma no vetor de listas 11 20 31 36 37 44 156 83 0 1 2 3 4 5 6 7 8 9 Os números são novamente retirados do vetor de listas na ordem em que aparecem e são inseridos no vetor original 11 11 20 11 20 31 11 20 31 36 11 20 31 36 37 11 20 31 36 37 44 11 20 31 36 37 44 156 11 20 31 36 37 44 156 83 Agora os elementos estão ordenados considerando a casa da unidade e a casa dezena 11 20 31 36 37 44 156 83 Entretanto o vetor ainda não está ordenado O processo de ordenação deve ser repetido para cada casa decimal até o número de repetições for igual ao número de casas decimais do maior número da sequência Como o maior número da sequência é o 156 após a terceira repetição a sequência estará ordenada A terceira e última iteração realizará a ordenação com base na centena Os números são sacados na ordem em que estão atualmente na sequência O 11 será o primeiro a ser analisado A centena de 11 é 0 logo ele será guardado na posição 0 do vetor de listas 11 0 1 2 3 4 5 6 7 8 9 A centena de 20 é 0 também logo ele será guardado na posição 0 do vetor de listas 11 20 0 1 2 3 4 5 6 7 8 9 Ao final da iteração os elementos estarão organizados da seguinte forma no vetor de listas 11 20 31 36 37 44 83 156 0 1 2 3 4 5 6 7 8 9 Os números são novamente retirados do vetor de listas na ordem em que aparecem e são inseridos no vetor original 11 11 20 11 20 31 11 20 31 36 11 20 31 36 37 11 20 31 36 37 44 11 20 31 36 37 44 83 11 20 31 36 37 44 83 156 Agora o vetor encontrase ordenado 11 20 31 36 37 44 83 156 O processo encerra aqui pois o maior número tem três casas decimais e o ele já se repetiu três vezes15 212 Pseudocódigo A implementação do método Radix Sort leva a necessidade de vários métodos auxiliares São necessários um método para identificar o maior número um método para contar a quantidade de dígitos de um número e um método para isolar uma casa decimal específica de um número O método começa criando a estrutura auxiliar do vetor de listas e identificando o maior número da sequência recebida como entrada Em seguida é calculada a quantidade dígitos que compõem o maior número void radixsortint vetor List auxiliar new List10 int maior maiorvetor int qtdrepeticoes qtddigitosmaior continua endfuncao Quadro 20 Trecho do Algoritmo Radix Sort parte 1 A qtdrepeticoes corresponde à quantidade de dígitos que compõem o maior número que fizer parte da sequência Essa variável será usada para controlar o laço mais externo justamente para caracterizar quantas vezes o processo interno deve se repetir void radixsortint vetor List auxiliar new List10 int maior maiorvetor int qtdrepeticoes qtddigitosmaior forint i 1 i qtdrepeticoes i continua endfor 15 Se houvesse um número com quatro dígitos por exemplo o 9999 o processo do Radix Sort continuaria e se repetiria uma quarta vez mesmo que a sequência já estivesse ordenada após a terceira repetição endfuncao Quadro 21 Trecho do Algoritmo Radix Sort parte 2 Dentro do for cada número que compõe a sequência de entrada será analisado será identificado o digito correspondente ao número da repetição dígito da unidade na primeira repetição dígito da dezena na segunda repetição e assim sucessivamente e o valor deste dígito será usado para escolher em qual posição do vetor de listas auxiliar o número deve ser salvo void radixsortint vetor List auxiliar new List10 int maior maiorvetor int qtdrepeticoes qtddigitosmaior forint i 1 i qtdrepeticoes i forint v vetor int digito getdigitoi v auxiliardigitoaddv endfor continua endfor endfuncao Quadro 22 Trecho do Algoritmo Radix Sort parte 3 Após esse laço interno os números do vetor estão guardados na estrutura auxiliar Ao retirálos do array de listas na ordem em que aparecem obteremos a sequência ordenada considerando a quantidade de casas decimais do contador i primeiro apenas a unidade depois dezena e unidade e assim sucessivamente void radixsortint vetor List auxiliar new List10 int maior maiorvetor int qtdrepeticoes qtddigitosmaior forint i 1 i qtdrepeticoes i forint v vetor int digito getdigitoi v auxiliardigitoaddv endforeach int p 0 forList lista auxiliar forint v lista vetorp v endforeach endforeach endfor endfuncao Quadro 23 Código Completo do Algoritmo Radix Sort Ao final da iteração os números voltam ao vetor de entrada O processo se repete então considerando a próxima casa decimal 213 Análise da Complexidade O Radix Sort é um algoritmo bem diferente dos demais que estudamos até agora Todos os anteriores realizam a ordenação baseada em comparações O limite teórico para realizar ordenação com base em comparações é Entretanto por não se tratar de um algoritmo de ordenação por comparação o Radix Sort é um algoritmo de tempo de execução linear O primeiro laço interno do Radix Sort tem complexidade e o segundo laço interno tem complexidade onde seria o universo de valores possíveis que um dígito pode assumir assim o custo total do algoritmo é denotado pela equação Embora pareça que o Radix Sort é um dos mais eficientes dependendo das características da sequência ele pode de fato alcançar um tempo execução quadrático Para isso basta que os números que se quer ordenar sejam grandes muitas casas decimais 62 Counting Sort 211 Funcionamento Uma grande desvantagem que o Radix Sort apresenta é a necessidade por uma estrutura auxiliar consideravelmente grande um vetor de listas para realizar a ordenação Manter essa estrutura na memória pode ser bastante custoso Em comparação o Couting Sort é uma técnica que necessita apenas de dois vetores de inteiros com tamanho dez Resumidamente o algoritmo realiza uma contagem para identificar para cada chave que faz parte da sequência quantas chaves menores que ela existe dentro da sequência utilizando essa informação para realizar a ordenação Além disso Suponhamos que queremos ordenar a seguinte sequência 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 O processo de ordenação com o Couting Sort de forma similar ao Radix Sort também é realizado por partes primeiro considerando apenas a cada da unidade depois considerando também a dezena e assim sucessivamente até se passar por todas as casas decimais do maior digito da sequência Para iniciar o processo de ordenação cria se um vetor de inteiros de tamanho dez Esse vetor vai guardar nessa primeira repetição a Frequência Absoluta da Unidade F Abs U 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 Cada posição desse vetor representa um possível número para o dígito da unidade e guardará a quantidade de valores da sequência que possuem tal dígito por exemplo o índice zero guardará a informação de quantos valores com zero como dígito da unidade existem Para preencher a Frequência Absoluta recomendase analisar os números na sequência na ordem em que eles se apresentam e um por vez O primeiro número da sequência é 20 que tem como unidade o dígito 0 Logo incrementamos em um o valor guardado no índice zero do vetor de Frequência Absoluta F Ab U 1 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 O próximo número da sequência é o 31 cuja unidade é o dígito 1 Dessa vez incrementamos em um o valor guardado no índice um do vetor de Frequência absoluta F Ab U 1 1 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 Repetindo esse processo para cada valor da sequência ao final o vetor de Frequência Absoluta da Unidade estará preenchido da seguinte forma F Ab U 1 2 0 1 1 0 2 1 0 0 0 1 2 3 4 5 6 7 8 9 Com o vetor de Frequência Absoluta devidamente preenchido vamos construir o segundo vetor chamado de Frequência Acumulada da Unidade o qual também tem tamanho dez e que começa preenchido por zeros F Ab U 1 2 0 1 1 0 2 1 0 0 0 1 2 3 4 5 6 7 8 9 F Ac U 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 Cada índice do vetor de Frequência Acumulada guardará a da Unidade quantidade de valores dentro da sequência que possuem o dígito da unidade menor que o do índice em questão por exemplo o índice cinco guardará a informação de quantos valores com dígito da unidade menor que cinco fazem parte da sequência que desejamos ordenar Uma forma de obter essa informação é somar as frequências absolutas que vem antes do índice que queremos calcular Por exemplo no índice cinco do vetor de Frequência Acumulada vai a soma dos índices de zero a quatro do vetor de Frequência absoluta No índice zero até pela definição do que a informação representa sempre vai zero Assim 1 2 3 4 5 6 7 8 9 Outra forma de preencher cada posição do vetor de Frequência Acumulada é simplesmente somar o valor guardado na posição anterior do próprio vetor de Frequência Acumulada com o valor guardado no mesmo índice no vetor de Frequência Absoluta Por exemplo no índice cinco do vetor de Frequência Acumulada iria a soma do valor guardado no índice quatro do vetor de Frequência Acumulada com o valor guardado no índice quatro do vetor de Frequência Absoluta As duas formas chegam ao mesmo resultado 1 2 3 4 5 6 7 8 9 Dessa forma o vetor de Frequência Acumulada da Unidade após ser todo preenchido pela estratégia da sua escolha é a seguinte F Ac U 0 1 3 3 4 5 5 7 8 8 0 1 2 3 4 5 6 7 8 9 Uma forma de confirmar se o vetor foi corretamente preenchido é averiguar se os valores guardados em cada índice representam corretamente a informação do vetor original Conforme dito anteriormente cada índice do vetor de Frequência Acumulada da Unidade guardará a quantidade de valores dentro da sequência que possuem o dígito da unidade menor que o do índice em questão Por exemplo o índice dois do vetor de Frequência Acumulada da Unidade guarda o valor 3 Isso significa que no vetor que pretendemos ordenar há 3 valores com dígitos de unidade menor que dois Como podemos perceber essa informação está correta 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 Com o vetor de F Ac da U completamente preenchido podemos proceder com a ordenação da sequência Para isso vamos precisar de outro vetor do tamanho do vetor que desejamos ordenar Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 0 1 3 3 4 5 5 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 0 1 2 3 4 5 6 7 Agora começará de fato o processo de ordenação da sequência considerando a casa da unidade 1 Vamos analisar cada elemento que faz parte da sequência original na ordem em que eles estão dispostos 2 Para cada elemento vamos observar qual é o seu dígito da unidade 3 Em seguida vamos para o índice no vetor de Frequência Acumulada correspondente a esse dígito para descobrir em qual índice do novo vetor o elemento deverá ser guardado 4 Guardamos o elemento que estamos analisando naquele índice do novo vetor 5 e incrementamos o valor guardado no vetor de Frequência Acumula no índice correspondente ao dígito da unidade daquele número para que outro número com o mesmo dígito da unidade seja guardado numa posição subsequente Esse processamento está detalhado a seguir considerando o 20 primeiro valor da sequência que desejamos ordenar Assim os vetores que estamos manipulando apresentam agora a seguinte configuração Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 1 3 3 4 5 5 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 0 1 2 3 4 5 6 7 E repetimos o processamento descrito para os demais números O 31 possui 1 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 1 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 12 3 3 4 5 5 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 0 1 2 3 4 5 6 7 O 11 possui 1 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 2 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 23 3 3 4 5 5 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 11 0 1 2 3 4 5 6 7 O 83 possui 3 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 3 do 2º vetor Após Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 3 3 34 4 5 5 7 8 8 0 1 2 3 4 5 6 7 8 9 guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 2 20 31 11 83 0 1 2 3 4 5 6 7 O 36 possui 6 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 5 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 3 3 4 4 5 56 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 11 83 36 0 1 2 3 4 5 6 7 O 37 possui 7 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 7 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 3 3 4 4 5 6 78 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 11 83 36 37 0 1 2 3 4 5 6 7 O 44 possui 4 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 4 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 3 3 4 45 5 6 8 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 11 83 44 36 37 0 1 2 3 4 5 6 7 O 156 possui 6 como dígito da unidade O vetor de frequência acumulada indica que ele deve ser guardado no índice 6 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 36 37 44 156 0 1 2 3 4 5 6 7 F Ac U 1 3 3 4 4 5 67 8 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 Após todo esse processamento tomamos o 2º vetor como a sequência que desejamos ordenar e ela agora dispõe os elementos ordenados pela casa decimal da unidade como pode ser observado a seguir 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 O processo descrito se repete agora analisando o dígito da unidade de cada elemento da sequência Novamente o primeiro passo é construir o vetor de Frequência Absoluta dessa vez da Dezena F Ab D 0 1 1 3 1 1 0 0 1 0 0 1 2 3 4 5 6 7 8 9 Após preencher o vetor de Frequência Absoluta da Dezena prosseguimos com a criação do vetor de Frequência Acumulada da Dezena F Ab D 0 1 1 3 1 1 0 0 1 0 0 1 2 3 4 5 6 7 8 9 F Ac D 0 0 1 2 5 6 7 7 7 8 0 1 2 3 4 5 6 7 8 9 Com o vetor de F Ac da D completamente preenchido podemos proceder com a ordenação da sequência Para isso vamos precisar novamente de outro vetor do tamanho do vetor que desejamos ordenar Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 0 1 2 5 6 7 7 7 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 0 1 2 3 4 5 6 7 Agora começará de fato o processo de ordenação da sequência considerando a casa da dezena Repetimos o mesmo processo descrito anteriormente mas dessa vez observando o dígito da dezena ao invés do da unidade O 20 possui 2 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 2 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 0 12 2 5 6 7 7 7 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 0 1 2 3 4 5 6 7 O 31 possui 3 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 2 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 0 2 23 5 6 7 7 7 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 20 31 0 1 2 3 4 5 6 7 O 11 possui 1 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 0 do 2º vetor Após Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 01 2 3 5 6 7 7 7 8 0 1 2 3 4 5 6 7 8 9 guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 2 11 20 31 0 1 2 3 4 5 6 7 O 83 possui 8 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 7 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 1 2 3 5 6 7 7 78 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 11 20 31 83 0 1 2 3 4 5 6 7 O 44 possui 4 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 5 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 1 2 3 56 6 7 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 11 20 31 44 83 0 1 2 3 4 5 6 7 O 36 possui 3 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 3 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 1 2 34 6 6 7 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 11 20 31 36 44 83 0 1 2 3 4 5 6 7 O 156 possui 5 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 6 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 1 2 4 6 67 7 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 11 20 31 36 44 156 83 0 1 2 3 4 5 6 7 O 37 possui 3 como dígito da dezena O vetor de frequência acumulada indica que ele deve ser guardado no índice 4 do 2º vetor Após guardarmos o elemento nesse índice incrementamos a informação do vetor de frequência acumulada Vetor 1 20 31 11 83 44 36 156 37 0 1 2 3 4 5 6 7 F Ac D 0 1 2 45 6 7 7 7 8 8 0 1 2 3 4 5 6 7 8 9 Vetor 2 11 20 31 36 37 44 156 83 0 1 2 3 4 5 6 7 Após todo esse processamento tomamos o 2º vetor como a sequência que desejamos ordenar e ela agora dispõe os elementos ordenados pela casa decimal da dezena e da unidade como pode ser observado a seguir 11 20 31 36 37 44 156 83 0 1 2 3 4 5 6 7 Por fim para a sequência ficar totalmente ordenada só precisamos repetir esse processo mais uma vez mas considerando agora a casa decimal da centena Essa será a última repetição por que o maior número da sequência possui três dígitos Exercício Termine a ordenação da sequência utilizada no nosso exemplo utilizando o algoritmo Counting Sort 212 Pseudocódigo O processo de ordenação do Couting Sort pode ser descrito em quatro etapas conforme o fluxograma apresentado na Figura 2 Figura 2 Fluxograma do Couting Sort Com esse fluxograma será bem mais fácil iniciar a codificação do Couting Sort A primeira etapa do algoritmo a exemplo do Radix Sort é a coleta de informações sobre a sequência que se deseja ordenar a fim de identificar o maior elemento da sequência e a quantidade de dígitos que este possui void coutingsortint vetor int maior maiorvetor int qtdDigitosMaior qtddigitosmaior continua endfuncao Quadro 24 Trecho do Algoritmo Couting Sort parte 1 Em seguida se inicia o processo de ordenação por cada casa decimal que no código é descrito por um laço que começa de um representando a casa da unidade e vai até qtdDigitosMaior void coutingsortint vetor int maior maiorvetor int qtdDigitosMaior qtddigitosmaior forint casaDecimal 1 casaDecimal qtdDigitosMaior casaDecimal continua endfuncao Quadro 25 Trecho do Algoritmo Couting Sort parte 2 Ao final de cada repetição do laço apresentado no Quadro 25 a sequência estará um pouco mais organizada Primeiro considerando apenas a casa decimal da unidade depois considerando conjuntamente a dezena e assim sucessivamente até se analisar todas as casas decimais relevantes Dentro desse laço a primeira coisa que acontece é o preenchimento do vetor de Frequência Absoluta Para cada elemento k que faz parte da sequência se observa qual dígito usando a função getdigito ele possui na posição designada pela variável casaDecimal com um correspondendo a unidade dois a dezena e assim sucessivamente void coutingsortint vetor int maior maiorvetor int qtdDigitosMaior qtddigitosmaior forint casaDecimal 1 casaDecimal qtdDigitosMaior casaDecimal preenchendo a frequência absoluta int freqabsoluta new int10 forint k vetor int digito getdigitok casaDecimal freqabsolutadigito endfor continua endfuncao Quadro 26 Trecho do Algoritmo Couting Sort parte 3 Após preencher o vetor de Frequência Absoluta computase o vetor de Frequência Acumulada No código apresentado no Quadro 27 optou se por calcular cada posição da Frequência Acumulada como a soma da Frequência Absoluta e Acumulada da posição imediatamente anterior 2ª estratégia apresentada void coutingsortint vetor int maior maiorvetor int qtdDigitosMaior qtddigitosmaior forint casaDecimal 1 casaDecimal qtdDigitosMaior casaDecimal preenchendo a frequência absoluta int freqabsoluta new int10 forint k vetor int digito getdigitok casaDecimal freqabsolutadigito endfor preenchendo a frequência acumulada int freqacumulada new int10 forint i 1 i freqabsolutalength i freqacumuladai freqabsolutai1 freqacumuladai1 endfor continua endfuncao Quadro 27 Trecho do Algoritmo Couting Sort parte 4 Por fim com os dois vetores corretamente preenchidos criase uma cópia do vetor original para reorganizar os elementos que fazem parte da sequência na mesma medida em que se analisa eles em sua ordem original A nova posição de cada elemento é definida pelo vetor de Frequência Acumulada conforme se observa no Quadro 28 void coutingsortint vetor int maior maiorvetor int qtdDigitosMaior qtddigitosmaior forint casaDecimal 1 casaDecimal qtdDigitosMaior casaDecimal preenchendo a frequência absoluta int freqabsoluta new int10 forint k vetor int digito getdigitok casaDecimal freqabsolutadigito endfor preenchendo a frequência acumulada int freqacumulada new int10 forint i 1 i freqabsolutalength i freqacumuladai freqabsolutai1 freqacumuladai1 endfor reorganizando os elementos considerando a casa decimal da vez int copia vetorclone forint k copia int digito getdigitok casaDecimal int destino freqacumuladadigito vetordestino k endfor endfor endfuncao Quadro 28 Código Completo do Algoritmo Couting Sort O objetivo do último laço é ordenar os elementos considerando a casa decimal da vez Cada elemento será guardado na posição destino Essa posição destino é descoberta da seguinte forma 1 a função getdigito vai pegar o digito da casa decimal que está sendo considerada 2 no vetor de Frequência Acumulada o valor guardado no índice correspondente a digito vai determinar destino isto é para qual índice do vetor o elemento deve ser reposicionado Após se encontrar o destino devese incrementar o valor guardado no índice correspondente ao dígito para que os próximos números da sequência que possuam o mesmo dígito naquela casa decimal sejam alocados em posições posteriores do vetor 213 Análise da Complexidade Embora o Counting Sort pareça ser complicado na verdade seu funcionamento e implementação são bem simples O código apresentado no Quadro 28 demonstra que o algoritmo é composto por uma série de laços que utilizam vários controladores de repetições diferentes A função que identifica o maior elemento do vetor tem custo O laço mais externo é repetido vezes que corresponde a quantidade de dígitos do maior elemento As etapas internas desse laço possuem respectivamente custo de ordem e nesse contexto seria o universo de valores possíveis que um dígito pode assumir Aplicando propriedades de simplificação de notação assintótica teríamos que o custo do Couting Sort seria igual teoricamente o mesmo do Radix Sort mas com a vantagem de necessitar de bem menos espaço de armazenamento Entretanto o Couting Sort é conhecido por possuir complexidade igual nesse contexto corresponderia ao valor do maior elemento Isso por que existe uma variação desse algoritmo que realiza a ordenação com apenas uma passagem pela sequência Nessa variação o vetor de frequência acumulada tem o tamanho denotado pelo valor do maior elemento da sequência ou seja denotaria uma necessidade de espaço muito maior se tornando inviável para vetores com grandes elementos Essa variante mais eficiente está apresentada no Quadro 29 void coutingsortint vetor pegar informações int maior maiorvetor preenchendo a frequência absoluta int fab new intmaior forint k vetor fabk1 preenchendo a frequência acumulada int fac new intmaior forint i 1 i faclength i faci fabi1faci1 reorganizando os elementos int copia vetorclone forint k copia vetorfack1k endfuncao Quadro 29 Código Completo do Algoritmo Couting Sort variante Inclusive essa variante poderia ser otimizada reduzindo a necessidade por espaço com algumas adaptações 7 Classificação e comparação dos algoritmos de ordenação Os algoritmos de ordenação podem ser classificados de várias formas diferentes Mas sem sombra de dúvidas a classificação mais difundida leva em consideração a ideia por trás do algoritmo de ordenação Nessa classificação conforme já comentado os algoritmos podem ser do tipo troca seleção inserção intercalação e distribuição Outra classificação leva em consideração a área da memória onde a ordenação acontece Nessa classificação um algoritmo de ordenação pode ser de ordenação externa quando a ordenação acontece na memória secundária ou interna quando a ordenação acontece na memória principal Todos os algoritmos apresentados até aqui são de ordenação interna Outra classificação leva em consideração a necessidade de estruturas de dados auxiliares para realizar a ordenação Nessa classificação um algoritmo pode ser inplace quando a ordenação não faz uso de estruturas auxiliares e a ordenação ocorre dentro do próprio vetor ou não inplace quando é necessária uma estrutura de dados auxiliar para realizar a ordenação Outra classificação leva em consideração se o processamento instruções executadas pelo algoritmo varia de execução para execução Nessa classificação um algoritmo pode ser adaptativo quando se comporta diferente dependendo da sequência ou não adaptativo quando se comporta sempre da mesma forma Outra classificação leva em consideração como o algoritmo lida com elementos repetidos dentro da sequência Um algoritmo de ordenação é dito estável se ele preserva a ordem de elementos repetidos dentro da sequência Considere por exemplo a sequência 2a 2b 1 Notese que o elemento 2 aparece duas vezes dentro da sequência Em um algoritmo estável garantase que o 2a virá sempre antes do 2b na sequência ordenada pois o 2a aparece antes na sequência original Nos algoritmos não estáveis ou instáveis não há essa garantia Um exemplo de algoritmo de ordenação estável é o Bubble sort pois basta não realizar troca ao se deparar com elementos vizinhos iguais e de algoritmo não estável é o Quick sort pois ao se comparar elementos em lados diferentes esquerda e direita pode acontecer de um elemento passar na frente de outro de mesmo valor O Erro Fonte de referência não encontrada resume as características principais dos algoritmos de ordenação estudados Nome Tipo Melhor Caso Pior Caso Adaptativo In place Estável Bolha Troca 16 Sim Sim Sim Inserção Inserção Sim Sim Sim 16 A implementação mais inteligente do algoritmo da Bolha pode alcançar um custo linear Essa variação tem a particularidade de ser do tipo adaptativo Entretanto no geral a implementação mais comum do Bolha não é adaptativo e tem custo quadrático no pior caso Direta Seleção Direta Seleção Não Sim Não Quick Sort Troca Não Sim Não Shell Sort Inserção Sim Sim Não Heap Sort Seleção Não Sim Não Merge Sort Intercalação Não Não Sim Radix Sort Distribuição Não Não Sim Couting Sort Distribuição Não Não Sim Quadro 30 Quadro Resumo da Classificação dos Algoritmos de Ordenação Os algoritmos destacados no Erro Fonte de referência não encontrada são considerados os de pior desempenho entre os estudados 8 Exercícios de Fixação 1 Demonstre o passo a passo da ordenação das sequências abaixo utilizando os algoritmos de ordenação estudados Para cada sequência indique qual algoritmo você acredita que terá o melhor desempenho a 10 20 30 40 50 b 50 40 30 20 10 c 20 10 50 30 40 2 Escreva o código da versão mais eficiente que você conseguir pensar do algoritmo da Bolha Indique por que sua versão é mais eficiente do que a apresentada no texto 3 Use o método Quick Sort para ordenar esse array de Strings escolha como pivô sempre o elemento do meio da sequência Ana João Marcos José Alice Bruno Carlos Julio Juliana Moacir Felipe 4 Qual método de ordenação é mais eficiente para ordenar uma sequência composta apenas por números iguais selection sort ou insertion sort Justifique 5 Descreva como você modificaria o Radix Sort para ordenar cadeias de caracteres de tamanho diferente Por exemplo a chave carrega deve estar antes de carregamento e depois de borboleta