Quicksort é um algoritmo recursivo que utiliza a estratégia da divisão e conquista. Considerada a mais rápida ordenação baseada em comparações sobre arranjos. Na prática, se bem implementado, executa quase sempre em Θ(n lg n). No pior caso pode executar em tempo Θ(n2).
O heapsort utiliza uma estrutura de dados chamada heap binário para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada. ... O heap é gerado e mantido no próprio vetor a ser ordenado.
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar....
A complexidade no tempo desse algoritmo de divisão e conquista é O(nlogn), sendo mais eficiente do que os algoritmos Bubble Sort, Selection Sort e Insertion Sort, que já foram analisados em artigos anteriores do blog. ... Como é de costume, também disponibilizarei o algoritmo codificado em Java, C e em JavaScript.
A complexidade de um algoritmo tem a ver com quanto tempo e memória esse algoritmo gasta de acordo com o tamanho de sua entrada.
A ideia da notação Big-O é descrever o comportamento geral (também chamado de assintótico, pois é o comportamento no limite conforme os dados crescem) do algoritmo em termos do crescimento do número de operações conforme cresce o número de elementos processados (a quantidade de itens é descrita, genericamente, por n ).
Ou seja, multiplicada por uma constante c, a função g(n) limita superiormente a função f(n), a partir de um determinado no. A expressão f(n) = O(g(n)) significa que f(n) não cresce mais que g(n), podendo crescer de forma igual ou inferior.