-
O consumo de tempo da função quicksort é proporcional ao número de comparações entre elementos do vetor. Se o índice j devolvido por separa estiver sempre mais ou menos a meio caminho entre p e r , o número de comparações será aproximadamente
n log2 n ,
sendo n o número de elementos do vetor. Caso contrário, o número de comparações estará na ordem de n2 . (Isso acontece, por exemplo, se o vetor já estiver ordenado ou quase ordenado.) Portanto, o pior caso do Quicksort não é melhor que o dos algoritmos elementares.
Felizmente, o pior caso é muito raro. Em média, o consumo de tempo do quicksort é proporcional a n log2 n .
-
"O método de classificação Quicksort é estável..."
O método QuickSort é instável. Os métodos de classificação estáveis são MergeSort, InsertionSort e BubbleSort.
"... e executado em tempo linearmente dependente da quantidade de dados que estão sendo classificados."
Não é linear - O(N). A complexidade do QuickSort é O(N * log(N)), isso no melhor caso e no caso médio. No pior caso, a complexidade do QuickSort é O(N²).
Abraços.
-
ESTÁVEL: Um algoritmo de ordenação diz-se estável se preserva a ordem de registros de chaves iguais. Isto é, se tais registros aparecem na sequência ordenada na mesma ordem em que estão na sequência inicial.
Esta propriedade é útil apenas quando há dados associados às chaves de ordenação.
Alguns algoritmos de ordenação estáveis:
· Bubble sort
· Insertionsort
· Merge sort
· Bucket sort
· Counting Sort2
Alguns algoritmos de ordenação não estável:
· Selection Sort (Dependedo algorítmo)
· Quick Sort
· Heap Sort
· Shell Sort
-
algoritmos estáveis - MIB, homens de preto - merge, insert e bubble sort
algoritmos instáveis - SSH Q, segurança - select, shell, heap e quick sort
-
Em Quicksort, a lista é dividida em parte esquerda e parte direita, sendo que os elementos da parte esquerda são todos menores do que os elementos da parte direita. Em seguida, as duas partes são ordenadas recursivamente.nao é linear pois seu desempenho é (n log n).
-
Força Guerreiro!!!!!!