Métodos de Ordenação

Estruturas de Dados Avançadas

Selection Sort

Selection sort demo

Seleciona a primeira posição do vetor e compara o elemento com os demais, partindo da esquerda para a direita, trocando-os quando necessário. Ao término das comparações, seleciona a proxima posição e compara o elemento com os posteriores. Essa lógica é repetida até que a ultima posição esteja ordenada.

Categoria Complexidade Performance
Seleção Simples Baixa 

int* selection_sort(int vetor[], int tamanho) {
  int i, j, min, aux;
  for (i = 0; i < (tamanho-1); i++) {
    min = i;
    for (j = (i+1); j < tamanho; j++) {
      if(vetor[j] < vetor[min])
        min = j;
    }
    if (i != min) {
      aux = vetor[i];
      vetor[i] = vetor[min];
      vetor[min] = aux;
    }
  }
  return vetor;
}

Bubble Sort

Bubble sort demo

Compara o elemento da primeira posição do vetor com o elemento da posição seguinte, trocando-os se necessário, e avançando uma posição, até o fim. Essa lógica é repetida até que não haja troca de posições.

Categoria Complexidade Performance
Troca Simples Relativamente Baixa 

int* bubble_sort(int vetor[], int tamanho) {
  int i, j, aux = 0;
  for(i = tamanho-1; i > 0; i--) {
    for(j = 0; j < i; j++) {
      if(vetor[j] > vetor[j+1]) {
        int temp;
        temp = vetor[j];
        vetor[j] = vetor[j+1];
        vetor[j+1] = temp;
      }
    }
  }
  return vetor;
}

Quicksort

Quicksort demo

Utilizando um elemento como guia (denominado pivô), separamos os elementos em dois vetores, os menores e os maiores que o mesmo. Desses dois vetores criados, a lógica é aplicada repetidamente, até que os itens estejam ordenados.

Categoria Complexidade Performance
Troca Relativamente Complexo Alta 

int* quick_sort(int vetor[], int esq, int dir) {
  int i, j, pivo, aux;
  i = esq;
  j = dir;
  pivo = vetor[(i+j)/2];
  do {
    while(vetor[i] < pivo && i < dir)
      i++;
    while(vetor[j] > pivo && j > esq)
      j--;
    if(i <= j) {
      aux = vetor[i];
      vetor[i] = vetor[j];
      vetor[j] = aux;
      i++;
      j--;
    }
  } while (i <= j);
  if(esq < j)
    quick_sort(vetor, esq, j);
  if(dir > i)
    quick_sort(vetor, i, dir);
  return vetor;
}

Relembrando

Gnome Sort

Gnome sort demo

Baseado no Bubble Sort, também compara os elementos vizinhos da esquerda para a direita. Quando houver troca, o algoritmo compara o elemento com os anteriores, da direita para a esquerda, até encontrar sua posição correta.

Esse método evita que o algoritmo percorra elementos já ordenados.

Categoria Complexidade Performance
Troca Relativamente Simples Relativamente Baixa 

int* gnome_sort(int vetor[], int tamanho) {
  int next = 0, previous = 0;
  int i = 0;
  for(i = 0; i < tamanho; i++) {
    if(vetor[i] > vetor[i+1]) {
      previous = i;
      next = i+1;
      while(vetor[previous] > vetor[next]) {
        swap(&vetor[previous], &vetor[next]);
        if(previous > 0)
          previous--;
        if(next > 0)
          next--;
      }
    }
  }
  return vetor;
}

void swap(int *A, int *B) {
  int C = *A;
  *A = *B;
  *B = C;
}

Cocktail Sort

Cocktail sort demo

Também baseado no Bubble Sort, a ideia desse algoritmo (também conhecido como Bubble Sort Bidirecional) é eliminar os elementos tartaruga mais rapidamente. O Cocktail Sort compara os elementos em pares, da esquerda para a direita, e, ao chegar no final do vetor, volta comparando os elementos da direita para a esquerda.

Categoria Complexidade Performance
Troca Relativamente Complexo Relativamente Baixa 

int* cocktail_sort(int vetor[], int tamanho) {
  int length, bottom, top, swapped, i, aux;
  length = tamanho;
  bottom = 0;
  top = length-1;
  swapped = 0;
  while(swapped == 0 && bottom < top) {
    swapped = 1;
    for(i = bottom; i < top; i = i+1) {
      if(vetor[i] > vetor[i+1]) {
        aux = vetor[i];
        vetor[i] = vetor[i+1];
        vetor[i+1] = aux;
        swapped = 0;
      }
    }
    top = top-1;
    for(i = top; i > bottom; i = i-1) {
      if(vetor[i] < vetor[i-1]) {
        aux = vetor[i];
        vetor[i] = vetor[i-1];
        vetor[i-1] = aux;
        swapped = 0;
      }
    }
    bottom = bottom+1;
  }
  return vetor;
}

Comb Sort

Comb sort demo

Também visando diminuir os problemas dos elementos tartaruga no Bubble Sort, o Comb Sort utiliza um gap maior para cada iteração, consequentemente melhorando a performance.

Categoria Complexidade Performance
Troca Relativamente Simples Alta 

int* comb_sort(int vetor[], int tamanho) {
    float shrink_factor = 1.247330950103979;
    int gap = tamanho, swapped = 1, swap, i;
    while ((gap > 1) || swapped) {
        if (gap > 1)
           gap = gap/shrink_factor;
        swapped = 0;
        i = 0;
        while ((gap+i) < tamanho) {
            if (vetor[i]-vetor[i+gap] > 0) {
                swap = vetor[i];
                vetor[i] = vetor[i+gap];
                vetor[i+gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
    return vetor;
}

Comparação

Benchmark
Benchmark