Saltar para o conteúdo

Selection sort

Origem: Wikipédia, a enciclopédia livre.
Selection sort

algoritmo selection sort
algoritmo selection sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso total, 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 elementos restantes, até os últimos dois elementos.

Descrição do algoritmo

[editar | editar código-fonte]

É 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

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 enquanto que, por exemplo, os algoritmos heapsort e mergesort possuem complexidades

  • 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.
  • Ele é um dos mais lentos para vetores de tamanhos grandes.
  • Ele não é estável.
  • Ele faz sempre comparações, independentemente do vetor estar ordenado ou não.

Implementações

[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;
     }
  }
}

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;
    }
}
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;
        }
    }
}
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]
// 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) }
  }
}

Ligações externas

[editar | editar código-fonte]