Selection sort

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^{2})$ enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades $O(nlogn)$.

Implementações

Código em 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 j;
    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() ) );
  }
}

Para visualizar esquematização 3D, copie e cole o seguinte link no navegador:

• www.own3d.es

Código em C#

public int[] ordernar(int[] vetor)
{
    int aux = 0;
    for (int i = 0; i < vetor.Length - 1; i++)
    {
        for (int j = i + 1; j < vetor.Length; j++)
        {
            if (vetor[j] < vetor[i])
            {
                aux = vetor[j];
                vetor[j] = vetor[i];
                vetor[i] = aux;
            }
        }
    }
    return vetor;
}

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