Flashcard FC188900
Quantas comparações são necessárias para ordenar uma lista com n elementos usando o algoritmo de ordenação por seleção?
Análise Combinatória (Princípio Fundamental da Contagem, Arranjos, Combinações, Permutações)
CESGRANRIO · 2014
Quantas comparações são necessárias para ordenar uma lista com n elementos usando o algoritmo de ordenação por seleção?
Mostrar resposta e comentário
Resposta
Resposta: \( \frac{n(n-1)}{2} \) comparações.A ordenação por seleção realiza comparações sequenciais para encontrar o menor elemento da lista, removendo-o a cada passo.
Na primeira iteração, são feitas \(n-1\) comparações, na segunda \(n-2\), e assim sucessivamente, até a penúltima iteração com 1 comparação.
Portanto, o total de comparações é a soma dos números de 1 até \(n-1\):
\[\text{Total} = (n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2}\]
Exemplo:
Considere ordenar uma lista com 4 números: 8, 3, 5, 1.
- Na 1ª iteração, com 4 elementos, fazemos 3 comparações para achar o menor.
- Na 2ª iteração, com 3 elementos, fazemos 2 comparações.
- Na 3ª iteração, com 2 elementos, fazemos 1 comparação.
Total de comparações = 3 + 2 + 1 = 6.
De acordo com a fórmula: \( \frac{4(4-1)}{2} = \frac{12}{2} = 6 \) comparações.
⬇️ Assista à vídeoaula ⬇️ Aula sobre Princípio Fundamental da Contagem
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/187763
Conteúdo do catálogo FC Concursos · Atualizado em