Time and Space Complexity
Lição 7 de 9 do curso Selection Sort - Série DSA da Coddy.
Complexidade de Tempo:
- Melhor, Médio e Pior Caso: O(n2)
- O Selection Sort sempre varre toda a parte não ordenada para encontrar o mínimo, mesmo que o array já esteja ordenado. O número de comparações não depende da ordem de entrada.
Complexidade de Espaço:
- O(1)
- O Selection Sort é um algoritmo "in-place". Ele reorganiza os elementos usando apenas uma quantidade constante de memória extra, não importa quão grande seja a entrada.
Resumo:
- O Selection Sort é simples e eficiente em termos de memória.
- Ele realiza poucas trocas (no máximo n-1), o que é útil quando as operações de escrita são caras.
- Sua complexidade de tempo quadrática o torna uma escolha ruim para grandes conjuntos de dados, onde algoritmos como Merge Sort ou Quick Sort são preferidos.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Selection Sort - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity