Selection sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Selection sort

algoritmo selection sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso total, auxiliar
Algoritmos
Animação do algoritmo selection sort.

A ordenação por seleção (do inglês, selection sort) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os elementos restantes, até os últimos dois elementos.

Descrição do Algoritmo[editar | editar código-fonte]

É composto por dois laços, um laço externo e outro interno. O laço externo serve para controlar o índice inicial e o mais interno percorre todo o vetor. Na primeira iteração do laço externo o índice começa de 0 e cada iteração ele soma uma unidade até o final do vetor e o laço mais interno percorre o vetor começando desse índice externo + 1 até o final do vetor. Isso ficará mais explícito no exemplo.

Exemplo:

vetor = 9 - 7 - 8 - 1 - 2 - 0 - 4

O primeiro laço o índice inicial é 0. O laço mais interno começa do índice 1 (índice_inicial_externo + 1) e percorre o vetor até acha o menor elemento, neste caso o número zero. O zero passa para a posição inicial do vetor que na primeira iteração do laço é 0.

0 - 7 - 8 - 1 - 2 - 9 - 4

Ao fim do laço interno o laço externo incrementa uma unidade, agora a posição inicial do vetor passa a ser 1, pois o zero já se encontra no lugar dele, não é preciso mais fazer verificações pois ele é o menor elemento deste vetor. Agora o processo se repete, buscando o segundo menor elemento, neste caso o um.

0 - 1 - 8 - 7 - 2 - 9 - 4

Consequentemente o terceiro menor, quarto menor,...

Assim sucessivamente até o vetor está ordenado.

0 - 1 - 2 -7 - 8 - 9 - 4

...

0 - 1 - 2 - 4 - 8 - 9 - 7

...

0 - 1 - 2 - 4 - 7 - 9 - 8

...

0 - 1 - 2 - 4 - 7 - 8 - 9

Complexidade[editar | editar código-fonte]

O Selection Sort compara a cada interação um elemento com os outros, visando encontrar o menor. Dessa forma, podemos entender que não existe um melhor caso mesmo que o vetor esteja ordenado ou em ordem inversa serão executados os dois laços do algoritmo, o externo e o interno. A complexidade deste algoritmo será sempre enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades .

Vantagens[editar | editar código-fonte]

  • Ele é um algoritmo simples de ser implementado em comparação aos demais.
  • Não necessita de uma vetor auxiliar (in-place).
  • Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória.
  • Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.

Desvantagens[editar | editar código-fonte]

  • Ele é um dos mais lentos para vetores de tamanhos grandes.
  • Ele não é estável.
  • Ele faz sempre comparações, independente do vetor está ordenado ou não.

Implementações[editar | editar código-fonte]

Código em VisualG[editar | editar código-fonte]

//exemplo de ordenação crescente de um vetor com dez posições:
 
Algoritmo "Selection sort"

var 
//declarar as variáveis:
a: vetor [0..9] de inteiro
i, j, aux, menor:inteiro

Inicio
//ordenar o vetor:
Para i de 0 ate 8 faca
    menor <- i
    Para j De i+1 ate 9 faca
        Se a[menor] > a[j] entao
            menor <- j
        Fimse
    Fimpara
        aux <- a[menor]
        a[menor] <- a[i]
        a[i] <- aux
Fimpara
 
//escrever o vetor ordenado:
Para i De 0 Ate 9 Passo 1 faca
    Escreva (a[i], " ")
Fimpara
Fimalgoritmo
~~~~

C[editar | editar código-fonte]

void selection_sort(int num[], int tam) 
{ 
  int i, j, min, aux;
  for (i = 0; i < (tam-1); i++) 
  {
     min = i;
     for (j = (i+1); j < tam; j++) {
       if(num[j] < num[min]) 
         min = j;
     }
     if (i != min) {
       aux = num[i];
       num[i] = num[min];
       num[min] = aux;
     }
  }
}
Código da ordenação SelectionSort com strings
void ordenar_selecao_nome() {
    int i,j,indmin;
    string min, aux;
    for(i=0; i< (tam-1); i++) {
        strcpy(min,vetor[i]);
        indmin = i;
        for(j=i+1; j<tam; j++) {
            if(strcmp(vetor[j],min)<0)
                strcpy(min,vetor[j]);
                indmin = j;
        }
        if(strcmp(vetor[i], min)>0) {
            strcpy(aux, vetor[i]);
            strcpy(vetor[i], vetor[indmin]);
            strcpy(vetor[indmin], aux);
        }
    }
}

Código em C++[editar | editar código-fonte]

template<class T>
void selection_sort( std::vector<T> &lista )
{
  for( std::vector<T>::iterator it = lista.begin(); it != lista.end()-1; ++it )
  {
    std::iter_swap( it, std::min_element( it, lista.end() ) );
  }
}

Código em C#[editar | editar código-fonte]

