Métodos de Ordenação: Bubble Sort e Introdução ao Problema da Ordenação

Algoritmos para Ordenação Monael Pinheiro Ribeiro DSc Universidade Federal do ABC Centro de Matemática Computação e Cognição Problema da Ordenação Formalmente Suponha uma coleção V de elementos de tamanho n V v0 v1 v2 vn1 Desejase que V tenha a seguinte propriedade vj vj1 0 j n1 vj V Informalmente Dado um vetor V de tamanho n Garantir que após um procedimento os elementos de V ou seja v0 v1 vn1 estejam ordenados de forma crescente Problema da Ordenação Formalmente Suponha uma coleção V de elementos de tamanho n V v0 v1 v2 vn1 Desejase que V tenha a seguinte propriedade vj vj1 0 j n1 vj V Informalmente Dado um vetor V de tamanho n Garantir que após um procedimento os elementos de V ou seja v0 v1 vn1 estejam ordenados de forma decrescente Método da Bolha Método da Bolha Método da Bolha Método da Bolha Bubble Sort Método da Bolha O método bolha de ordenação usa justamente o conceito das bolha no meio fluídico Mecanismo Comparase os n elementos do vetor dois a dois Trocando de posição quando o iésimo elemento for maior que o i1ésimo elemento Repetese para os n1 elementos restantes Repetese para os n2 elementos restantes Até que só reste 1 elemento Que por sua vez já é ordenado Bubble Sort Bubble Sort Bubble Sort Bubble Sort 0 1 2 3 4 6 9 1 V0 V1 Bubble Sort 0 1 2 3 4 6 9 1 V0 V1 Não Bubble Sort 0 1 2 3 4 6 9 1 V0 V1 Não Vá para o próximo Bubble Sort 0 1 2 3 4 6 9 1 V1 V2 Bubble Sort 0 1 2 3 4 6 9 1 V1 V2 Não Bubble Sort 0 1 2 3 4 6 9 1 V1 V2 Não Vá para o próximo Bubble Sort 0 1 2 3 4 6 9 1 V2 V3 Bubble Sort 0 1 2 3 4 6 9 1 V2 V3 Sim Bubble Sort 0 1 2 3 4 6 9 1 V2 V3 Sim Então Troque V2 e V3 Bubble Sort 0 1 2 3 4 6 1 9 V2 V3 Sim Então Troque V2 e V3 Vá para o próximo O maior elemento do vetor V de n posições está na posição n1 3 do vetor Agora reaplique o procedimento no vetor excluindo a posição n1 3 Bubble Sort 0 1 2 3 4 6 1 9 V0 V1 Bubble Sort 0 1 2 3 4 6 1 9 V0 V1 Não Vá para o próximo Bubble Sort 0 1 2 3 4 6 1 9 V1 V2 Bubble Sort 0 1 2 3 4 6 1 9 V1 V2 Sim Bubble Sort 0 1 2 3 4 1 6 9 V1 V2 Sim Então Troque V1 e V2 Vá para o próximo Bubble Sort 0 1 2 3 4 1 6 9 V1 V2 Sim Então Troque V1 e V2 Vá para o próximo O maior elemento do subvetor V de n1 posições está na posição n2 2 do vetor Agora reaplique o procedimento no vetor excluindo a posição n2 2 e n1 3 Bubble Sort 0 1 2 3 4 1 6 9 V0 V1 Bubble Sort 0 1 2 3 4 1 6 9 V0 V1 Sim Bubble Sort 0 1 2 3 1 4 6 9 V0 V1 Sim Então Troque V1 e V2 Vá para o próximo Bubble Sort 0 1 2 3 1 4 6 9 V0 V1 Sim Então Troque V1 e V2 Vá para o próximo Bubble Sort 0 1 2 3 1 4 6 9 V0 V1 Sim Então Troque V1 e V2 Vá para o próximo O maior elemento do subvetor V de n2 posições está na posição n3 1 do vetor Bubble Sort 0 1 2 3 1 4 6 9 V0 V1 Sim Então Troque V1 e V2 Vá para o próximo O maior elemento do subvetor V de n2 posições está na posição n3 1 do vetor Bubble Sort 0 1 2 3 1 4 6 9 V0 V1 Sim Então Troque V1 e V2 Vá para o próximo O maior elemento do subvetor V de n2 posições está na posição n3 1 do vetor O subvetor restante tem tamanho 1 Um elemento só já está ordenado Portanto o procedimento terminou Bubble Sort 0 1 2 3 1 4 6 9 V0 V1 Sim Então Troque V1 e V2 Vá para o próximo O maior elemento do subvetor V de n2 posições está na posição n3 1 do vetor O subvetor restante tem tamanho 1 Um elemento só já está ordenado Portanto o procedimento terminou Bubble Sort 01 public static void bubbleSortint v int n 02 03 int i j aux 04 fori0 in1 i 05 06 forj0 jn1i j 07 08 ifvj vj1 09 10 aux vj 11 vj vj1 12 vj1 aux 13 14 15 16 Eficiência Qual o esforço computacional necessário para o Bubble Sort ordenar n elementos no pior caso Qual a função primitiva do bubble sort 01 public static void bubbleSortint v int n 02 03 int i j aux 04 fori0 in1 i 05 06 forj0 jn1i j 07 08 ifvj vj1 09 10 aux vj 11 vj vj1 12 vj1 aux 13 14 15 16 Eficiência Quantas vezes ocorre a função primitiva no pior caso Pense para o exemplo n4 i j Linha 8 0 0 1x 0 1 1x 0 2 1x 0 3 1 0 1x 1 1 1x 1 2 2 0 1x 2 1 3 Total 6 x Eficiência Comportamento Tamanho Comparações 4 6 10 45 20 190 30 435 100 4950 1000 499500 10000 49995000 Eficiência Eficiência Comportamento 0 200000 400000 600000 800000 1000000 1200000 1400000 1600000 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 n² Bubble Eficiência Comportamento On² Vale a Pena Estudar Selection Sort O Selection Sort ordena um arranjo baseado em localizar o menor elemento e posicionálo na 1ª posição Então encontra o segundo menor elemento e posicionáo na 2ª posição e assim por diante Para os n1 elementos do vetor Vale a Pena Estudar Insertion Sort Algoritmo de Ordenação baseado na forma como ordenamos cartas de baralho O mais eficiente para o MELHOR CASO