Algoritmos de Ordenação

InsertionSort

Introdução

• inspirado na forma como cartas são organizadas na mão = pegar uma carta de cada vez e inserir na posição correta
• analisa cada elemento comparando com os demais à esquerda
• início = segundo elemento do vetor
  • esse tem que ser o ponto de partida porque primeiro elemento não tem nenhum outro à esquerda
• elementos à esquerda do selecionado ficam sempre em ordem crescente/decrescente
• comparação em pares
• ordenação in-place = feita rearranjando os elementos no próprio vetor
• algoritmo
  • 2 estruturas de repetição
  • n-1 execuções
• vídeo de exemplo - AlgoRythmics InsertionSort

Funcionamento

1. A lista é dividida em duas partes: uma ordenada (inicialmente contendo apenas o primeiro elemento) e uma não ordenada
2. Itera-se sobre os elementos da lista não ordenada, um a um
3. Para cada elemento, ele é comparado com os elementos da parte ordenada
4. O elemento é então inserido na posição correta dentro da parte ordenada, deslocando os elementos, se necessário
5. Repete-se o processo até que todos os elementos estejam ordenados

Algoritmo

insertionSort(V[0...n], n)
  para i 1 até n faça
    j i
    enquanto (V[j] < V[j-1]) e j > 0 faça
      aux V[j-1];
      V[j-1] V[j];
      V[j] aux;
      j j - 1
    fim_enquanto
  fim_para
fim_insertionsort

#include <stdio.h>
#define LEN 6
int main(){
  int vetor [LEN] = {4,6,9,2,4,3};
  for(int i =1; i <LEN; i++){
    int j = i;
    while((vetor[j] < vetor[j-1]) && j > 0){
      int aux = vetor[j-1];
      vetor[j-1] = vetor[j];
      vetor[j] = aux;
      --j;
    }
  }
  for(int i = 0; i < LEN; i++){
    printf("%d", vetor[i]);
  }
}

Complexidade

• melhor caso
  • vetor já ordenado
  • O(n)
  • apenas uma comparação por elemento
  • segunda estrutura de repetição não é executada
• pior caso
  • vetor na ordem inversa à desejada
  • O(n^2)
  • todas as execuções necessárias
  • cada elemento precisa ser comparado e deslocado até o início da lista

BubbleSort

Introdução

• algoritmo baseado em trocas
• simples compreensão e implementação
• inspirado na dinâmica das bolhas formadas em um copo de refrigerante
  • elementos menores ("mais leves") movem-se na direção de suas posições finais na sequência ordenada
  • movem-se na direção do início da sequência

Funcionamento

• cada elemento da posição i será comparado com o elemento da posição i+1
  • 1º elemento comparado com 2º
  • 2º com 3º
  • 3º com 4º, assim por diante
• quando os elementos estão fora de ordem, é feita a inversão e esses dois elementos são trocados de posição
• fim da comparação = penúltimo elemento é comparado com o último
• resultado = maior elemento na última posição processo continua até que todo o vetor esteja ordenado
• demonstração - AlgoRythmics

Algoritmo e Implementação

#include <stdio.h>
#define LEN 6

int main(){
  int v [LEN] = {4,6,9,2,4,3};
  for(int n= 1; n<=LEN ; n++) {
    for(int j=0; j<LEN-1; j++) {
      if (v[j] > v[j+1] ) {
        int aux = v[j];
        v[j] = v[j+1];
        v[j+1] = aux;
      }
    }
  }
  for(int i = 0; i < LEN; i++){
    printf(" %d ", v[i]);
  }
}

// versão melhorada
// realiza comparações após o elemento que iniciou a iteração anterior
// isso diminui a quantidade de comparações
#include <stdio.h>
#define LEN 6
int main(){
  int v [LEN] = {4,6,9,2,4,3};
  for(int i= 1; i<=LEN-1 ; i++) {
    for(int j = LEN-1; j>=i; j--) {
      if (v[j] < v[j-1] ) {
        int aux = v[j];
        v[j] = v[j-1];
        v[j-1] = aux;
      }
    }
  }
  for(int i = 0; i < LEN; i++){
    printf(" %d ", v[i]);
  }
}

