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. Do russo, Сортировка выбором) é 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 (n-1) elementos restantes, até os últimos dois elementos.

Complexidade 1[editar | editar código-fonte]

O algoritmo possui complexidade enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades .

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
lista: array[1..1000] of integer;
a,b,c,backup,tamanho: integer;
begin
  for a := 1 to tamanho do
  begin
    c := a + 1;
    for b := c to tamanho do
    begin
      if (lista[a] > lista[b]) then
      begin
        backup := lista[a];
        lista[a] := lista[b];
        lista[b] := backup;
      end;
    end;
  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]

Referências