-
Método da Troca e Partição (QuickSort): é o mais rápido entre os métodos
apresentados até o momento, e também o mais utilizado. Esse método foi
proposto por C. A. R. Hoare em 1962 e parte do princípio que é mais rápido
classificar dois vetores com n/2 elementos cada um, do que um com n
elementos (dividir um problema maior em dois menores).
A parte mais delicada do método é o particionamento do vetor. O vetor é
particionado em três segmentos:
V[1], ..., V[i - 1] V[i] V[i + 1], ..., V[n]
(segmento 1) (segmento 2) (segmento 3)
A partição é realizada através da escolha arbitrária de um elemento (V[i])
de modo que os elementos no segmento 1 sejam menores, e os elementos
no segmento 3 sejam maiores do que o elemento escolhido V[i].
Após a ordenação dos segmentos 1 e 3, tem-se o vetor original
classificado. O processo de partição pode ser repetido para os segmentos
1 e 3.
Obs. Quando um segmento apresenta um número de elementos menor ou
igual a M (um número pré-estabelecido), aplica-se um método simples de
ordenação.
-
- Complexidade de tempo: θ(n lg2 n) no melhor caso e no caso médio e θ(n2) no pior caso;
- Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e θ(lg2 n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n2) no pior caso.
-
Essa questão deveria ter sido anulada, pois apresenta erro de notação.
teta(n): caso médio
ômega(n): pior caso
O(n): pior caso
Como a questão utiliza teta(n) para falar de pior caso, há erro de notação. Alguém comenta?
-
Olá galera, dica rápida, simples e free!!!!
PIOR MÉDIO MELHOR
QUICK SORT: O(n2) O(nlogn) O(nlogn)
A técnica de particionamento é uma arma poderosa que o quicksort possui.
Para maiores detalhes: https://pt.wikipedia.org/wiki/Quicksort
Go ahead!!!
-
Gabarito C
Quicksort - Escolhe-se um pivot e particiona-se a lista em duas sublistas: uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivot, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio é de O(n log n).
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !
-
c-
O método Quicksort é uma aplicação do princípio divide and conquer. Para a ordenação, inicialmente o vetor é dividido em uma sublista da direita e uma da esquerda, de modo que todo elemento da sublista da esquerda seja menor que o da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva. o pior caso é n². normal é nlogn