Questão FC373176
Considere um vetor com n elementos. O método de ordenação
Algoritmos e Lógica de Programação
FCC · 2022
Considere um vetor com n elementos. O método de ordenação
- é chamado de estável (stable) se não altera a posição relativa de elementos com mesmo valor depois da ordenação. Por exemplo, o vetor v[ 77, 55, 22, 33, 44, 22] tem dois elementos iguais a 22; um método de ordenação estável mantém o 22 da posição 3 antes do 22 da posição 6.
- por Seleção (Selection Sort) é de ordem de complexidade cúbica ou O (n3) e sua estratégia é ir comparando e trocando os elementos de posição, colocando os maiores nas posições finais do vetor.
- da Bolha (Bubble Sort) é de ordem de complexidade cúbica ou O (n3) e sua estratégia é ir comparando e trocando os elementos de posição, colocando os menores nas posições iniciais do vetor.
- Quicksort, que é sempre O (log n), utiliza um pivô para dividir o vetor em uma sublista da direita e uma da esquerda, de modo que todo elemento da sublista da esquerda seja maior que os da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva.
- Quicksort, devido ao loop interno complexo (que o torna duas vezes mais lento que o Heapsort) não necessita de memória adicional e é sempre O (log n) qualquer que seja a ordem inicial dos elementos. Este é o método a ser usado para aplicações que não podem tolerar variações no tempo esperado de ordenação.
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
Um método de ordenação é chamado de estável quando não altera a posição relativa entre elementos que têm o mesmo valor. Ou seja, se dois itens A e B são iguais em termos de chave e A aparece antes de B no vetor inicial, após a ordenação A continuará antes de B.
No exemplo v[77, 55, 22, 33, 44, 22], os dois elementos iguais a 22 estão nas posições 3 e 6. Um algoritmo estável garantirá que, após ordenar por valor, o 22 originalmente na posição 3 permaneça antes do 22 originalmente na posição 6.
Essa propriedade é importante quando cada registro tem outras informações além da chave: a estabilidade preserva uma ordem secundária (por exemplo, data ou prioridade) sem necessidade de passos adicionais. Para testar estabilidade, basta marcar a ordem inicial (índices) e verificar se a ordem relativa entre iguais foi mantida.
Conteúdo do catálogo FC Concursos · Atualizado em