Aula 09a Ordenação:BubbleSort, SelectSort e InsertSort

Bruno HottAlgoritmos e Estruturas de Dados IDECSI – UFOP

Bruno Hott 2

O Critério de Ordenação

● Ordena-se de acordo com uma chave:

typedef int TChave;

typedef struct{ TChave chave; /* outros componentes */}Item;

Bruno Hott 3

Características

● Estabilidade: relativo à manutenção da ordem original de itens de chaves iguais– Um método de ordenação é estável se a ordem relativa dos itens com

chaves iguais não se altera durante a ordenação.● Ordenação interna: arquivo a ser ordenado cabe todo na memória

principal.

Bruno Hott 4

Critério de Avaliação

● Sendo n o número de registros no arquivo, as medidas de complexidade relevantes são:– Número de comparações C(n) entre chaves.– Número de movimentações M(n) de itens

Bruno Hott 5

Outras Considerações

● O uso econômico da memória disponível é um requisito primordial na ordenação interna.

● Métodos de ordenação in situ são os preferidos.● Métodos que utilizam listas encadeadas não são muito utilizados.● Métodos que fazem cópias dos itens a serem ordenados possuem

menor importância.

Bruno Hott 6

Métodos simples

● Bolha (BubbleSort)● Seleção (SelectSort)● Inserção (InsertSort)

Bruno Hott 7

Método Bolha

● Os elementos vão “borbulhando” a cada iteração do método até a posição correta para ordenação da lista

● O método poderia parar quando nenhum elemento borbulhasse/trocasse de posição

● Como os elementos são trocados (borbulhados) frequentemente, há um alto custo de troca de elementos

Bruno Hott 8

Método Bolha

void Bolha( Item* v, int n ){ int i, j; Item aux; for( i = 0; i < n-1; i++ ) for( j = 1; j < n-i; j++ ) if( v[j].chave < v[j-1].chave ){ aux = v[j]; v[j] = v[j-1]; v[j-1] = aux; }}

Bruno Hott 9

Análise de Complexidade

● Comparações - C(n)

● Movimentações – M(n)

