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:
 
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
 
//escrever o vetor ordenado:
Para i De 0 Até 9 Passo 1
    Escrever a[i], " "
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,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() ) );
  }
}
</source

=== Código em [[C#]] ===
<source lang="csharp">
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 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 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