Selection Sort

Prévia do material em texto

Selection Sort
Selection Sort é um algoritmo de ordenação simples e intuitivo. A ideia principal é dividir a
lista em duas partes: a parte ordenada e a parte não ordenada. No início, a parte ordenada está
vazia e a parte não ordenada contém todos os elementos. O algoritmo funciona da seguinte
maneira:
Encontrar o menor elemento na parte não ordenada da lista.
Trocar esse menor elemento com o primeiro elemento da parte não ordenada.
Mover a fronteira entre a parte ordenada e a parte não ordenada é um elemento para a direita.
Repetir os passos acima até que toda a lista esteja ordenada.
Exemplo:
Para ordenar a lista [64, 25, 12, 22, 11]:
Passo 1: Encontrar o menor elemento (11) e trocar com o primeiro elemento (64). A lista fica
[11, 25, 12, 22, 64].
Passo 2: Encontrar o segundomenor elemento (12) e trocar com o segundo elemento (25). A
lista fica [11, 12, 25, 22, 64].
Passo 3: Encontrar o terceiro menor elemento (22) e troca com o terceiro elemento (25). A lista
fica [11, 12, 22, 25, 64].
Passo 4: Encontrar o quarto menor elemento (25) e trocar com o quarto elemento (25). A lista
fica [11, 12, 22, 25, 64].
Agora a lista está ordenada.
Insertion Sort
Insertion Sort é outro algoritmo de ordenação simples que constrói a lista ordenada de um
elemento por vez. Ele é mais eficiente do que o Selection Sort emmuitos casos, especialmente
em listas parcialmente ordenadas. O algoritmo funciona da seguinte maneira:
Começar com o segundo elemento (considerando o primeiro elemento como a lista ordenada).
Comparar o segundo elemento com os elementos da lista ordenada (à esquerda) e inserir esse
elemento na posição correta.
Repetir o processo para o terceiro elemento, quarto elemento, e assim por diante até que todos
os elementos estejam ordenados.
Exemplo:
Para ordenar a lista [64, 25, 12, 22, 11]:
Passo 1: Começar com o segundo elemento (25). Comparar com o primeiro (64) e inserir 25 na
posição correta. A lista fica [25, 64, 12, 22, 11].
Passo 2: Pegar o terceiro elemento (12). Comparar com 64 e 25 e inserir 12 na posição correta. A
lista fica [12, 25, 64, 22, 11].
Passo 3: Pegar o quarto elemento (22). Comparar com 64, 25 e 12 e inserir 22 na posição
correta. A lista fica [12, 22, 25, 64, 11].
Passo 4: Pegar o quinto elemento (11). Comparar com 64, 25, 22 e 12 e
inserir 11 na posição correta. A lista fica [11, 12, 22, 25, 64].
Agora a lista está ordenada.
Comparação entre Selection Sort e Insertion
Sort
Complexidade Temporal: Ambos têm complexidade O ( n2 ) no pior caso. Insertion Sort pode
ser mais eficiente em listas parcialmente ordenadas com complexidade média de O ( N ) para
listas quase ordenadas.
Complexidade Espacial: Ambos têm complexidade espacial O ( 1 ) pois são algoritmos in-place,
ou seja, não requerem espaço adicional significativo além da entrada.
Estabilidade: Insertion Sort é estável (mantém a ordem relativa dos elementos iguais).
Selection Sort não é estável (a ordem relativa dos elementos iguais pode mudar).
Utilização: Insertion Sort é preferível quando a lista é pequena ou quase ordenada. Selection
Sort pode ser usado quando a estabilidade não é um requisito e a simplicidade do algoritmo é
desejada.
Resumo:
Selection Sort: Encontra o menor elemento da parte não ordenada e omove para a parte
ordenada. É simples mas geralmente menos eficiente que o Insertion Sort.
Insertion Sort: Insere cada elemento na posição correta na parte ordenada. É eficiente para
listas pequenas ou parcialmente ordenadas e é estável.
Ambos são algoritmos básicos de ordenação, adequados para entender conceitos
fundamentais, mas em aplicações práticas, algoritmos mais eficientes comoMerge Sort, Quick
Sort, ou Heapsort são geralmente preferidos.
1. Como funciona o Selection Sort?
O Selection Sort divide a lista em duas partes: a parte ordenada e a parte não ordenada.
Ele entra pela lista, encontrando omenor elemento na parte não ordenada e trocando-o
com o primeiro elemento dessa parte. A fronteira entre as partes ordenada e não
ordenada é movida um elemento para a direita a cada iteração até que a lista esteja
completamente ordenada.
2. Qual é a complexidade temporal do Selection Sort no pior caso?
A complexidade temporal do Selection Sort no pior caso é O (n2). Isso ocorre porque,
para cada um dos n elementos, o algoritmo faz uma comparação com cada um dos
elementos restantes na parte não ordenada, resultando em n + ( n - 1 ) + ( n - 2 ) + ... + 1
comparações, o que é aproximadamente n2/2
3. Como o Insertion Sort insere elementos na lista?
O Insertion Sort considera o segundo elemento como o ponto de partida da lista
ordenada e insere cada elemento subsequente na posição correta em relação aos
elementos já ordenados. Ele compara o elemento atual com os elementos da parte
ordenada da lista, movendo-os para a direita até encontrar a posição correta para
inserir o elemento atual.
4. Quando o Insertion Sort é mais eficiente que o Selection Sort?
O Insertion Sort é mais eficiente que o Selection Sort em listas que já estão parcialmente
ordenadas ou são pequenas. Em listas quase ordenadas, o Insertion Sort pode alcançar
uma complexidade temporal média de O (n), pois requer menos movimentos de
elementos.
5. Qual a diferença de estabilidade entre o Selection Sort e o Insertion Sort?
O Insertion Sort é estável, o que significa que ele mantém a ordem relativa dos
elementos iguais. O Selection Sort não é estável, pois ao trocar elementos, ele pode
alterar a ordem relativa dos elementos iguais.
6. Pode-se dizer que o Selection Sort é um algoritmo in-place?
Sim, o Selection Sort é um algoritmo in-place porque ele realiza a ordenação dentro da
própria lista de entrada, sem requerer espaço adicional significativo além de algumas
variáveis temporárias.
7. Qual é a complexidade espacial do Insertion Sort e do Selection Sort?
A complexidade espacial de ambos os algoritmos é O (1) já que eles são algoritmos
in-place e não necessitam de espaço adicional proporcional ao tamanho da entrada
para realizar a ordenação.
8. Como o Insertion Sort se comporta em listas quase ordenadas?
Em listas quase ordenadas, o Insertion Sort é muito eficiente, com uma complexidade
média próxima de O (n) . Isso acontece porque cada elemento já está próximo de sua
posição final, necessitando poucas comparações e movimentações.
9. Em quais cenários o Selection Sort pode ser preferível ao Insertion Sort?
O Selection Sort pode ser preferível em cenários onde a simplicidade do algoritmo é
desejada e a estabilidade não é um requisito. Ele é fácil de implementar e entender, e
seu comportamento é consistente independentemente da ordem inicial dos elementos.
10. Qual algoritmo você escolheria para ordenar uma lista pequena e por quê?
Para ordenar uma lista pequena, eu escolheria o Insertion Sort. Ele geralmente é mais
eficiente para listas pequenas devido ao seu desempenho relativamente bom em tais
casos e à sua simplicidade de implementação. Além disso, ele é estável e realiza menos
trocas de elementos comparado ao Selection Sort.