Quero um Titulo

...

Método ilustrado:

[pic 6]

Figura 4: Bubble Sort http://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261

Vantagens:

É um algoritmo de ordenação simples e estável.

Desvantagens:

Possui muita lentidão devido seu modo de execução, o qual passa em cada elemento do vetor.

Esse método de ordenação é indicado em tabelas pequenas, quando se sabe que a tabela está quase ordenada e demonstração didáticas.

Ordenação pelo Método da Insertion Sort

https://pt.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/insertion-sort

O Insertion sort é um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados. O tempo gasto para executar este algoritmo depende do valor de entrada, sendo que se for para ordenar milhares de números esse algoritmo deve levar bem mais tempo do que ordenar apenas três números. Além disso, esse tipo de ordenação pode levar diferentes quantidades de tempo para ordenar duas sequências de entrada do mesmo tamanho dependendo do quanto elas já estão ordenadas. Por isso o melhor caso para se usar o Insertion Sort é quando o array já está quase ordenado. O tempo de execução obedecerá uma função linear e a complexidade do algoritmo será de O(n).

Sendo assim podemos considerar o pior caso é a situação inversa quando o array está totalmente fora de ordem. Nesta situação para cada iteração do laço externo, o laço interno executará n-1 vezes, onde n é o valor da variável j no laço externo. Temos que a complexidade de tempo do algoritmo neste caso será de O(n(n-1)) = O(n2-n) = O(n2).

Outra maneira de pensar sobre a inserção, pode ser imaginando-se em um jogo de cartas. Você está segurando as cartas na sua mão, e estas cartas são classificados. O negociante entrega-lhe exatamente uma nova carta. Você tem que colocá-la para o local correto para que as cartas que você está segurando ainda são classificadas. Em tipo de seleção, cada elemento que você adicionar ao subarray ordenada não é menor do que o elemento já na subarray classificada. Mas, no nosso exemplo a carta nova adquirida pode ser menor do que alguma das cartas que você já está segurando, assim você irá ordena-las, comparando a nova carta contra cada carta em sua mão, até encontrar o lugar para colocá-la. Você insere a nova carta no lugar certo, e mais uma vez, a sua mão segura cartas inteiramente ordenadas. Em seguida, o negociante dá-lhe outra carta, e você repete o mesmo procedimento. E assim sucessivamente, até que o negociante para de lhe dar mais cartas.

A ideia por trás do tipo de inserção é o Loop sobre posições na matriz, começando com o índice 1. Sendo cada nova posição como uma nova carta adquirida por você, que precisa ser inserida no local correto no subarray classificados à esquerda dessa posição.

Exemplo:

[pic 7]

Figura 5: Isertion Sort http://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261

Vantagens e Desvantagens

A principal vantagem da ordenação por inserção é a sua simplicidade, além de mostrar um bom desempenho em listas pequenas. É um algoritmo de ordenação de local, logo, o requerimento de espaço é mínimo.

A desvantagem é que não possui um desempenho tão bom quantos outros algoritmos de ordenação. Com n² passos necessários para funcionar, o insertion sort também não funciona bem com listas grandes.

Apostila da unicamp

http://www.ft.unicamp.br/liag/siteEd/includes/arquivos/MergeSortResumo_Grupo4_ST364A_2010.pdf

Ordenação pelo Método da Mergesort

O Mergesort é classificado como ordenação por partição, que parte do princípio de "dividir para conquistar". É uma técnica que foi utilizada pela primeira vez por Anatolii Karatsuba em 1960, consiste em dividir um problema maior em problemas menores, e sucessivamente até que o mesmo seja resolvido diretamente. A técnica é realizada em três fases:

Divisão: processo em que pegamos o problema e vamos dividido em problemas menores e assim subsequentemente de maneira recursiva, até que não possamos mais dividir.

Conquista: quando se alcança o a menor parte do problema.

Combinação: Combinação dos resultados dos menores problemas obtidos até que seja obtida a solução do problema maior. Os algoritmos que utilizam o método de partição são caracterizados como os mais rápidos dentre os outros, pelo fato de sua complexidade ser, na maioria das situações, O(nlogn). Os dois representantes mais ilustres desta classe são o quicksort e o mergesort.

- Não é um método in-place

Na ciência da computação, um algoritmo in-place é um algoritmo que transforma a entrada de informação usando Estrutura de Dados com pequena e constante quantidade de espaço de memória extra. A informação de entrada as vezes é sobrescrita por uma saída de dados como o algoritmo executa. Um algoritmo não in-place, como o Merge Sort, é chamado de out-of-place.

Aplicando Dividir para conquistar no MergeSort

Dividir: dividir a lista em duas listas com cerca da metade do tamanho.

Conquistar: dividir cada uma das duas sublistas recursivamente até que tenham tamanho um.

Combinar: unir as duas sublistas de volta em uma lista ordenada.

Sendo implementações estável na sua grande maioria, onde podem ser iterativas ou recursivas. Tem a desvantagem de utilizar uma estrutura auxiliar que ocupando o dobro de memória.

Destacando suas características em cima do paradigma de "divisão para conquista":

Dividir: se a sequência tiver mais de um elemento, dívida