GabaritoA — Seleção
Gabarito: letra A (Seleção). O algoritmo que atende às características descritas é o Selection Sort (ordenação por seleção): não é estável, seu tempo de execução é quadrático (O(n²)) — mas a banca pode ter interpretado como linear em relação ao número de trocas (n-1 trocas) — e a entrada já ordenada não altera seu custo, pois ele sempre percorre todo o vetor para encontrar o menor elemento.
A questão cobra três propriedades fundamentais de algoritmos de ordenação: estabilidade, complexidade e sensibilidade à ordenação inicial. Vamos analisar cada alternativa:
Não é estável: O Selection Sort não preserva a ordem relativa de elementos iguais, pois pode trocar um elemento igual com outro de posição, quebrando a estabilidade.
Tempo de execução: No melhor, pior e médio caso, o Selection Sort realiza O(n²) comparações, e O(n) trocas. A afirmação de "tempo linear" na questão é imprecisa, mas o Selection Sort é o único entre as opções que não melhora com dados ordenados e é instável. As trocas são lineares, e talvez a banca tenha usado esse fato.
Entrada ordenada não melhora: O algoritmo sempre percorre o vetor inteiro para encontrar o menor elemento, independentemente da ordenação inicial, resultando sempre no mesmo número de comparações.
Shellsort: não é estável, mas sua complexidade depende da sequência de gaps, geralmente entre O(n log n) e O(n²). Entradas ordenadas podem melhorar o desempenho em algumas implementações, e o tempo não é linear.
Insertion Sort: é estável (preserva a ordem de elementos iguais). Além disso, seu melhor caso é O(n) quando a entrada já está ordenada, contrariando a característica de que a ordenação não melhora o custo.
Heapsort: não é estável, mas sua complexidade é O(n log n) em todos os casos, e o tempo não é linear. Embora não se beneficie de dados ordenados, a complexidade não é linear.
Quicksort: não é estável. Sua complexidade típica é O(n log n) e o pior caso é O(n²), que ocorre justamente quando a entrada está ordenada (dependendo da escolha do pivô). Portanto, a entrada ordenada piora o custo, não permanece igual.
Para provas de concurso, decore as três propriedades de cada algoritmo de ordenação: estabilidade, complexidade assimptótica e comportamento com dados ordenados. Uma tabela de resumo:
Algoritmo | Estável | Melhor Caso | Pior Caso | Melhora com ordenação? |
|---|---|---|---|---|
Seleção | Não | O(n²) | O(n²) | Não |
Inserção | Sim | O(n) | O(n²) | Sim |
Heapsort | Não | O(n log n) | O(n log n) | Não |
Quicksort | Não | O(n log n) | O(n²) | Não (piora) |
Shellsort | Não | O(n log n) | O(n²) | Depende |
A armadilha da questão está no termo "tempo linear", que é tecnicamente incorreto para o Selection Sort. A banca provavelmente considerou o número linear de trocas (n-1) como "tempo de execução". Na dúvida, lembre-se: o Selection Sort é o único que não melhora com dados ordenados e não é estável entre as alternativas.
Gabarito: letra A
Link permanente: /questoes/qq260081