M(n) = 3C(n)

)(2

)1(2

)1)(20()1(

1)1()(

22

2

0

2

0

2

0

2

0

nOnn

nnn

nn

ininnCn

i

n

i

n

i

n

i

Bruno Hott 10

Ordenação por Bolha

● Vantagens:– Algoritmo simples– Algoritmo estável

● Desvantagens:– O fato de o arquivo já estar ordenado não ajuda reduzir o número de

comparações (o custo continua quadrático), porém o número de movimentação cai a zero.

● Possível modificação na atual implementação?

Bruno Hott 11

Método Bolha

void Bolha (Item* v, int n ){ int i, j, troca; Item aux; for( i = 0; i < n-1; i++ ){ troca = 0; for( j = 1; j < n-i; j++ ){ if( v[j].chave < v[j-1].chave ){ aux = v[j]; v[j] = v[j-1]; v[j-1] = aux; troca = 1; } if(troca == 0) break; } }}

Bruno Hott 12

Método Seleção

● Seleção do n-ésimo menor (ou maior) elemento da lista● Troca do n-ésimo menor (ou maior) elemento com a n-ésima

posição da lista● Uma única troca por vez é realizada

Bruno Hott 13

Método Seleção

void Selecao( Item* v, int n ){ int i, j, min; Item aux; for(i = 0; i < n - 1; i++){ min = i; for(j = i+1; j < n; j++) if( v[j].chave < v[min].chave) min = j; aux = v[min]; v[min] = v[i]; v[i] = aux; }}

Bruno Hott 14

Análise de Complexidade

● Comparações – C(n)

● Movimentações – M(n)M(n) = 3(n-1))(

2

)1(2

)1)(20()1(

1)1()(

22

2

0

2

0

2

0

2

0

nOnn

nnn

nn

ininnCn

i

n

i

n

i

n

i

Bruno Hott 15

Ordenação por Seleção

● Vantagens:– Custo linear no tamanho da entrada para o número de movimentos de

registros.– É o algoritmo a ser utilizado para arquivos com registros muito

grandes.– É muito interessante para arquivos pequenos.

● Desvantagens:– O fato de o arquivo já estar ordenado não ajuda em nada, pois o custo

continua quadrático.– O algoritmo não é estável.

Bruno Hott 16

Método Seleção – Melhoria!

void Selecao(Item* v, int n){ int i, j, min; Item aux; for( i = 0; i < n-1; i++ ){ min = i; for( j = i+1; j < n; j++ ) if( v[j].chave < v[min].chave) min = j; if( i != min ){ aux = v[min]; v[min] = v[i]; v[i] = aux; } }}

Bruno Hott 17

Método Inserção

● Algoritmo utilizado pelo jogador de cartas– As cartas são ordenadas da esquerda para direita uma por uma. – O jogador escolhe a segunda carta e verifica se ela deve ficar antes ou

na posição que está.– Depois a terceira carta é classificada, deslocando-a até sua correta

posição– O jogador realiza esse procedimento até ordenar todas as cartas

● Alto custo em remover uma carta de uma posição e colocá-la em outra quando a representação é por arranjos

Bruno Hott 18

Método Inserção

void Insercao( Item* v, int n ){ int i, j; Item aux; for( i = 1; i < n; i++ ){ aux = v[i]; j = i–1; while( (j >= 0) && (aux.chave < v[j].chave) ){ v[j+1] = v[j]; j--; } v[j+1] = aux; }}

Bruno Hott 19

Análise de Complexidade

● Comparações – C(n)– No anel mais interno, na i-ésima iteração, o valor de Ci é:

● melhor caso: Ci (n) = 1● pior caso: Ci (n) = i● caso medio: Ci(n) = 1/i (1 + 2 + ... + i) = (i+1)/2

– Assumindo que todas as permutações de n são igualmente prováveis no caso médio, temos:

● melhor caso: C(n) = (1 + 1 + ... + 1) = n - 1● pior caso: C(n) = (1 + 2 + ... + n-1) = n2/2 - n/2● caso medio: C(n) = (2 + 3 + ... + n ) = n½ 2/4 + n/4 – 1/2

Bruno Hott 20

Análise de Complexidade

● Movimentações – C(n)– No anel mais interno, na i-ésima iteração, o valor de Ci é:

● melhor caso: Ci (n) = 0● pior caso: Ci (n) = i● caso medio: Ci(n) = 1/i (0 + 1 + 2 + ... + i-1) = (i-1)/2

– Assumindo que todas as permutações de n são igualmente prováveis no caso médio, temos:

● melhor caso: C(n) = (2 + 2 + ... + 2) = 2n - 2● pior caso: C(n) = (2+1 + 2+2 + ... + 2+n-1) = (n2+3n-4)/2● caso médio: C(n) = (2 + 3 + ... + n ) = (n½ 2 + n – 2)/2

Bruno Hott 21

Ordenação por Inserção

● O número mínimo de comparações e movimentos ocorre quando os itens estão originalmente em ordem.

● O número máximo ocorre quando os itens estão originalmente na ordem reversa.

● É o método a ser utilizado quando o arquivo está “quase” ordenado.

● É um bom método quando se deseja adicionar uns poucos itens a um arquivo ordenado, pois o custo é linear.

● O algoritmo de ordenação por inserção é estável.

Bruno Hott 22

Ordenação Interna

● Métodos simples:– Adequados para pequenos arquivos.– Requerem O(n²) comparações.– Produzem programas pequenos.

● Métodos eficientes:– Adequados para arquivos maiores.– Requerem O(n log n) comparações.– Usam menos comparações.– As comparações são mais complexas nos detalhes.– Métodos simples são mais eficientes para pequenos arquivos.

Bruno Hott 1

Aula 09b Ordenação:QuickSort

Bruno HottAlgoritmos e Estruturas de Dados IDECSI – UFOP

Bruno Hott 2

Quicksort

● Proposto por Hoare em 1960 e publicado em 1962.● É o algoritmo de ordenação interna mais rápido que se conhece para

uma ampla variedade de situações.● Provavelmente é o mais utilizado.● A ideia básica é dividir o problema de ordenar um conjunto com n

itens em dois problemas menores.● Os problemas menores são ordenados independentemente.● Os resultados são combinados para produzir a solução final.

Bruno Hott 3

Quicksort

● A parte mais delicada do método é o processo de partição.● O vetor A [esq..dir] é rearranjado por meio da escolha

arbitrária de um pivô x.● O vetor A é particionado em duas partes:

– Parte esquerda: chaves ≤ x.– Parte direita: chaves ≥ x.

Bruno Hott 4

Quicksort - Partição

● Algoritmo para o particionamento:

1) Escolha arbitrariamente um pivô x.

2) Percorra o vetor a partir da esquerda até que A[i] ≥ x.

