Selection sort
Origem: Wikipédia, a enciclopédia livre.
O selection sort, ou 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.
Índice |
[editar] Complexidade
O algoritmo possui complexidade O(n2) enquanto que, por exemplo, os algoritmos Heap Sort e Merge Sort possuem complexidades O(n log n).
[editar] Implementações
[editar] Código em C
void selectionSort(int vetor[],int tam)
{
int i,j;
int min,aux;
for (i=0;i<tam-1;i++)
{
min=i;
for (j=i+1;j<tam;j++)
{
if (vetor[j]<vetor[min])
min=j;
}
aux=vetor[i];
vetor[i]=vetor[min];
vetor[min]=aux;
}
}
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);
}
}
}
}
[editar] Código em C++
template<class T>
void selection_sort( std::vector<T> &lista )
{
std::vector<T>::iterator it;
for( it = lista.begin(); it != lista.end()-1; ++it )
{
std::iter_swap( it, std::min_element( it, lista.end() ) );
}
}
[editar] Código em Pascal
Program selectionsort(input,output);
Var
i,tam,a,tmp : 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;
End.
[editar] Código em Java
public void SelectionSort(int[] v) {
int index_min;
int 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[j-1];
v[j-1] = aux;
}
}
}
}
[editar] 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
