Algoritmos de Ordenação: Conceitos e Implementações

DESENVOLVIMENTO DE APLICACOES ORIENTADAS A OBJETOS Um dos ingredientes mais comuns em programagao sao os algoritmos Algoritmos de Ordenacao de ordenagao e busca Na verdade 0 conceito de conjunto ordenado oe 1 Definigdes Preliminares de elementos tem um impacto consideravel no nosso quotidiano e na 2 Ordenagao por Selecdo Direta eficiéncia de algoritmos que agem sobre os dados Imagine como seria 3 Ordenago por insergao Simples age a 4 Bubble Sort achar 0 significado de uma palavra no dicionario se eles nao 5 QuickSort estivessem organizados em ordem alfabética A busca 6 grandemente 6 Algoritmos de Ordenagao facilitada porque existe uma ordem na qual os elementos estado organizados Um arquivo de tamanho N é uma sequéncia de WN registros ro 717N1 Como a composigao de um registro depende da aplicagao consideraremos 0 arquivo como sendo um vetor simples ou um vector No entanto poderia também ser uma lista ligada ou alguma outra estrutura de armazenamento de dados Quando nao se tem acesso direto a todos os registros do arquivo alguns métodos de ordenagdo podem se tornar muito ineficientes como veremos mais adiante Uma chave de ordenagao k deve ser atribuida a cada registro r normalmente a chave 6 um campo do registro Um arquivo é dito ordenado pela chave sez 7 implica em k k em alguma ordem das chaves Dois registros podem ter a mesma chave Uma técnica de ordenagao é chamada estavel se para todos os registros 7 e 7 tais que k kj se r precede r no arquivo original entao r precede r no arquivo ordenado A seguir consideraremos os principais algoritmos de ordenagao sua implementagao e seu desempenho ou sua complexidade computacional Por questdes de simplicidade o arquivo a ordenar sera um vetor de inteiros usaremos objetos da classe padrao C vector x 21 Algoritmo Ache o menor elemento no arquivo e o troque com o elemento na primeira posição Ache o segundo menor elemento e o troque com o elemento na segunda posição e assim sucessivamente 22 Implementação O arquivo a ordenar é o vector x de tamanho N A biblioteca C11 padrão utility inclui a operação swapab que troca os valores de a com b A função indicedomenor recebe um vetor x um limite inferior inf e um superior sup e retorna o índice do menor elemento de x entre inf e sup int indicedomenorvectorint x int inf int sup EXERCÍCIO void selecaovectorint x const int N xsize for int i0 iN i int im indicedomenorxiN1 stdswapxi xim troca xi com xim 23 Desempenho Comparações lêse da ordem de N ao quadrado Exercício Implemente a função indicedomenor em C 3 Ordenação por Inserção Simples 31 Algoritmo 000 020 ON 2 Como ordenação de cartas de baralho inicialmente considerase o primeiro elemento como estando ordenado Acrescentase então os elementos seguintes um a um na posição apropriada no meio daqueles já considerados e portanto já estavam ordenados Cada elemento é inserido na posição adequada movendose todos os elementos maiores do que ele para a direita para abrir espaço 32 Implementação void insercaovectorint x const int N xsize for int i1 iN i int v xi int j i while j0 xj1 v xj xj1 j xj v 33 Desempenho Comparações 4 Bubble Sort 41 Algoritmo Passar várias vezes pelo arquivo de maneira sequencial Em cada passo comparar cada elemento no arquivo com o seu sucessor xi com xii e trocálos caso não estejam na ordem certa No i ésimo passo o iésimo maior elemento estará na sua posição correta no arquivo Portanto são necessários N1 passos para ordenar o arquivo inteiro O algoritmo pode ser melhorado considerandose que se durante uma passagem nenhum elemento foi trocado então o vetor já está ordenado e o algoritmo pode ser interrompido sem necessidade de todos os N1 passos 000 010 ON 2 42 Implementagao void Bubblevectorint x const int N xsize bool troca true for int i0 iN1 troca i troca false for int j0 jNi1 j if xj xj1 troca true std swapxjxj1 43 Desempenho Comparacées ON A 51 Algoritmo Seja x o vetor a ordenar e N o numero de elementos em x Seja a um elemento qualquer de x por exemplo a x O vetor x é entao organizado de forma que a seja colocado em uma posigdo j com as seguintes condigées 1 Todos os elementos nas posig6es de a j1 Sao menores Ou iguais a a 2 Todos os elementos nas posigdes de j1 a N1 sao maiores que a Ao fazer isso a estara na sua posigao correta no vetor Se este processo for repetido recursivamente para os subvetores da posigdo a posigao j1 e da posigao j1 a posiao N1 0 resultado é 0 arquivo ordenado 52 Implementação A função divide divide o vetor x de inf até sup como descrito acima int dividevectorint x int inf int sup int a xinf int esq inf int dir sup while esq dir esq reduz 1 comparação desnecessária while xesq a esqsup esq while xdir a dir if esq dir stdswapxesq xdir dir reduz 1 comparação desnecessária stdswapxinf xdir return dir void QuickSortvectorint x int inf int sup if inf sup int j Dividex inf sup QuickSortx inf j1 QuickSortx j1 sup 53 Desempenho 000 016 Comparações menos comparações no caso geral para N grande do que os demais métodos 6 Algoritmos de Ordenação As curvas matemáticas de complexidade de algoritmos são comparadas no gráfico abaixo FIGURA 1 Curvas de complexidade Existem vários sites na Internet que ilustram o comportamento de algoritmos de ordenação por meio de animações Dois deles TopTalcom Algorithm Animations and Visualizations Um bom exercício é tentar classificar cada algoritmo por ordem de eficiência e procurar entender porque uns são mais lentos do que os outros por meio do cálculo do número de comparações necessárias em cada caso Exercício Desenvolva o algoritmo para o Buble Sort bidirecional que empurra o maior elemento para o final do vetor e logo em seguida o menor para o início do vetor Implementeo em C Por que o Bubble Sort bidirecional é mais eficiente que o Bubble Sort tradicional se em cada interação ambos colocam 1 elemento na posição certa 2021 Luiz A de P Lima Jr ON logN