53
edits
Changes
Jump to navigation
Jump to search
→Árvores e Ordenação
== Árvores e Ordenação ==
Essa seção explica como usar o Maple para executar e analisar algoritmos de ordenação. Árvores são frequentemente usadas para modelar algoritmos de ordenação, especialmente quando a complexidade desses algoritmos está sendo estudada. Em particular, essa seção foca em dois dos muitos tipos diferentes de algoritmos de ordenação que serão estudados, o bubble sort e o merge sort.
=== Bubble Sort ===
Para começar, nós iremos examinar a implementação do bubble sort. A razão pelo qual o bubble sort foi dado o nome "bubble" (bolha) é que o menor da lista "borbulha" em direção a frente da lista, se movendo um passo mais próximo a sua posições após cada iteração. O pseudo-código, que é destacado na página 575 do texto, é como o seguinte:
1. Recebe como entrada uma lista, L, de n elementos.
2. Entra num laço de repetição do índice i de 1 até n-1.
3. Entra num laço de repetição do índice j de 1 até n-i.
4. Se o elemento na posição j+1 na lista L é menor que o elemento na posição j de L, troque esses dois elementos.
No final de cada laço j, nós posicionamos os elementos mais largos i no final de L.
O seguinte procedure, chamado BubbleSort, é uma implementação desse pseudocódigo.
<pre>
BubbleSort:=proc(L::list)
local i, j, temp, T;
T:= array(L);
for i from 1 to nops(L)-1 do
for j from 1 to nops(L)-i do
if T[j] > T[j+1] then
temp:=T[j];
T[j] := T[j+1];
T[j+1] := temp;
fi;
od;
od;
convert(T,list);
end:
</pre>
Note que antes de começar a mover os elementos, nós convertemos a lista L em um arranjo. Isso porque nós podemos mudar cada elemento de um arranjo em apenas uma operação, enquanto para mudar qualquer parte de uma lista, nós devemos recopiar a lista inteira -- um processo envolvendo n operações. Quando nós terminarmos de mover os elementos, nós transformamos o arranjo novamente em uma lista.
Podemos examinar a execução desse procedure em uma lista desordenada. Note que se a lista tem cinco elementos, um total de 5*4/2 = 10 laços são usados pelo algoritmo bubble sort para ordenar esses elementos.
<pre>
BubbleSort([3,2,4,1,5]);
</pre>
=== Merge Sort ===
Nós iremos agora implementar o merge sort em Maple. Nós também iremos usar Maple para estudar a complexidade desse algoritmo. O algoritmo de merge sort pode ser implementado como um procedure recursivo. A idéia básica da tarefa de aplicar merge sort numa é de dividir a lista em duas de tamanhos iguais ou quase iguais, ordenando cada sub-lista usando o algoritmo merge sort, e no final juntando as listas resultantes. Isso pode ser descrito no seguinte pseudo-código:
1. Dada uma lista de elementos, se o tamanho da lista é 1, retorne essa lista.
2. Se a lista tem mais de dois elementos, use o merge sort nessas duas listas e retorne a lista fundida resultante.
Primeiro usamos um procedure, Merge, que pega duas listas ordenadas e funde elas em uma única lista ordenada, consistindo dos elementos das duas listas. Aqui está o exemplo em código Maple para o procedure de Merge:
<pre>
Merge := proc(L1::list, L2::list)
local L, i,j,k,m,n;
L:=[];
i := 1; j := 1; k := 1;
m := nops(L1); n := nops(L2);
L := array(1..m+n);
while i <= m and j <= n do
if L1[i] <= L2[j] then
L[k] := L1[i];
i := i+1;
else
L[k] := L2[j];
j := j+1;
fi;
k := k+1;
od;
while i <= m do
L[k] := L1[i];
i := i+1; k := k+1;
od;
while j <= n do
L[k] := L2[j];
j := j+1; k := k+1;
od;
convert(L,list);
end:
</pre>
Nós ilustramos o uso desse procedure com o seguinte exemplo:
<pre>
Merge([1,2,6,8],[3,5,7]);
</pre>
Agora nós damos o pseudo-código para o algoritmo merge sort:
A descrição do algoritmo merge sort que nós iremos usar é baseada na definição recursiva. Em pseudocódigo:
1. Se a lista L tem apenas um elemento, ela é ordenada em ordem, então retornamos L como ela é.
2. Se L tem mais de um elemento, nós dividimos a lista em duas listas de mesmo tamanho, ou de maneira que a segunda lista tenha exatamente um elemento a mais que a primeira.
3. Nós recursivamente usamos o merge sort nas duas listas, e então juntamos as duas listas.
<pre>
MergeSort:=proc(L::list)
local First, Second,i, n;
</pre>
Se a lista tem apenas um elemento, retorne-o
<pre>
if nops(L) = 1 then
</pre>
print(L)
<pre>
L;
else
</pre>
A lista tem mais de um elemento print(L)
<pre>
n := nops(L);
mid := floor(n/2);
</pre>
Divida as listas em duas sub-listas de tamanho igual
<pre>
First := L[1..mid];
Second := L[mid+1..n];
</pre>
Junte o resultado dos merge sorts nas duas listas
<pre>
Merge(MergeSort(First), MergeSort(Second));
fi;
end:
</pre>
Nós ilustramos o uso do procedure MergeSort ordenando uma lista desordenada com 100 elementos:
<pre>
MergeSort([8,2,4,6,9,7,10,1,5,3]);
</pre>
Nós iremos agora analizar o tempo de execução do MergeSort em relação ao BubbleSort. Especificamente, nós iremos criar uma lista desordenada com 10000 elementos aleatórios e executar o BubbleSort e o MergeSort nessa lista. Isso irá nos dar uma ilustração limitada do tempo de execução desses procedures, na qual o leitor deve expandir lendo análises teóricos no texto.
Para criar uma lista aleatória com 1000 elementos, usamos os comandos rand e seq do Maple, como representado a seguir:
<pre>
A:=[seq(rand(), i=1..100)]:
</pre>
Então, nós podemos usar o comando time para medir a quantidade de tempo necessário para ordenar a lista aleatória:
<pre>
st:=time(): BubbleSort(A): time() - st;
st:=time(): MergeSort(A): time() - st;
</pre>
O leitor é encorajado a implementar outros tipos de algoritmos de ordenação usando o Maple e a estudar a complexidade relativa desses algoritmos quando usandos para ordenar listas de vários tamanhos diferentes. Também é interessante usar técnicas de animação para ilustrar os passos dos algoritmos de ordenação. Apesar de não fazermos isso aqui, o leitor com habilidades avançadas de programação é convidado a fazê-lo. Tome nota especial para a importância de usar a estrutura de dados correta, ex: lists vs arrays.
== Árvores de Extensão ==