3) Percorra o vetor a partir da direita até que A[j] ≤ x.

4) Troque A[i] com A[j].5) Continue este processo até os apontadores i e j se cruzarem.

Bruno Hott 5

Quicksort - Após a Partição

● Ao final do algoritmo de partição, o vetor A[esq..dir] está particionado de tal forma que:– Os itens em A[esq], A[esq + 1], ..., A[j] são menores ou iguais a x;– Os itens em A[i], A[i + 1], ..., A[dir] são maiores ou iguais a x.

Bruno Hott 6

Quicksort - Exemplo

● O pivô x é escolhido como sendo:– O elemento central: A[(i + j) / 2].

● Exemplo:

3 6 4 5 1 7 2

Bruno Hott 7

Quicksort - Exemplo

3 6 4 5 1 7 2

3 2 4 1 5 7 6

1 2 4 3 5 7 6

.

.

.

1 2 3 4 5 7 6

Continua...

Caso especial: pivô já na posição correta

Bruno Hott 8

Quicksort - Exemplo

1 2 3 4 5 7 6

1 2 3 4 5 6 7Final

3 2 4 1 5 6 7

1 2 4 3 5 6 7

Bruno Hott 9

Quicksort - Partição

void particao(Item* A, int esq, int dir, int *i, int *j){ Item x, aux; *i = esq; *j = dir; x = A[(*i + *j)/2]; /* obtem o pivo x */ do{ while(x.chave > A[*i].chave) (*i)++; while(x.chave < A[*j].chave) (*j)--; if(*i <= *j){ aux = A[*i]; A[*i] = A[*j]; A[*j] = aux; (*i)++; (*j)--; } }while(*i <= *j);}

Bruno Hott 10

Quicksort

● O anel interno da função Particao é extremamente simples.● Razão pela qual o algoritmo Quicksort é tão rápido.

Bruno Hott 11

Quicksort - Função

void quickSort(Item *A, int n){ Ordena(A, 0, n-1);}

void ordena(Item *A, int esq, int dir){ int i,j; particao(A, esq, dir, &i, &j); if(esq < j ) ordena( A, esq, j ); if(i < dir) ordena( A, i, dir );}

Bruno Hott 12

Quicksort - Características

● Qual o pior caso para o Quicksort?● Qual o melhor caso?● O algoritmo é estável?

Bruno Hott 13

Quicksort - Análise

● Seja C(n) a função que conta o número de comparações.● Pior caso: C(n) = O(n²)● O pior caso ocorre quando, sistematicamente, o pivô é escolhido como

sendo um dos extremos de um arquivo já ordenado.● Isto faz com que o procedimento Ordena seja chamado recursivamente n

vezes, eliminando apenas um item em cada chamada.● O pior caso pode ser evitado empregando pequenas modificações no

algoritmo.● Para isso basta escolher três itens quaisquer do vetor e usar a mediana

dos três como pivô.

Bruno Hott 14

Quicksort - Análise

● Melhor caso:– C(n) = 2C(n/2) + n = n log n– Esta situação ocorre quando cada partição divide o arquivo em duas

partes iguais.● Caso médio de acordo com Sedgewick e Flajolet (1996, p. 17):

– C(n) ≈ 1,386n log n – 0,846n,– Isso significa que em média o tempo de execução do Quicksort é O(n log n).

Bruno Hott 15

Quicksort

● Vantagens:– É extremamente eficiente para ordenar arquivos de dados.– Necessita de apenas uma pequena pilha como memória auxiliar.– Requer cerca de n log n comparações em média para ordenar n itens.

● Desvantagens:– Tem um pior caso O(n²) comparações.– Sua implementação é muito delicada e difícil:– Um pequeno engano pode levar a efeitos inesperados para algumas entradas

de dados.– O método não é estável.

Bruno Hott 1

Aula 09c Ordenação:MergeSort

Bruno Hott 2

Problema de Ordenação

● Dado um arranjo com n números naturais, ordenar estes números em ordem crescente.

Entrada: 95 48 70 86 21 37

Saída: 21 37 48 70 86 95

