6

Aprendi Haskell, e agora estou começando a aprender C. Estive tentando passar o meu código do quicksort em Haskell para C mas não obtive sucesso. Então decidi olhar alguns livros e encontrei o seguinte código:

/* Função de inicialização da Quicksort. */
void quicksort(char *item, int count)
{
    qs(item, 0, count-1);
}

/* A Quicksort. */
void qs(char *item, int left, int right)
{
    register int i, j;
    char x, y;

    i = left; j = right;
    x = item[(left + right)/2];

do
{
    while(item[i]<x && i<right) i++; // DUVIDA 1
    while(x<item[j] && j>left) j--;  // DUVIDA 1

    if(i<=j)
    {
        y = item[i];
        item[i] = item[j];
        item[j] = y;
        i++; j--;
    }
 }
 while(i<=j); // DUVIDA 2

 if(left<j) qs(item, left, j);
 if(i<right) qs(item,  i, right);
}

Duvida 1) Fiz alguns testes de mesa, compilei e executei com algumas entradas e não descobri o porque de colocar && i<right e && j>left dentro do while sendo que o próprio item[i]<x e x<item[j] já faz as devidas verificações.

Duvida 2) Para este código não seria mais correto colocar apenas while(i<=j) ao invés do do while(i<=j).

1
  • Veja o tour. Você pode aceitar a resposta que melhor lhe atendeu em cada uma das suas perguntas se achar que resolveu o problema.
    – Maniero
    Commented 31/08/2014 às 16:30

1 Resposta 1

4

O quicksort funciona, em pseudo codigo, da seguinte maneira:

1) Escolha um elemento do vetor, chamado de pivo.
2) Ordene o vetor de forma que todo elemento menor que o pivo
esteja a esquerda dele e todo elemento maior esteja a direita.
3) Aplique os passos 1 e 2 para os dois "vetores" resultantes, o
de elementos maiores e o de elementos menores.

A funcao quicksort do seu exemplo e so um wrapper para a funcao qs.

A funcao qs e a que faz os passos que eu descrevi acima:

i = left; j = right;
x = item[(left + right)/2];

x e o nosso pivo, nesse caso sempre o elemento que esta na metade do vetor (nao vou entrar no merito da discussao se esse e um bom pivo ou nao).

    while(item[i]<x && i<right) i++;
    while(x<item[j] && j>left) j--;

Agora, o que ele faz e, a partir do inicio do vetor, mas sem passar de j, que marca o fim do vetor, incrementar i enquanto elemento que esta na posicao i for menor que o pivo, e o mesmo para j. Logo, ao final desses dois whiles acima, todos os elementos com indice menor que i sao menores que o pivo e todos os elementos maiores que j sao maiores que o pivo. Ele faz isso porque nao precisamos mexer nesses elementos, ja que eles respeitam o fato que que os da esquerda do pivo sao menores que ele e os da direita maiores.

Depois desses dois whiles nos tambem sabemos que o item[i] > x e item[j] < j, ou i >= j.

Se i < j, nos sabemos, entao, que item[i] > x e item[j] < x. Logo, nos trocamos ambos de lugar e 'arrumamos' o vetor ate esse ponto. Em seguida incrementamos i e decrementamos j para analisar os proximos elementos.

Quanto a sua duvida 2, o do...while(i <= j) e o while(i <= j) sao identicos, ja que dentro do while ele faz a verificacao. Entao foi a gosto do fregues :P

Nota: Esse codigo deve ser de alguma referencia antiga, ja que ele usa a palavra register, que "nao faz nada".

Outra coisa e que o quicksort em Haskell e bem mais simples, mas esta fazendo exatamente a mesma coisa:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
          where
                  lesser  = filter (< p) xs
                  greater = filter (>= p) xs

O p e o pivo, lesser sao todos os elementos da lista menores que p e greater os maiores. As chamadas para a funcao filter que deixam o quicksort um tanto melhores.

4
  • Então se eu omitir && i<right e && j>left do while vai dar problema ? O que eu estava com mais dúvida era isso, pois executei sem && i<right e && j>left e funcionou perfeitamente. Commented 30/08/2014 às 4:00
  • Sim, vai dar problema. Tente rodar com um vetor ordenado ao contrario, como 5 4 3 2 1. Commented 30/08/2014 às 5:31
  • Testei sem && i<right e && j>left utilizando 5 4 3 2 1 como meu vetor e funcionou do mesmo jeito. Eu já fiz o "teste de mesa" com alguns vetores e ainda não vi a utilidade de && i<right e && j>left. Muito provável que eu não esteja enxergando isso, pois em vários lugares encontrei o quicksort implementado desta maneira com && i<right e && j>left. Se possível, me mostre em que momento neste seu exemplo de 5 4 3 2 1 que é necessário esta implementação. Commented 4/09/2014 às 0:38
  • Pensando agora, quando o pivo e sempre o elemento do meio acho que nao e relevante mesmo. Mas, se o seu pivo fosse o ultimo elemento do vetor poderia dar problema. Na maioria das implementacoes decentes do quicksort o pivo e escolhido de forma mais ou menos aleatoria, entao e importante por. Nessa que voce colocou, contudo, acho que da na mesma ter ou nao. Commented 4/09/2014 às 16:20

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .