Para ordenar um vetor de 10 elementos usando-se a ordenação por seleção, a quantidade de comparações necessárias é igual a
- A)25.
Errada, porque 25 não corresponde à soma das comparações da ordenação por seleção para 10 elementos.
- B)65.
Errada, pois 65 superestima o total e não bate com a fórmula n(n-1)/2.
- C)35.
Errada, já que 35 fica abaixo do número real de comparações exigidas.
- D)45.
Certa, porque para 10 elementos a seleção faz 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 comparações.
- E)55.
Errada, pois 55 seria o total de comparações de outro raciocínio, não da ordenação por seleção.
Gabarito: D
Na ordenação por seleção, a ideia é simples: em cada passada, você procura o menor elemento da parte ainda não ordenada e o coloca na posição correta. Parece trabalho de formiguinha, e é mesmo, porque o algoritmo vai vasculhando o vetor inteiro, ou quase inteiro, repetidas vezes. O ponto-chave é que a quantidade de comparações não depende do conteúdo do vetor, mas do tamanho dele. Para um vetor com 10 elementos, a primeira passada faz 9 comparações, a segunda faz 8, depois 7, e assim por diante, até sobrar apenas 1. Então a conta fica 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45. É uma soma clássica da série de números naturais em ordem decrescente. Isso mostra a característica da ordenação por seleção: ela sempre tem custo quadrático em comparações, isto é, cresce como n(n-1)/2. Para n = 10, o resultado é 10 vezes 9 dividido por 2, que dá 45. Em prova, quando aparecer seleção, pense nessa fórmula antes de sair contando dedo a dedo. Por isso o gabarito é a alternativa D. A banca quer que você reconheça a lógica da seleção: cada elemento “resolve” uma posição e o restante do vetor é varrido para achar o menor, acumulando exatamente 45 comparações no caso de 10 elementos.