Bruno Hott 3

Abordagem Dividir-para-Conquistar

● Método em Computação que consiste em – Dividir a entrada em conjuntos menores– Resolver cada instância menor de maneira recursiva– Reunir as soluções parciais para compor a solução do problema

original.

Bruno Hott 4

Abordagem Balanceamento

● Métodos de ordenação de divisão por conquista:– SelectSort– QuickSort (pior caso?)

● Divisão do problema de forma balanceada:– MergeSort

Bruno Hott 5

Exemplo de MergeSort

Entrada: 47 26 33 05 99 38 64 15

Divide: 47 26 33 05 99 38 64 15

● Resolve Recursivamente:– Primeira metade: 47 26 33 05

(Divide, Resolve recursivamente, Intercala obtendo 05 26 33 47)– Segunda metade: 99 38 64 15

(Divide, Resolve recursivamente, Intercala obtendo 15 38 64 99)

Bruno Hott 6

Exemplo de MergeSort

Entrada: 47 26 33 05 99 38 64 15

Resolve Recursivamente:

(Retorna 05 26 33 47 )

(Retorna 15 38 64 99 )

Intercala as soluções parciais:

05 15 26 33 38 47 64 99

Bruno Hott 7

Algoritmo MergeSort

void mergesort(Item* A,int ini,int fim){ int meio; if(fim == ini) return; meio = (ini+fim)/2; mergesort( A, ini, meio ); mergesort( A, meio+1, fim ); intercala( A, ini, meio, fim ); return; }}

Bruno Hott 8

Implementação de Intercala

intercalaAB(Item* C, Item* A, int n, Item* B, int m){ int i, j, k;

for(i = 0, j = 0, k = 0; k < n+m; k++){ if( i == n ) { C[k] = B[j++]; continue; } if( j == m ) { C[k] = A[i++]; continue; }

if( A[i].chave < B[j].chave ) C[k] = A[i++]; else C[k] = B[j++]; }}

Bruno Hott 9

Exemplo de MergeSort

2 6 8 5 10 9 12 1 15 7 3 13 4 11 16 142 6 5 8 10 9 12 1 15 7 3 13 4 11 16 142 5 6 8 10 9 12 1 15 7 3 13 4 11 16 142 5 6 8 9 10 12 1 15 7 3 13 4 11 16 142 5 6 8 9 10 1 12 15 7 3 13 4 11 16 142 5 6 8 1 9 10 12 15 7 3 13 4 11 16 141 2 5 6 8 9 10 12 15 7 3 13 4 11 16 141 2 5 6 8 9 10 12 7 15 3 13 4 11 16 141 2 5 6 8 9 10 12 7 15 3 13 4 11 16 141 2 5 6 8 9 10 12 3 7 13 15 4 11 16 141 2 5 6 8 9 10 12 3 7 13 15 4 11 16 141 2 5 6 8 9 10 12 3 7 13 15 4 11 14 161 2 5 6 8 9 10 12 3 7 13 15 4 11 14 161 2 5 6 8 9 10 12 3 4 7 11 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Bruno Hott 10

Implementação de Intercala

intercala(Item* A, int ini, int meio, int fim){ int i, j, k; Item* C = (int*) malloc((fim-ini+1)*sizeof(Item)); for(i = ini, j = meio+1, k = 0; k <= fim-ini; k++){ if( i == meio+1 ) { C[k] = A[j++]; continue; } if( j == fim+1 ) { C[k] = A[i++]; continue; }

if( A[i].chave < A[j].chave ) C[k] = A[i++]; else C[k] = A[j++]; } for(i = ini, k = 0; i <= fim; i++, k++){ A[i] = C[k]; } free(C);}

Bruno Hott 11

Complexidade do MergeSort

Para que teremos que fazer com que

Então:

Bruno Hott 12

MergeSort

● Vantagens– Como HeapSort, MergeSort é O(n log n)– Indicado para aplicações que exigem restrição de tempo (executa sempre

em um determinado tempo para um dado n)– Passível de ser transformado em estável

● Implementação de intercala

– Fácil Implementação● Desvantagens

– Utiliza memória auxiliar – O(n)– Na prática mais lento que HeapSort

Bruno Hott 1

Aula 09d Ordenação:Heapsort

Bruno HottAlgoritmos e Estruturas de Dados IDECSI – UFOP

Bruno Hott 2

