Algoritmos de ordenação - di.ubi.pt cbarrico/Disciplinas/ProgramacaoAlgoritmos/... · Ordenação…

  • Published on
    10-Nov-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>1/14</p><p>ALGORITMOS DE</p><p>ORDENAO RECURSIVOS</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao rpida (Quicksort) 2/14</p><p>Ordenao rpida (Quicksort)</p><p>Ideia</p><p>- Baseia-se num princpio muito simples que, quando aplicado recursivamente,</p><p>acaba por ordenar o vetor.</p><p>- Este princpio composto por 2 passos essenciais:</p><p>1. Escolher um elemento do vetor, o pivot (por ex., V[0]);</p><p>2. Dividir o vetor em 2 partes (esquerda e direita), em que:</p><p>- Parte esquerda com os elementos menores do que o pivot;</p><p>- Parte direita com os elementos maiores do que o pivot.</p><p>- Ao ser aplicado sucessivamente este princpio a ambas as partes, quando o</p><p>processo recursivo terminar o vetor est ordenado.</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao rpida (Quicksort) 3/14</p><p>Algoritmo</p><p>O algoritmo composto ento por 3 passos:</p><p>1.Determinar a posio final k do elemento pivot (V[0]) no vetor V com N elementos e</p><p>coloc-lo nessa posio, dividindo o vetor em 2 partes:</p><p>- Esquerda = V[0], ..., V[k-1]</p><p>- Direita = V[k+1], ..., V[N-1]</p><p>2. Aplicar o algoritmo recursivamente parte esquerda;</p><p>3. Aplicar o algoritmo recursivamente parte direita.</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao rpida (Quicksort) 4/14</p><p>Algoritmo principal</p><p>Ordenar por Quicksort um sub-vetor de V desde inicio at fim</p><p>Se (inicio &lt; fim) ento</p><p>k posio final do pivot, V[inicio], no vetor V</p><p>Ordenar por Quicksort o sub-vetor esquerdo ao pivot</p><p>Ordenar por Quicksort o sub-vetor direito ao pivot</p><p>Nota:</p><p>Se (inicio &gt;= fim) ento o sub-vetor de V tem </p><p>- apenas um elemento (inicio = fim) ou </p><p>- est vazio (inicio &gt; fim). </p><p>Logo, este sub-vetor est ordenado.</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao rpida (Quicksort) 5/14</p><p>Algoritmo auxiliar</p><p>Determinar a posio final k do pivot (V[inicio]) no sub-vetor de V de inicio a fimk inicio</p><p>Para i desde (inicio+1) at fim fazer</p><p>Se (V[i] &lt; V[inicio]) ento</p><p>k k + 1</p><p>Trocar (V[k], V[i])</p><p>Trocar (V[k], V[inicio])</p><p>Devolver (k)</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao rpida (Quicksort) 6/14</p><p>Funo principalvoid OrdenarQuicksort (int V[], int inicio, int fim) {</p><p>int k; // k = posio do pivot V[inicio]</p><p>if (inicio &lt; fim) {</p><p>k = DeterminarPivot(V, inicio, fim);</p><p>OrdenarQuicksort(V, inicio, k-1);</p><p>OrdenarQuicksort(V, k+1, fim);</p><p>}</p><p>}</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao rpida (Quicksort) 7/14</p><p>Funo auxiliar 1int DeterminarPivot (int V[], int inicio, int fim) {</p><p>int i, k = inicio; // k = posio do pivot V[inicio]</p><p>for (i = inicio+1; i </p></li><li><p>Ordenao rpida (Quicksort) 8/14</p><p>Funo auxiliar 2void Trocar (int *a, int *b){</p><p>int aux;</p><p>aux = *a;</p><p>*a = *b;</p><p>*b = aux;</p><p>}</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao por fuso (Merge Sort) 9/14</p><p>Ordenao por fuso (Merge Sort)</p><p>Ideia</p><p>- dividir o vetor em vrios sub-vetores de menor dimenso,</p><p>- ordenar estes sub-vetores separadamente e,</p><p>- fundi-los num vetor nico.</p><p>Algoritmo</p><p>- recursivo</p><p>- consiste em</p><p>- dividir sucessivamente o vetor ao meio at que se obtenham subvetores com apenas</p><p>1 elemento (que est ordenado)</p><p>- fundir os sub-vetores num vetor nico.</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao por fuso (Merge Sort) 10/14</p><p>Algoritmo</p><p>1. Ordenar o vetor V entre as posies</p><p>- a e b (V[a], V[a+1], ..., V[b]), e </p><p>- b+1 e c (V[b+1], V[b+2], ..., V[c]);</p><p>2. Fundir o vetor V entre as posies a e c, pois est ordenado entre as posies- a e b (V[a] V[a+1] ... V[b]) e </p><p>- b+1 e c (V[b+1] V[b+2] ... V[c]). </p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao por fuso (Merge Sort) 11/14</p><p>Algoritmo</p><p>Ordenar por fuso um vetor V entre as posies inicio e fim</p><p>Se (inicio &lt; fim) ento</p><p>meio (inicio + fim) / 2</p><p>Ordenar por fuso o vetor V entre as posies inicio e meio</p><p>Ordenar por fuso o vetor V entre as posies meio+1 e fim</p><p>Fundir os sub-vetores de V entre [inicio, meio] e [meio+1, fim]</p><p>Nota:</p><p>Se (inicio fim) ento o vetor V composto </p><p>- apenas por um elemento (inicia = fim) ou </p><p>- est vazio (inicio &gt; fim). </p><p>Logo, est ordenado.</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao por fuso (Merge Sort) 12/14</p><p>Funovoid OrdenarFusao (int V[], int inicio, int fim) {</p><p>int meio;</p><p>if (inicio &lt; fim) {</p><p>meio = (inicio + fim) / 2;</p><p>OrdenarFusao(V, inicio, meio);</p><p>OrdenarFusao(V, meio+1, fim);</p><p>Fusao(V, inicio, meio, fim);</p><p>}</p><p>}</p><p>Algoritmos de Ordenao Recursivos Programao II</p></li><li><p>Ordenao por fuso (Merge Sort) 13/14</p><p>Funo auxiliarvoid Fusao (int V[], int inicio, int meio, int fim) {</p><p>int esq = inicio, dir = meio+1, k = 0, Aux[fim-inicio+1];</p><p>while ((esq </p></li><li><p>Ordenao por fuso (Merge Sort) 14/14</p><p>Funo auxiliar (cont.)if (esq &gt; meio)</p><p>for (i = dir; i fim</p><p>for (i = esq; i = fim) ento o sub-vetor de V tem- apenas um elemento (inicio = fim) ou- est vazio (inicio &gt; fim).</p><p>Logo, este sub-vetor est ordenado.</p><p>Algoritmo auxiliarDeterminar a posio final k do pivot (V[inicio]) no sub-vetor de V de inicio a fim</p><p>Funo principalFuno auxiliar 1Funo auxiliar 2</p><p>Ordenao por fuso (Merge Sort)Ideia- dividir o vetor em vrios sub-vetores de menor dimenso,- ordenar estes sub-vetores separadamente e,- fundi-los num vetor nico.</p><p>Algoritmo- recursivo- consiste em- dividir sucessivamente o vetor ao meio at que se obtenham subvetores com apenas 1 elemento (que est ordenado)- fundir os sub-vetores num vetor nico.</p><p>Algoritmo1. Ordenar o vetor V entre as posies- a e b (V[a], V[a+1], ..., V[b]), e- b+1 e c (V[b+1], V[b+2], ..., V[c]);</p><p>2. Fundir o vetor V entre as posies a e c, pois est ordenado entre as posies- a e b (V[a] V[a+1] ... V[b]) e- b+1 e c (V[b+1] V[b+2] ... V[c]).</p><p>AlgoritmoOrdenar por fuso um vetor V entre as posies inicio e fimNota:Se (inicio fim) ento o vetor V composto- apenas por um elemento (inicia = fim) ou- est vazio (inicio &gt; fim).</p><p>Logo, est ordenado.</p><p>FunoFuno auxiliarFuno auxiliar (cont.)</p></li></ul>