Selection sort

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) é 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.

Descrição do algoritmo

É composto por dois laços, um laço externo e outro interno. O laço externo serve para controlar o índice inicial e o interno percorre todo o vetor. Na primeira iteração do laço externo o índice começa de 0 e cada iteração ele soma uma unidade até o final do vetor e o laço mais interno percorre o vetor começando desse índice externo + 1 até o final do vetor. Isso ficará mais explícito no exemplo.

Exemplo:

vetor = 9 - 7 - 8 - 1 - 2 - 0 - 4

O primeiro laço o índice inicial é 0. O laço mais interno começa do índice 1 (índice_inicial_externo + 1) e percorre o vetor até achar o menor elemento, neste caso o número zero. O zero passa para a posição inicial do vetor que na primeira iteração do laço é 0.

0 - 7 - 8 - 1 - 2 - 9 - 4

Ao fim do laço interno, o laço externo incrementa uma unidade, agora a posição inicial do vetor passa a ser 1, pois o zero já se encontra no lugar dele, não é preciso mais fazer verificações pois ele é o menor elemento deste vetor. Agora o processo se repete, buscando o segundo menor elemento, neste caso o um.

0 - 1 - 8 - 7 - 2 - 9 - 4

Consequentemente o terceiro menor, quarto menor,...

Assim sucessivamente até o vetor está ordenado.

0 - 1 - 2 -7 - 8 - 9 - 4

...

0 - 1 - 2 - 4 - 8 - 9 - 7

...

0 - 1 - 2 - 4 - 7 - 9 - 8

...

0 - 1 - 2 - 4 - 7 - 8 - 9

Complexidade

O selection sort compara a cada interação um elemento com os outros, visando encontrar o menor. Dessa forma, podemos entender que não existe um melhor caso mesmo que o vetor esteja ordenado ou em ordem inversa serão executados os dois laços do algoritmo, o externo e o interno. A complexidade deste algoritmo será sempre $O(n^{2})$ enquanto que, por exemplo, os algoritmos heapsort e mergesort possuem complexidades $O(n\log n).$

Vantagens

• Ele é um algoritmo simples de ser implementado em comparação aos demais.
• Não necessita de um vetor auxiliar (in-place).
• Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória.
• Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.

Desvantagens

• Ele é um dos mais lentos para vetores de tamanhos grandes.
• Ele não é estável.
• Ele faz sempre $(n^{2}-n)/2$ comparações, independentemente do vetor estar ordenado ou não.

Implementações

C

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

Colocando os menores no início:

void SelectionSort(int vetor[], int tam) {
    for (int indice = 0; indice < tam; ++indice) {
        int indiceMenor = indice;
        for (int indiceSeguinte = indice+1; indiceSeguinte < tam; ++indiceSeguinte) {
            if (vetor[indiceSeguinte] < vetor[indiceMenor]) {
                indiceMenor = indiceSeguinte;
            }
        }
        int aux = vetor[indice];
        vetor[indice] = vetor[indiceMenor];
        vetor[indiceMenor] = aux;
    }
}

C#

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 (vetor[i] != vetor[min])
        {
            aux = vetor[i];
            vetor[i] = vetor[min];
            vetor[min] = aux;
        }
    }
}

Python

def selection_sort(lista):
  """ Ordena uma lista. Custo O(n²) """
  
  n = len(lista) # tamanho da lista

  if n == 1:  # caso base
    return lista[0] 

  # Loop externo para iterar sobre os índices da lista
  for i in range(n-1):
    
    menor = i  # primeiro índice inicia como o menor

    # Loop interno para encontrar o índice do menor elemento
    for j in range(i + 1, n):
      if lista[j] < lista[menor]:
        menor = j

    # Se o elemento atual não é o menor, troca
    if lista[i] != lista[menor]:
      aux = lista[i]
      lista[i] = lista[menor]
      lista[menor] = aux

  return lista 

# USO
lista_desordenada = [3,2,1] # Lista de números desordenados
lista_ordenada = selection_sort(lista_desordenada) # ordena
print(lista_ordenada) # [1, 2, 3]

V

// Loop

fn selection_sort_loop<T>(mut array_to_sort []T, compare fn (a T, b T) bool) {
  array_to_sort_len := array_to_sort.len

  for i in 0..array_to_sort_len {
    // index of lowest
    mut ilo := i

    for j in i + 1..array_to_sort_len {
      if compare(array_to_sort[ilo], array_to_sort[j]) {
        ilo = j
      }
    }

    //if i != ilo {
      array_to_sort[i], array_to_sort[ilo] = array_to_sort[ilo], array_to_sort[i]
      /*tmp := array_to_sort[i]
      array_to_sort[i] = array_to_sort[ilo]
      array_to_sort[ilo] = tmp*/
    //}
  }
}


fn selection_sort_loop_clone<T>(array_to_sort []T, compare fn (a T, b T) bool) []T {
  mut array_to_sort_clone := array_to_sort.clone()

  selection_sort_loop<T>(mut array_to_sort_clone, compare)

  return array_to_sort_clone
}

// Recursion

fn selection_sort_recursion<T>(mut array_to_sort []T, compare fn (a T, b T) bool) {
  array_to_sort_len := array_to_sort.len

  //if array_to_sort_len <= 1 { return }

  // index of lowest
  i := 0
  mut ilo := i

  for j in i + 1..array_to_sort_len {
    if compare(array_to_sort[ilo], array_to_sort[j]) {
      ilo = j
    }
  }

  //if i != ilo {
    array_to_sort[i], array_to_sort[ilo] = array_to_sort[ilo], array_to_sort[i]
    /*tmp := array_to_sort[i]
    array_to_sort[i] = array_to_sort[ilo]
    array_to_sort[ilo] = tmp*/
  //}

  if i + 1 < array_to_sort_len {
    selection_sort_recursion<T>(mut array_to_sort[i + 1..], compare)
  }
}

fn selection_sort_recursion_clone<T>(array_to_sort []T, compare fn (a T, b T) bool) []T {
  mut array_to_sort_clone := array_to_sort.clone()

  selection_sort_recursion<T>(mut array_to_sort_clone, compare)

  return array_to_sort_clone
}

// Selection Sort

enum LoopRec {
  loop
  recursion
}

fn selection_sort<T>(mut array_to_sort []T, compare fn (a T, b T) bool, loop_rec LoopRec) {
  match loop_rec {
    .loop { selection_sort_loop<T>(mut array_to_sort, compare) }
    .recursion { selection_sort_recursion<T>(mut array_to_sort, compare) }
  }
}

fn selection_sort_clone<T>(array_to_sort []T, compare fn (a T, b T) bool, loop_rec LoopRec) []T {
  return match loop_rec {
    .loop { selection_sort_loop_clone<T>(array_to_sort, compare) }
    .recursion { selection_sort_recursion_clone<T>(array_to_sort, compare) }
  }
}

Ver também

• Algoritmo de ordenação
• Quick sort
• Merge sort
• Bubble sort
• Heapsort
• Pesquisa binária

Ligações externas

• Sorting algorithms/Selection sort - Implementação do algoritmo em várias linguagens de programação