Filas de Prioridades

● É uma estrutura de dados onde a chave de cada item reflete sua habilidade relativa de abandonar o conjunto de itens rapidamente.

● Aplicações:– SOs usam filas de prioridades, nas quais as chaves representam o

tempo em que eventos devem ocorrer.– Métodos numéricos iterativos são baseados na seleção repetida de um

item com maior (menor) valor.– Sistemas de gerência de memória usam a técnica de substituir a

página menos utilizada na memória principal por uma nova página.

Bruno Hott 3

Filas de Prioridades (TAD) - Operações

1) Constrói uma fila de prioridades a partir de um conjunto com n itens.

2) Informa qual é o maior item do conjunto.

3) Retira o item com maior chave.

4) Insere um novo item.

5) Aumenta o valor da chave do item i para um novo valor que é maior que o valor atual da chave.

6) Substitui o maior item por um novo item.

7) Altera a prioridade de um item.

8) Remove um item qualquer.

9) Agrupar duas filas de prioridades em uma única.

Bruno Hott 4

Filas de Prioridades - Representação

● Lista linear não ordenada:– Constrói é O(n)– Insere é O(1)– Retira é O(n)– Altera é O(n)

● Lista linear ordenada:– Constrói é O(n log n) ( ou O(n²) )– Insere é O(n)– Retira é O(1)– Altera é O(n)

Bruno Hott 5

Filas de Prioridades - Representação

● A melhor representação é através de uma estruturas de dados chamada heap:– Neste caso, Constrói é O(n).– Insere, Retira, Substitui e Altera são O(log n).

● Observação:– Para implementar a operação Agrupar de forma eficiente e ainda

preservar um custo logarítmico para as operações Insere, Retira, Substitui e Altera é necessário utilizar estruturas de dados mais sofisticadas, tais como árvores binomiais (Vuillemin, 1978).

Bruno Hott 6

Filas de Prioridades

● As operações das filas de prioridades podem ser utilizadas para implementar algoritmos de ordenação.

● Basta utilizar repetidamente a operação Insere para construir a fila de prioridades.

● Em seguida, utilizar repetidamente a operação Retira para receber os itens na ordem reversa.

Bruno Hott 7

Usando Listas de Prioridades

● O uso de listas lineares não ordenadas corresponde ao método da Seleção.

● O uso de listas lineares ordenadas corresponde ao método da Inserção.

● O uso de heaps corresponde ao método Heapsort.

Bruno Hott 8

Heaps

É uma seqüência de itens com chavesc[1], c[2], ... , c[n], tal que: c[i] >= c[2*i], c[i] >= c[2*i + 1],para todo i = 1, 2, ..., n/2

Bruno Hott 9

Heaps

● A definição pode ser facilmente visualizada em uma árvore binária completa:

Bruno Hott 10

Heaps

● Árvore binária completa:– Os nós são numerados de 1 a n.– O primeiro nó é chamado raiz.– O nó ⌊k/2⌋ é o pai do nó k, para 1 < k <= n.– Os nós 2k e 2k + 1 são os filhos à esquerda e à direita do nó k, para 1 <= k <= ⌊n/2⌋.

Bruno Hott 11

Heaps

● As chaves na árvore satisfazem a condição do heap.● A chave em cada nó é maior do que as chaves em seus filhos.● A chave no nó raiz é a maior chave do conjunto.● Uma árvore binária completa pode ser representada por um array:

Bruno Hott 12

Heaps

● A representação é extremamente compacta.● Permite caminhar pelos nós da árvore facilmente.● Os filhos de um nó i estão nas posições 2i e 2i + 1.● O pai de um nó i está na posição i/2.● Na representação do heap em um arranjo, a maior chave está sempre na

posição 1 do vetor.● Os algoritmos para implementar as operações sobre o heap operam ao

longo de um dos caminhos da árvore.● Um algoritmo elegante para construir o heap foi proposto por Floyd em

1964.

Bruno Hott 13

Heaps

● O algoritmo não necessita de nenhuma memória auxiliar.● Dado um vetor A[1], A[2], ..., A[n].● Os itens A[n/2 + 1], A[n/2 + 2], ..., A[n] formam um heap:

– Neste intervalo não existem dois índices i e j tais que j = 2i ou j = 2i + 1.

Bruno Hott 14

Heaps

● Algoritmo:

