Selection sort

Selection sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	O(n2)
complexidade caso médio	O(n2)
complexidade melhor caso	O(n2)
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

O algoritmo possui complexidade O(n²) enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades O(nlogn).

Implementações

Código em Portugol

//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

void selection_sort(int num[], int tam) 
{ 
  int i, j, min;
  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) {
      int swap = num[i];
      num[i] = num[min];
      num[min] = swap;
    }
  }
}

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(strcmpi(vetor[i], vetor[j])>0) {
            strcpy(aux_char, vetor[i]);
            strcpy(vetor[i], vetor[j]);
            strcpy(vetor[j], aux_char);
        }
    }
}

Código em C++

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#

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

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<=n-1) 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

public static void SelectionSort(int[] v) {
   int index_min,
       aux;
 
   for (int i = 0; i < v.length; i++) {
       index_min = i;
       for (int j = i + 1; j < v.length; j++) {
          if (v[j] < v[index_min]) {
             index_min = j;
          }
       }
       if (index_min != i) {
         aux = v[index_min];
         v[index_min] = v[i];
         v[i] = aux;
       }
   }
}

Código em Visual Basic

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
 
    aux = Vetor(i)
    Vetor(i) = Vetor(min)
    Vetor(min) = aux
Next i
 
End Function

Código em Python

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

function selection_sort(&$array) {
        $len = count($array) -1;
        for($i=0; $i<=$len ; $i++) {
                $ini = $i;
                for($j=$i+1; $j<=$len; $j++) {
                        if ($array[$j] < $array[$i]) {
                                $ini = $j;
                        }
                }
                if ($ini != $i) {
                        $troca = $array[$i];
                        $array[$i] = $array[$ini];
                        $array[$ini] = $troca;
                }
        }
}

Ver também

• Ordenação de vector
• Quick sort
• Merge sort
• Bubble sort
• Heapsort
• Pesquisa binária

Referências