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.

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 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:
 
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 passo 1 faca
    menor <- i
    Para j De i+1 ate 9 passo 1 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
    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))))

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

Referências