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 O(n^2)
complexidade caso médio O(n^2)
complexidade melhor caso O(n^2)
complexidade de espaços pior caso O(n) total, O(1) auxiliar
Algoritmos
Animação do algoritmo selection sort.

O selection sort (do inglês, ordenação por seleção) é 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 O(n^2) enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades O(n log n).

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:
 
INICIO
//declarar as variáveis:
Inteiro a[10] <- {12, 7, 4, 50, 8, 15, 30, 21, 18, 1}
Inteiro i, j, aux, menor
 
//ordenar o vetor:
Para i de 0 ate 8 passo 1
    menor <- i
    Para j De i+1 Até 9 passo 1
        Se a[menor] > a[j] então
            menor <- j
        Fimse
Próximo
    Se menor =/= i então
        aux <- a[menor]
        a[menor] <- a[i]
        a[i] <- aux
    Fimse
Próximo
<gallery>
Ficheiro:Exemplo1.jpg|Legenda1
Ficheiro:Exemplo2.jpg|Legenda2
 
{| class="wikitable"
|-
! Texto do cabeçalho !! Texto do cabeçalho !! Texto do cabeçalho
|-
| Aplicações ||Biblioteca    ||Definições
|-
| App Store  ||Redes      ||Pesquisa
| iTunes     ||iPad Suite ||Themes
| Camera     ||Game Center||Help Center||
|-
| Pessoas    ||Informações||Meteorologia||
|}
 
|}
]]
</gallery>
//escrever o vetor ordenado:
Para i De 0 Até 9 Passo 1
    Escrever a[i], " "
escreva("O computador está pronto a ser utilizado")
Próximo
FIM
~~~~

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,n;
    for(i=0; i<n-1; i++) {
        for(j=i+1; j<n; j++) {
            if(strcmp(vetor[i], vetor[j])>0) {
            strcpy(aux_char, vetor[i]);
            strcpy(vetor[i], vetor[j]);
            strcpy(vetor[j], aux_char);
        }
    }
}

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 selectionsort(input,output);
 
Var
   i,tam,a,tmp,n	: integer;
   v	  	: array[1..50] of integer;
   trocou 	: boolean;
 
Begin
 
   tam:=n-1;
   a:=1;
   trocou:=true;
   while (trocou) and (a<=tam) do
   Begin
      trocou:=false;
      for i:=1 to tam do
	 if v[i]>v[i+1] then
	 Begin
	 tmp:=v[i];
	 v[i]:=v[i+1];
	 v[i+1]:=tmp;
	 trocou:=true;
	 End;
      tam:=tam-1;
      a:=a+1;
   End;
Readln;
End.

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

public static void selection(int[] array) {
	for (int fixo = 0; fixo < array.length - 1; fixo++) {
		int menor = fixo;
 
		for (int i = menor + 1; i < array.length; i++){
			if (array[i] < array[menor]){
				menor = i;
		}
}
		if (menor != fixo) {
			// Troca
                        int t = array[fixo];
                        array[fixo] = array[menor];
                        array[menor] = t;
		}
	}
}

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 selectsort (L):
	n=len(L)
	for i in range(n-1):
		mini = i
 
		for j in range(i+1,n):
			if(L[j]<L[mini]):
				mini=j
 
		L[i],L[mini]=L[mini],L[i]


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);
?>

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

Referências