Algoritmos de ordenação - di.ubi.pt cbarrico/Disciplinas/AlgoritmosEstruturas... · Ordenação rápida…

  • Published on
    11-Dec-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>Ordenao rpida (Quicksort)</p> <p> Baseia-se num princpio muito simples que, quando aplicado de forma </p> <p>recursiva, 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., V1);</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 succesivamente este princpio a ambas as partes, quando </p> <p>o processo recursivo terminar o vetor est ordenado.</p> <p>Algoritmos de ordenao</p> <p>Ordenao rpida (Quicksort)</p> <p>O algoritmo composto ento por 3 etapas:</p> <p>1. Determinar a posio final (posPivot) do elemento pivot (por ex. V1) no </p> <p>vetor e coloc-lo nessa posio, dividindo o vetor em 2 partes:</p> <p> Esquerda = V1, ..., VposPivot - 1 </p> <p> Direita = VposPivot + 1, ..., VN </p> <p>2. Aplicar o algoritmo recursivamente parte esquerda;</p> <p>3. Aplicar o algoritmo recursivamente parte direita.</p> <p>Algoritmos de ordenao</p> <p>Quicksort (Algoritmo)</p> <p>Ordenar por Quicksort um subvetor de V desde inicio at fim</p> <p>Se (inicio &lt; fim) ento</p> <p>posPivot posio final do pivot, Vinicio, no vetor</p> <p>Ordenar por Quicksort o subvetor esquerdo ao pivot</p> <p>Ordenar por Quicksort o subvetor direito ao pivot</p> <p>Note-se que se (inicio &gt;= fim) ento o subvetor de V tem </p> <p>- apenas um elemento (inicio = fim) ou </p> <p>- est vazio (inicio &gt; fim).</p> <p>Logo, este subvetor est ordenado.</p> <p>Algoritmos de ordenao</p> <p>Quicksort (Algoritmo)</p> <p>Determinar a posio final posPivot do pivot (Vinicio) no subvetor de </p> <p>V desde inicio at fimposPivot inicio</p> <p>Para k desde (inicio+1) at fim fazer</p> <p>Se (Vk &lt; Vinicio) ento</p> <p>posPivot posPivot + 1</p> <p>Trocar(VposPivot, Vk)</p> <p>Trocar(VposPivot, Vinicio)</p> <p>{ Resultado = posPivot }</p> <p>Algoritmos de ordenao</p> <p>Quicksort (em MatLab)</p> <p>function [V] = OrdenarQuicksort (V, inicio, fim)</p> <p>if inicio &lt; fim</p> <p>[posPivot, V] = DeterminarPivot(V, inicio, fim);</p> <p>V = OrdenarQuicksort(V, inicio, posPivot - 1);</p> <p>V = OrdenarQuicksort(V, posPivot + 1, fim);</p> <p>end;</p> <p>Algoritmos de ordenao</p> <p>Quicksort (em MatLab)</p> <p>function [posPivot, V] = DeterminarPivot(V, inicio, fim)</p> <p>posPivot = inicio;</p> <p>for k = inicio+1:fim</p> <p>if V(k) &lt; V(inicio)</p> <p>posPivot = posPivot + 1;</p> <p>[V(k), V(posPivot)] = Trocar(V(k), V(posPivot));</p> <p>end;</p> <p>end;</p> <p>[V(inicio), V(posPivot)] = Trocar(V(inicio), V(posPivot));</p> <p>Algoritmos de ordenao</p> <p>Quicksort (em MatLab)</p> <p>function [a, b] = Trocar (a, b)</p> <p>c = a;</p> <p>a = b;</p> <p>b = c;</p> <p>Algoritmos de ordenao</p> <p>Ordenao por fuso (Merge Sort)</p> <p> A ordenao por fuso consiste em</p> <p> dividir o vetor em vrios subvetores de menor dimenso,</p> <p> ordenar estes subvetores separadamente e,</p> <p> fundi-los num vetor nico.</p> <p> O algoritmo de ordenao por fuso recursivo e consiste em</p> <p> dividir sucessivamente o vetor ao meio at que se obtenham </p> <p>subvetores com apenas um elemento (que est ordenado)</p> <p> fundir os subvetores num vetor nico.</p> <p>Algoritmos de ordenao</p> <p>Ordenao por fuso (Merge Sort)</p> <p>Pretende-se que o algoritmo de ordenao por fuso:</p> <p>1. Ordene um vetor V entre as posies </p> <p>a e b : Va, Va+1, ..., Vb e </p> <p>b+1 e c : Vb+1, Vb+2, ..., Vc;</p> <p>2. Fundir um vetor V entre as posies a e c, tendo em conta que est </p> <p>ordenado entre as posies</p> <p>a e b : Va Va+1 ... Vb e </p> <p>b+1 e c : Vb+1 Vb+2 ... Vc. </p> <p>Algoritmos de ordenao</p> <p>Ordenao por fuso (Merge Sort)</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 subvetores de V entre [inicio, meio] e [meio+1, fim]</p> <p>Note-se que se inicio fim ento o vetor 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</p> <p>Ordenao por fuso (em MatLab)</p> <p>function [V] = OrdenarFusao (V, inicio, fim)</p> <p>if inicio &lt; fim</p> <p>meio = floor((inicio + fim) / 2);</p> <p>V = OrdenarFusao(V, inicio, meio);</p> <p>V = OrdenarFusao(V, meio + 1, fim);</p> <p>V = Fusao(V, inicio, meio, fim);</p> <p>end;</p> <p>Algoritmos de ordenao</p> <p>Ordenao por fuso (em MatLab)</p> <p>function [V] = Fusao(V, inicio, meio, fim)esq = inicio;dir = meio + 1;k = 0;while esq </p> <p>Ordenao por fuso (em MatLab) cont.if esq &gt; meio</p> <p>for i = dir:fimk = k + 1;Aux(k) = V(i);</p> <p>end;else</p> <p>for i = esq:meiok = k + 1;Aux(k) = V(i);</p> <p>end;end;for i = 0:k-1 % passar o vetor Aux ordenado para o vetor V</p> <p>V(inicio+i) = Aux(i+1);end;</p> <p>Algoritmos de ordenao</p> <p>Diapositivo 1Diapositivo 2Diapositivo 3Diapositivo 4Diapositivo 5Diapositivo 6Diapositivo 7Diapositivo 8Diapositivo 9Diapositivo 10Diapositivo 11Diapositivo 12Diapositivo 13</p>