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.

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.

Descrição do algoritmoEditar

É 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

ComplexidadeEditar

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  

VantagensEditar

  • 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.

DesvantagensEditar

  • 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çõesEditar

CEditar

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

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

VEditar

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

Ligações externasEditar