Open main menu

Changes

39 bytes removed ,  13:25, 30 May 2016
no edit summary
=== Merge Sort ===
Nós iremos agora implementar o merge sort em Maple. Nós Usaremos também iremos usar o 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 lista é de dividir a lista dividi-la 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 pseudocódigo:
1. Dada uma lista de elementos, se o tamanho da lista é 1, retorne essa lista.
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 é está 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.
</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 1000 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 100 elementos, usamos os comandos rand e seq do Maple, como representado a seguir:
<pre>
</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 Atente-se à importância de usar a estrutura de dados correta, ex: lists vs arrays.
== Árvores de Extensão ==
53

edits