GabaritoD — 45.
Gabarito: letra D. A ordenação por seleção (selection sort) realiza exatamente n(n-1)/2 comparações. Para n=10, 10×9/2 = 45 comparações.
O algoritmo percorre o vetor, a cada iteração i (0 a n-2) compara o elemento da posição i com os n-1-i seguintes para encontrar o menor. Assim, o total de comparações é a soma dos inteiros de 1 a n-1: (n-1) + (n-2) + ... + 1 = n(n-1)/2. Substituindo n=10, obtém-se 45.
25 não corresponde a nenhuma fórmula típica; provavelmente distração.
65 não é o resultado da fórmula para n=10.
35 também não corresponde.
45 é exatamente 10×9/2, o total de comparações do selection sort para 10 elementos.
55 seria o resultado para n=11 (11×10/2=55), mas n=10.
Não confunda o número de comparações com o número de trocas (que é n-1 = 9) ou com a complexidade assintótica O(n²). O valor exato é a soma aritmética de 1 a n-1.
Memorize a fórmula n(n-1)/2 para o selection sort. Para quick sort, por exemplo, o número médio de comparações é O(n log n), mas o exato depende da implementação.
Gabarito: letra D.
Link permanente: /questoes/ce151512