• para evitar que o processo continue mesmo depois que o vetor estiver ordenado, basta declarar uma variável que sinaliza quando houve troca
  • vantagem = simplicidade do algoritmo
  • desvantagem = lentidão
  • uso indicado = pequena coleção, "quase ordenada" e para demonstração didática

/*
- versão melhorada
- finaliza quando não houverem mais trocas a serem realizadas
- não precisa percorrer o vetor inteiro
*/

#include <stdio.h>
#define LEN 6

int main(){
  int v [LEN] = {4,6,9,2,4,3};
  int n = 1, troca = 1;
  while(n <= LEN && troca == 1){
    troca = 0;
    for(int i=0; i<LEN-1; i++) {
      if (v[i] > v[i+1] ) {
        int aux = v[i];
        v[i] = v[i+1];
        v[i+1] = aux;
        troca = 1;
    }
  }
  ++n;
  }
  for(int i = 0; i < LEN; i++){
    printf(" %d ", v[i]);
  }
}

Resumo

• Simples compreensão e implementação
• Torna-se cada vez menos eficiente à medida que o número de elementos aumenta
• V2 = versão mais usada
  • melhor caso = vetor ordenado - O(n)
  • maior caso = vetor ordenado em ordem decrescente - O(n²)
• Há outros algoritmos/métodos de ordenação mais eficientes
  • exemplo = MergeSort, com complexidade O(n log n)

QuickSort

Introdução

• QuickSort = um dos algoritmos de ordenação mais eficientes e amplamente utilizados
• assim como o MergeSort, utiliza a estratégia Dividir para Conquistar (Divide and Conquer) para ordenar os elementos de uma lista
  • o QuickSort divide-a repetidamente em sublistas menores e ordena cada uma delas
• particularmente eficaz para grandes conjuntos de dados
• em média, é mais rápido que outros algoritmos de ordenação baseados em comparação.
• no QuickSort, o vetor é particionado em duas partes a partir da escolha de um pivot
  • particionamento = realizado de forma recursiva até chegar em apenas um único elemento
  • os elementos menores que o pivot devem ser alocados à sua esquerda e os maiores à sua direita

Funcionamento

• O algoritmo QuickSort funciona escolhendo um elemento chamado pivô e, em seguida, reorganizando a lista de tal forma que todos os elementos menores que o pivô fiquem à sua esquerda e todos os elementos maiores fiquem à sua direita. Após essa divisão, o pivô está na posição correta. Esse processo é recursivamente repetido para as sublistas à esquerda e à direita do pivô até que a lista inteira esteja ordenada.
• demonstração - AlgoRhytmics
• passo a passo
  1. Escolha do pivô = Selecionar um elemento da lista como pivô. Pode ser o primeiro, último, um elemento aleatório ou a mediana
  2. Particionamento = Reorganizar a lista de modo que todos os elementos menores que o pivô estejam antes dele e todos os elementos maiores estejam depois.
  3. Recursão = Aplicar o QuickSort recursivamente às sublistas à esquerda e à direita do pivô
  4. Condição de parada = quando a sublista tiver 0 ou 1 elemento, ela está automaticamente ordenada

Algoritmo e Implementação

QuickSort - Pseudocódigo

quicksort(X, inicio, fim)
  declare indice numérico
  se (inicio < fim) então
    indice <- particao(x, inicio, fim)
    quicksort(X, inicio, indice-1)
    quicksort(X, indice+1, fim)
  fim_se
fim_quicksort

QuickSort - Pseudocódigo

void quicksort(int v[], int inicio, int fim){
  if (inicio < fim){
    int indice = particao(v, inicio, fim);

    quicksort(v, inicio, indice-1);
    quicksort(v, indice+1, fim);
  }
}

Complexidade

MergeSort

---