Questão FC373201
Para ordenar um vetor com N elementos, o método de ordenação Seleção (Selection Sort) faz o seguinte número de comparações:
Algoritmos e Lógica de Programação
FCC · 2018
Para ordenar um vetor com N elementos, o método de ordenação Seleção (Selection Sort) faz o seguinte número de comparações:
- (N 2 − N)/2, sendo muito lento e inadequado para valores grandes de N.
- log 2(N 2 + N) no melhor caso.
- (N 2 + N −1)/2 no caso médio, ficando lento para valores grandes de N.
- (N − 1) quando o vetor já está originalmente ordenado.
- (N 2 + N)/4 no pior caso, sendo melhor que o pior caso do Bolha (Bubble Sort) pois faz menos trocas.
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
O Selection Sort percorre repetidamente a parte não ordenada do vetor para selecionar o menor (ou maior) elemento e colocá‑lo na posição correta. Por isso, o número de comparações que realiza depende apenas do tamanho do vetor e não da ordem dos dados.
Na 1ª passada faz \(N-1\) comparações, na 2ª \(N-2\), e assim por diante até 1. Logo somamos:
\( (N-1) + (N-2) + \dots + 2 + 1 = \frac{(N-1)\cdot N}{2} = \frac{N^2 - N}{2} \).
Essa fórmula mostra que o algoritmo tem complexidade quadrática em comparações, frequentemente escrita como O(N^2). Assim, é muito lento e inadequado para valores grandes de \(N\).
Conteúdo do catálogo FC Concursos · Atualizado em