Ordenação de Dados. Métodos de Ordenação Ordenação por troca –BubbleSort (método da bolha) –QuickSort (método da troca e partição) Ordenação por inserção

  • Published on
    17-Apr-2015

  • View
    105

  • Download
    1

Embed Size (px)

Transcript

  • Slide 1
  • Ordenao de Dados
  • Slide 2
  • Mtodos de Ordenao Ordenao por troca BubbleSort (mtodo da bolha) QuickSort (mtodo da troca e partio) Ordenao por insero InsertionSort (mtodo da insero direta) BinaryInsertionSort (mtodo da insero direta binria) Ordenao por seleo SelectionSort (mtodo da seleo direta) HeapSort (mtodo da seleo em rvore) Outros mtodos MergeSort (mtodo da intercalao) BucketSort (mtodo da distribuio de chave)
  • Slide 3
  • Mtodos de Ordenao Simples So trs BubbleSort InsertionSort SelectionSort Caractersticas fcil implementao alta complexidade comparaes ocorrem sempre entre posies adjacentes do vetor
  • Slide 4
  • BubbleSort BubbleSort um mtodo simples de troca ordena atravs de sucessivas trocas entre pares de elementos do vetor Caractersticas realiza varreduras no vetor, trocando pares adjacentes de elementos sempre que o prximo elemento for menor que o anterior aps uma varredura, o maior elemento est corretamente posicionado no vetor e no precisa mais ser comparado aps a i-sima varredura, os i maiores elementos esto ordenados
  • Slide 5
  • BubbleSort Simulao de funcionamento http://math.hws.edu/TMCM/java/xSortLab
  • Slide 6
  • BubbleSort - Complexidade Para um vetor de n elementos, n 1 varreduras so feitas para acertar todos os elementos 49215 n = 5 42159 21459 12459 12459 incio: 12459 1 a V: n 1 comparaes 2 a V: n 2 comparaes... (n-2) a V: 2 comparaes (n-1) a V: 1 comparao fim:
  • Slide 7
  • BubbleSort - Complexidade Definida pelo nmero de comparaes envolvendo a quantidade de dados do vetor Nmero de comparaes: (n - 1) + (n 2) +... + 2 + 1 Complexidade (para qualquer caso): i = 1 n - 1 i (n - 1) n = 2 O(n 2 )
  • Slide 8
  • InsertionSort InsertionSort um mtodo simples de insero Caractersticas do mtodo de insero considera dois segmentos (sub-vetores) no vetor: ordenado (aumenta) e no-ordenado (diminui) ordena atravs da insero de um elemento por vez (primeiro elemento) do segmento no- ordenado no segmento ordenado, na sua posio correta
  • Slide 9
  • Mtodo de Insero e5e5 e9e9...e8e8 e2e2 segmento ordenadosegmento no-ordenado e5e5 e8e8 e9e9...e2e2 Inicialmente, o segmento ordenado contm apenas o primeiro elemento do vetor
  • Slide 10
  • InsertionSort realiza uma busca seqencial no segmento ordenado para inserir corretamente um elemento do segmento no-ordenado nesta busca, realiza trocas entre elementos adjacentes para ir acertando a posio do elemento a ser inserido e5e5 e9e9 e8e8...e2e2 e5e5 e8e8 e9e9 e2e2
  • Slide 11
  • InsertionSort Simulao de funcionamento http://math.hws.edu/TMCM/java/xSortLab
  • Slide 12
  • InsertionSort - Complexidade Pior caso: vetor totalmente desordenado 95421 n = 5 59421 45921 24591 12459 incio: 1 a V: 1 comparao 2 a V: 2 comparaes... (n-2) a V: n-2 comparaes (n-1) a V: n-1 comparaes i = 1 n - 1 i (n - 1) n = 2 O(n 2 )
  • Slide 13
  • InsertionSort - Complexidade Melhor caso: vetor j ordenado 12459 n = 5 12459 12459 12459 12459 incio: 1 a V: 1 comparao 2 a V: 1 comparao... (n-2) a V: 1 comparao (n-1) a V: 1 comparao n - 1 O(n)
  • Slide 14
  • InsertionSort X BubbleSort Melhor casoPior caso InsertionSortO(n)O(n 2 ) BubbleSortO(n 2 )
  • Slide 15
  • SelectionSort SelectionSort um mtodo simples de seleo ordena atravs de sucessivas selees do elemento de menor valor em um segmento no- ordenado e seu posicionamento no final de um segmento ordenado e2e2 e5e5 e8e8...e6e6 e2e2 e5e5 e6e6 e8e8 troca
  • Slide 16
  • SelectionSort Caracterstica particular realiza uma busca seqencial pelo menor valor no segmento no-ordenado a cada iterao Simulao de funcionamento http://math.hws.edu/TMCM/java/xSortLab
  • Slide 17
  • SelectionSort - Complexidade Para qualquer caso 95124 15924 12954 12459 1 a V: n-1 comparaes 2 a V: n-2 comparaes... (n-1) a V: 1 comparao i = 1 n - 1 i (n - 1) n = 2 O(n 2 ) troca
  • Slide 18
  • Comparao Melhor casoPior caso InsertionSortO(n)O(n 2 ) BubbleSortO(n 2 ) SelectionSortO(n 2 )