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

Ordenao rpida (Quicksort)

Baseia-se num princpio muito simples que, quando aplicado de forma

recursiva, acaba por ordenar o vetor.

Este princpio composto por 2 passos essenciais:

1. Escolher um elemento do vetor, o pivot (por ex., V1);

2. Dividir o vetor em 2 partes (esquerda e direita), em que:

Parte esquerda com os elementos menores do que o pivot;

Parte direita com os elementos maiores do que o pivot.

Ao ser aplicado succesivamente este princpio a ambas as partes, quando

o processo recursivo terminar o vetor est ordenado.

Algoritmos de ordenao

Ordenao rpida (Quicksort)

O algoritmo composto ento por 3 etapas:

1. Determinar a posio final (posPivot) do elemento pivot (por ex. V1) no

vetor e coloc-lo nessa posio, dividindo o vetor em 2 partes:

Esquerda = V1, ..., VposPivot - 1

Direita = VposPivot + 1, ..., VN

2. Aplicar o algoritmo recursivamente parte esquerda;

3. Aplicar o algoritmo recursivamente parte direita.

Algoritmos de ordenao

Quicksort (Algoritmo)

Ordenar por Quicksort um subvetor de V desde inicio at fim

Se (inicio < fim) ento

posPivot posio final do pivot, Vinicio, no vetor

Ordenar por Quicksort o subvetor esquerdo ao pivot

Ordenar por Quicksort o subvetor direito ao pivot

Note-se que se (inicio >= fim) ento o subvetor de V tem

- apenas um elemento (inicio = fim) ou

- est vazio (inicio > fim).

Logo, este subvetor est ordenado.

Algoritmos de ordenao

Quicksort (Algoritmo)

Determinar a posio final posPivot do pivot (Vinicio) no subvetor de

V desde inicio at fimposPivot inicio

Para k desde (inicio+1) at fim fazer

Se (Vk < Vinicio) ento

posPivot posPivot + 1

Trocar(VposPivot, Vk)

Trocar(VposPivot, Vinicio)

{ Resultado = posPivot }

Algoritmos de ordenao

Quicksort (em MatLab)

function [V] = OrdenarQuicksort (V, inicio, fim)

if inicio < fim

[posPivot, V] = DeterminarPivot(V, inicio, fim);

V = OrdenarQuicksort(V, inicio, posPivot - 1);

V = OrdenarQuicksort(V, posPivot + 1, fim);

end;

Algoritmos de ordenao

Quicksort (em MatLab)

function [posPivot, V] = DeterminarPivot(V, inicio, fim)

posPivot = inicio;

for k = inicio+1:fim

if V(k) < V(inicio)

posPivot = posPivot + 1;

[V(k), V(posPivot)] = Trocar(V(k), V(posPivot));

end;

end;

[V(inicio), V(posPivot)] = Trocar(V(inicio), V(posPivot));

Algoritmos de ordenao

Quicksort (em MatLab)

function [a, b] = Trocar (a, b)

c = a;

a = b;

b = c;

Algoritmos de ordenao

Ordenao por fuso (Merge Sort)

A ordenao por fuso consiste em

dividir o vetor em vrios subvetores de menor dimenso,

ordenar estes subvetores separadamente e,

fundi-los num vetor nico.

O algoritmo de ordenao por fuso recursivo e consiste em

dividir sucessivamente o vetor ao meio at que se obtenham

subvetores com apenas um elemento (que est ordenado)

fundir os subvetores num vetor nico.

Algoritmos de ordenao

Ordenao por fuso (Merge Sort)

Pretende-se que o algoritmo de ordenao por fuso:

1. Ordene um vetor V entre as posies

a e b : Va, Va+1, ..., Vb e

b+1 e c : Vb+1, Vb+2, ..., Vc;

2. Fundir um vetor V entre as posies a e c, tendo em conta que est

ordenado entre as posies

a e b : Va Va+1 ... Vb e

b+1 e c : Vb+1 Vb+2 ... Vc.

Algoritmos de ordenao

Ordenao por fuso (Merge Sort)

Ordenar por fuso um vetor V entre as posies inicio e fim

Se (inicio < fim) ento

meio (inicio + fim) / 2

Ordenar por fuso o vetor V entre as posies inicio e meio

Ordenar por fuso o vetor V entre as posies meio+1 e fim

Fundir os subvetores de V entre [inicio, meio] e [meio+1, fim]

Note-se que se inicio fim ento o vetor composto

- apenas por um elemento (inicia = fim) ou

- est vazio (inicio > fim).

Logo, est ordenado.

Algoritmos de ordenao

Ordenao por fuso (em MatLab)

function [V] = OrdenarFusao (V, inicio, fim)

if inicio < fim

meio = floor((inicio + fim) / 2);

V = OrdenarFusao(V, inicio, meio);

V = OrdenarFusao(V, meio + 1, fim);

V = Fusao(V, inicio, meio, fim);

end;

Algoritmos de ordenao

Ordenao por fuso (em MatLab)

function [V] = Fusao(V, inicio, meio, fim)esq = inicio;dir = meio + 1;k = 0;while esq

Ordenao por fuso (em MatLab) cont.if esq > meio

for i = dir:fimk = k + 1;Aux(k) = V(i);

end;else

for i = esq:meiok = k + 1;Aux(k) = V(i);

end;end;for i = 0:k-1 % passar o vetor Aux ordenado para o vetor V

V(inicio+i) = Aux(i+1);end;

Algoritmos de ordenao

Diapositivo 1Diapositivo 2Diapositivo 3Diapositivo 4Diapositivo 5Diapositivo 6Diapositivo 7Diapositivo 8Diapositivo 9Diapositivo 10Diapositivo 11Diapositivo 12Diapositivo 13

Recommended

View more >