Scribd
Carregar
4 visualizações1 página

Select Sort

O Selection Sort é um algoritmo de ordenação que seleciona o menor elemento não ordenado e o coloca na posição correta, repetindo esse processo até que todo o array esteja ordenado. Possui complexidade de tempo O(n²) em todos os casos e não é estável, mas realiza no máximo n−1 trocas, sendo eficiente em situações onde o custo de escrita é alto. É um algoritmo in-place, não requerendo memória auxiliar significativa.

Enviado por

patriciodorivaldo
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
4 visualizações1 página

Select Sort

O Selection Sort é um algoritmo de ordenação que seleciona o menor elemento não ordenado e o coloca na posição correta, repetindo esse processo até que todo o array esteja ordenado. Possui complexidade de tempo O(n²) em todos os casos e não é estável, mas realiza no máximo n−1 trocas, sendo eficiente em situações onde o custo de escrita é alto. É um algoritmo in-place, não requerendo memória auxiliar significativa.

Enviado por

patriciodorivaldo
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd

SELECTION SORT

O Selection Sort é um algoritmo de ordenação simples e intuitivo. Ele percorre o array várias
vezes, selecionando o menor elemento ainda não ordenado e colocando-o na posição correta.

O algoritmo funciona em duas etapas principais:

1. Seleção do mínimo:
A cada iteração, o algoritmo percorre a parte não ordenada do array em busca do menor
elemento.

2. Troca (swap):
O menor elemento encontrado é trocado com o elemento na posição inicial da parte não
ordenada. Esse processo se repete, avançando a fronteira entre a parte ordenada e a não
ordenada, até que todo o array esteja em ordem.

O Selection Sort possui complexidade de tempo O(n²) em todos os cenários (melhor, médio e
pior caso), pois sempre realiza o mesmo número de comparações independentemente da
disposição inicial dos elementos. Em cada iteração i, percorre os n−i elementos restantes para
encontrar o mínimo, resultando em n(n−1)/2 comparações no total.

Assim como o Heap Sort, o Selection Sort não é estável, pois a operação de troca pode alterar
a ordem relativa de elementos com valores iguais. Em contrapartida, realiza no máximo n−1
trocas, o que o torna interessante quando o custo de escrita na memória é elevado. Além disso,
é um algoritmo in-place, não necessitando de memória auxiliar significativa.

Exemplo:

Array inicial Passo 1: mín=1 (idx 1) Após troca

3 1 5 2 4 3 1 5 2 4 1 3 5 2 4
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

Passo 2: mín=2 (idx 3) Após troca Passo 3: mín=3 (idx 3)

1 3 5 2 4 1 2 5 3 4 1 2 5 3 4
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

Após troca Passo 4: mín=4 (idx 4) Array ordenado

1 2 3 5 4 1 2 3 5 4 1 2 3 4 5
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

■ Elemento já ordenado ■ Mínimo atual (marcado em vermelho)

Você também pode gostar