-
Merge Sort possui eficiência O( n log n) em qualquer situação. Insert Sort possui no pior caso O ( n2)Buble sort possui no pior caso O (n)Quick sort possui no pior caso O (n2) eselection sort possui no pior caso O (n2)
-
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.
Sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas.
Para isso, ele divide a sequência original em pares de dados, ordena-as;
depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.
Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:
1. Dividir: Dividir os dados em subsequências pequenas;
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.
Vantagens
- Algorítimo de ordenação de simples implementação e fácil entendimento utilizando chamadas recursivas.
Desvantagens
- Alto consumo de memória, devido a série de chamadas recursivas.
Fonte: http://pt.wikipedia.org/wiki/Merge_sort
-
Classificação por Intercalação: divide a tabela em dois ou mais segmentos, ordena estes segmentos e depois os intercalam, terminando, ao final, com um único segmento (toda a tabela) ordenado.
O principal algoritmo desta família é o mergesort.
-
Classificação por Inserção: dividem a tabela em dois segmentos, sendo o 1o ordenado e o 2o não ordenado. A seguir, todos os elementos do 2o segmento vão, um a um, sendo inseridos no 1o segmento. Os principais algoritmos desta família são inserção direta com busca seqüencial, inserção direta com busca binária e incrementos decrescentes (shellsort).
Classificação por Trocas: efetuam a classificação por comparação entre pares de chaves, trocando-as de posição caso estejam fora de ordem. Os principais algoritmos desta família são bubblesort, shakesort, combsort e quicksort.
-
A primeira colega está equivocada quanto ao pior caso do BubbleSort, que será sempre O(n2).
-
Dica simples, rápida e free! ;-)
PIOR MÉDIO MELHOR
BUBBLE SORT: O(n2) O(n2) O(n)
QUICK SORT: O(n2) O(nlogn) O(nlogn)
MERGE SORT: O(nlogn) O(nlogn) O(nlogn)
INSERCTION SORT: O(n2) O(n2) O(n)
HEAPSORT: O(nlogn) O(nlogn) O(nlogn)
SELECTION SORT: O(n2) O(n2) O(n2)
Para você ter uma noção do que é pior, médio e melhor veja o gráfico "Big-O Complexity Chart" no site a seguir:
http://bigocheatsheet.com/
Go ahead!!!
-
Gabarito A
MergeSort - divide para conquistar sucessivamente o vetor, e vai ordenando juntando os vetores. Geralmente se implementa recursivamente.
Algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) nlogn no pior caso.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !
-
a-
todos os outros sao n² no pior caso. merge sort e merge sort sao nlogn