Mostrando postagens com marcador Algoritmos de Ordenação. Mostrar todas as postagens
Mostrando postagens com marcador Algoritmos de Ordenação. Mostrar todas as postagens

terça-feira, 17 de julho de 2012

Quick-Sort: Uma abordagem indutiva.

Neste post, vamos fazer uma análise indutiva do método de ordenação que na prática é o mais rápido. O quick-sort demostra a eficiência do paradigma "dividir e conquistar".
O primeiro passo do quick-sort é escolher aleatoriamente um elemento x que será chamado de pivô. Em seguida, o vetor será particionado de forma que os elementos a esquerda do pivô sejam menores que ele, e os elementos a direita sejam maiores ou iguais a ele. A Figura 1 apresenta uma partição cujo pivô é 4.

Figura 1. Vetor particionado

Descrição indutiva da "partição": Para construir o nosso algoritmo vamos utilizar a abordagem indutiva, detalhando o caso base, a hipótese de indução e o caso geral..

Idéia indutiva:
  • Caso Base: o vetor possui apenas 1 elemento, então ele já está particionado!
  • Hipótese de Indução: vamos supor que o problema da partição já está resolvido para n - 1 elementos e que sabemos onde termina a lista de elementos menores que o pivô.
  • Caso Geral: é quase trivial, pois basta verificar se o último elemento do vetor é menor ou maior que o pivô. Caso o último elemento seja menor que o pivô, então basta colocá-lo no final da lista de elementos menores que o pivô.
Implementação da partição: Seguindo o esquema indutivo apresentado, podemos implementar um método de forma simples. Nessa implementação, o pivô escolhido é o primeiro elemento do vetor.
  • Implementação em C++:
int partition(int X[], int left, int right) {
    int pivot = X[left];
    int i = left;

    for (int j = left; j <= right; j++)
        if (X[j] < pivot)
            swap(X, j, ++i);
    swap(X, left, i);
    return i;
}
Após a execução do método "partition", apenas o pivô estará na posição correta. Precisamos ordenar os elementos que estão à esquerda e à direita do pivô. No entanto, podemos assumir que a hipótese de indução fará esse trabalho, como podemos ver na Figura 2.
Figura 2.
Idéia indutiva:
  • Caso Base: um vetor com 1 elemento já está ordenado.
  • Hipótese de Indução: após a execução do método "partition", vamos assumir que a hipótese de indução sabe como ordenar todos os elemento que estão à esquerda e à direita do pivô.
  • Caso Geral: simplesmente já temos o vetor ordenado!

Na Figura 3, apresentamos o resultado final, um vetor ordenado!
Figura 3. Vetor ordenado.
A seguir, apresentamos a implementação completa do Quick-Sort.
  • Implementação em Haskell: por se tratar de uma linguagem funcional, Haskell permite que o programador implemente uma solução enxuta, sem se preocupar com detalhes.
quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort [x] = [x]
quickSort (x:xs) = quickSort menores ++ [x] ++ quickSort maiores
  where
    menores = [p | p <- xs, p <= x]
    maiores = [p | p <- xs, p > x]
  • Implementação em C++
void quickSort(int A[], int left, int right){
    if(left < right){
        int middle = partition(A, left, right);
        quickSort(A, left, middle - 1);
        quickSort(A, middle + 1, right);
    }
}
  • Implementação em Python
def quickSort(lista):
  if lista == []:
    return []
  else:
    pivot = lista[0]
    menores = [x for x in lista[1::] if x < pivot]
    maiores = [x for x in lista[1::] if x >= pivot]
    return quickSort(menores) + [pivot] + quickSort(maiores)

Complexidade do Quick-Sort: A complexidade do algoritmo depende da escolha do pivô, caso o pivô escolhido divida o vetor em duas partes com tamanhos iguais ou similares, a sua complexidade será O(n log n).
Caso os elementos do vetor já estejam ordenados, a complexidade do Quick-Sort no pior caso será descrita pela recorrência $T(n) = T(n - 1) + O(n) = O(n^2)$. Na prática, como o pior caso raramente acontece, a literatura reconhece que o Quick-Sort é o melhor algoritmo de ordenação, e por isso ele é utilizado em uma grande variedade de aplicações.

quarta-feira, 20 de junho de 2012

Insertion-Sort: Uma descrição Indutiva

Agora vamos fazer uma descrição indutiva do algoritmo Insertion-Sort. É importante lembrar que este tipo de abordagem é um pouco diferente dos métodos convencionais que muitos livros utilizam. No entanto, de forma simples e clara resolveremos o problema de ordenação.

Idéia indutiva:
  • Caso Base: é trivial, pois uma lista com apenas um elemento já está ordenada.
  • Hipótese de Indução: vamos assumir que a lista com n- 1 elementos já está ordenada.
  • Caso Geral: agora, basta inserir o último elemento na sequência que, por hipótese de indução, já está ordenada.
Antes de derivar o algoritmo vamos visualizar um exemplo.

Situação inicial: Vetor desordenado


Agora vamos trabalhar com os primeiros n - 1 elementos


Vamos assumir que os n - 1 elementos já estão ordenados


Agora, só precisamos inserir o último elemento na sequência ordenada


E vamos mais uma vez, construir o nosso algoritmo seguindo a idéia indutiva apresentada acima.

  • Implementação em Python (versão recursiva)
def ins_sort_rec(seq, i):
 if i==0: return
 ins_sort_rec(seq, i-1)
 j = i
 while j > 0 and seq[j-1] > seq[j]:
  seq[j-1], seq[j] = seq[j], seq[j-1]
  j -= 1
  • Implementação em Java (versão interativa)
static void insertionSort(int vet[]){
  int i, aux;
  for(int j = 1; j < vet.length; j++){
    i = j - 1;
    aux = vet[j];
    while(i > -1 && vet[i] > aux){
      vet[i+1] = vet[i];
      i--;
    }
    vet[i + 1] = aux;
  }
}

Complexidade do algoritmo
A relação de recorrência que expressa a complexidade de tempo do insertion-sort é: T(n) = T(n - 1) + n.
Essa relação nos diz que o tempo do insertion-sort é igual ao tempo que a hipótese de indução gasta para ordenar os n - 1 elementos, mais o tempo gasto para inserir um elemento na sequência ordenada.
Resolvendo a recorrência temos:

T(n) = T(n - 1) + n
T(n) = T(n - 2) + (n -1) + n
T(n) = T(n - 3) + (n - 2) + (n - 1) + n
...
T(n) = T(1) + 2 + 3 + 4 + 5 + ... + (n - 1) + n
T(n) = n(n + 1)/2
T(n) = O($n^2$)

Ou seja, a complexidade de tempo do insertion-sort é limitada pela função quadrática.