public void SelectionSort(int[] vetor)
{
    int min, aux;

    for (int i = 0; i < vetor.Length - 1; i++)
    {
        min = i;

        for (int j = i + 1; j < vetor.Length; j++)
            if (vetor[j] < vetor[min])
                min = j;

        if (min != i)
        {
             aux = vetor[min];
             vetor[min] = vetor[i];
             vetor[i] = aux;
        }
    }
}

Código em Pascal[editar | editar código-fonte]

program select_sort;
var
 X, i, J, M: integer;
begin
  for i := Low( A ) to High( A ) - 1 do
  begin
    M := i;
    for J := i + 1 to High( A ) do
      if A[ J ] < A[ M ] then
        M := J;
    X := A[ M ];
    A[ M ] := A[ i ];
    A[ i ] := X;
  end;
end.

Código em Java[editar | editar código-fonte]

public static int [] selection(int[] vetor) {
	    int menor;
	    int indiceMenor;
        for (int i = 0; i < vetor.length - 1; i++) {
            // antes de comparar, considera-se menor o valor atual do loop
            menor = vetor[i];
            indiceMenor = i;

            // compara com os outros valores do vetor
            for (int j = i + 1; j < vetor.length; j++){
                if (vetor[j] < menor){
                    menor = vetor[j];
                    indiceMenor = j;
                }
            }

            // troca os valores menor e maior
            vetor[indiceMenor] = vetor[i];
            vetor[i] = menor;
        }
        
        return vetor;
}

Código em Visual Basic[editar | editar código-fonte]

Public Function SelectionSort(Vetor(), tam)

Dim i, j
Dim min, aux

For i = 0 To tam
    min = i

    For j = i + 1 To tam
        If Vetor(j) < Vetor(min) Then min = j
    Next j
    
    If Vetor(i) <> Vetor(min) Then
        aux = Vetor(i)
        Vetor(i) = Vetor(min)
        Vetor(min) = aux
    End If
Next i

End Function

Código em Ruby[editar | editar código-fonte]

  def selection(array)
    a = array
      min = first
      first.upto(a.size-1) do |i|
        if a[min]  > a[i]
          min = i
        end 
      end
      a[first], a[min] = a[min], a[first]
    end
    print a
  end

Código em Python[editar | editar código-fonte]

def selection_sort (lista):
    for i in range(0,len(lista)):
        menor=i
        for k in range(i,len(lista)):
            if lista[k]<lista[menor]:
                menor=k
        lista[menor],lista[i]=lista[i],lista[menor]
    return lista

Código em PHP[editar | editar código-fonte]

<?php
	//cria um array desordenado
	$array = array(3,2,6,7,1,0,8,9,4,5);
	//exibe o array desordenado na tela
	print_r($array);
	//gera duas linhas em branco apenas para dar espaço
	echo "<br /><br />";
	//percorre o array para ordenar
	for ($i = 0; $i < count($array); $i++) {
		//define o primeiro índice como sendo o menor
		$menor = $i;
		//procura outro índice com valor menor anteriormente marcado
		//como menor
		for ($j = $i + 1; $j < count($array); $j++) {
			//compara se existe outro valor menor que o anteriormente marcado
			if ($array[$j] < $array[$menor]) {
				//determina o índice do novo valor menor encontrado
				$menor = $j;
			}
		}
		//compara se o índice definido no início foi modificado
		if ($menor != $i) {
			//realiza troca de valores conforme o índices
			$aux = $array[$i];
			$array[$i] = $array[$menor];
			$array[$menor] = $aux;
		}
	}
	//gera duas linhas em branco apenas para dar espaço
	echo "<br /><br />";
	//imprimi o array ordenadamente na tela
	print_r($array);
?>

Código em Scheme[editar | editar código-fonte]

(define selection-sort!
    (lambda (vec)
        (letrec ((aux-min
                    (lambda (i minimo pos-min)
                        (if (< i (vector-length vec))
                            (if (< (vector-ref vec i) minimo)
                                (aux-min (add1 i) (vector-ref vec i) i)
                                (aux-min (add1 i) minimo pos-min))
                            pos-min)))
                (aux-linha
                    (lambda (i)
                        (if (< i (sub1 (vector-length vec)))
                        ; percorre para cada valor
                            (begin
                                (let* ((base (vector-ref vec i))
                                    (pos-min (aux-min (add1 i) base i)))
                                (if (not (= i pos-min))
                                ; troca valores
                                    (begin
                                        (vector-set! vec i (vector-ref vec pos-min))
                                        (vector-set! vec pos-min base))))
                                (aux-linha (add1 i)))))))
            (aux-linha 0))))

Código em Haskell[editar | editar código-fonte]

selSort [] = []
selSort xs = let x = minimum xs in x : selSort (remove x xs)
  where remove _ [] = []
        remove a (x:xs)
          | x == a = xs
          | otherwise = x : remove a xs

Ver também[editar | editar código-fonte]