Bruno Hott 15

Heaps

● Os itens de A[4] a A[7] formam um heap.● O heap é estendido para a esquerda (Esq = 3), englobando o item A[3], pai

dos itens A[6] e A[7].● A condição de heap é violada:

– O heap é refeito trocando os itens D e S.● O item R é incluindo no heap (Esq = 2), o que não viola a condição de

heap.● O item O é incluindo no heap (Esq = 1).● A Condição de heap violada:

– O heap é refeito trocando os itens O e S, encerrando o processo.

Bruno Hott 16

Heaps

● O Programa que implementa a operação que informa o item com maior chave:

Item max(Item *A){ return (A[1]);}

Bruno Hott 17

Heaps

● Programa para refazer a condição do heap:

void refaz(Item* A, int esq, int dir){ int i = esq, j = i*2; Item aux = A[i];

while( j <= dir ){ if( j < dir ) if( A[j].chave < A[j+1].chave ) j++; if( aux.chave >= A[j].chave ) break; A[i] = A[j]; i = j; j = i*2; } A[i] = aux;}

Bruno Hott 18

Heaps

● Programa para construir o heap:

void constroi(Item *A, int *n){ int esq = *n / 2;

while(esq > 0){ refaz(A, esq, *n); esq--; }}

Bruno Hott 19

Heaps

● Programa que implementa a operação de retirar o item com maior chave:

Item retiraMax(Item *A, int *n){ Item max; if (*n < 1) printf(“Erro: heap vazio\n”); else{ max = A[1]; A[1] = A[*n]; (*n)--; refaz(A, 1, *n); } return max;}

Bruno Hott 20

Heaps

● Programa que implementa a operação de aumentar o valor da chave do item i:

void aumentaChave(Item* A, int i, TChave novo){ Item aux; if(novo < A[i].chave){ printf(“Erro: Chave Nova menor que a chave atual”); return; }

A[i].chave = novo; while( i > 1 && A[i/2].chave < A[i].chave ){ aux = A[i/2]; A[i/2] = A[i]; A[i] = aux; i /= 2; }}

Bruno Hott 21

Heaps

● Exemplo da operação de aumentar o valor da chave do item na posição i:

● O tempo de execução do procedimento aumentaChave em um item do heap é O(log n).

Bruno Hott 22

Heaps

● Programa que implementa a operação de inserir um novo item no heap:

void insere(Item* A, int* n, Item* x){ (*n)++; A[*n] = *x; A[*n].chave = INT_MIN; aumentaChave(A, *n, x->chave);}

Bruno Hott 23

Heapsort - Algoritmo

1) Construir o heap.

2) Troque o item na posição 1 do vetor (raiz do heap) com o item da posição n.

3) Use o procedimento refaz para reconstituir o heap para os itens A[1], A[2], ..., A[n-1].4) Repita os passos 2 e 3 com os n-1 itens restantes, depois com os

n-2, até que reste apenas um item.

Bruno Hott 24

Heapsort

● Exemplo de aplicação do Heapsort:

Bruno Hott 25

Heapsort

● O caminho seguido pelo procedimento refaz para reconstituir a condição do heap está em negrito.

● Por exemplo, após a troca dos itens S e D na segunda linha da Figura, o item D volta para a posição 5, após passar pelas posições 1 e 2.

Bruno Hott 26

Heapsort

● Programa que mostra a implementação do Heapsort:

void Heapsort(Item *A, int *n){ int esq, dir; Item x; constroi(A, n); esq = 1; dir = n; while(dir > 1){ x = A[1]; A[1] = A[dir]; A[dir] = x; dir--; refaz(A, esq, dir); }}

Bruno Hott 27

Heapsort - Análise

● refaz - gasta cerca de log n operações, no pior caso.● constroi – executa O(n) * refaz● Loop interno – executa (n) * refaz● Logo, Heapsort gasta um tempo de execução proporcional a

n log n, no pior caso.

Bruno Hott 28

Heapsort - Análise

● Vantagens:– O comportamento do Heapsort é sempre O(n log n), qualquer que seja a

entrada.● Desvantagens:

– O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort.

– O Heapsort não é estável.● Recomendado:

– Para aplicações que não podem tolerar eventualmente um caso desfavorável.– Não é recomendado para arquivos com poucos registros, por causa do tempo

necessário para construir o heap.