interpretation of quicksort

Question

I learned Haskell, and now I’m starting to learn C. I’ve been trying to pass my quicksort code in Haskell to C but I haven’t succeeded. So I decided to look at some books and found the following code:

/* 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);
}

Doubt 1) I did some desktop tests, compiled and ran with some entries and could not figure out why to put && i<right and && j>left while being that own item[i]<x and x<item[j] already makes the appropriate checks.

Doubt 2) For this code it would no longer be correct to put only while(i<=j) instead of do while(i<=j).

Answer 1

Quicksort works, in pseudo code, as follows:

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.

Function quicksort of your example and only a wrapper for the function qs.

Function qs and the one that makes the steps I described above:

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

x and our pivot, in this case always the element that is in the middle of the vector (I won’t get into the merits of the discussion if this is a good pivot or not).

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

Now, what it does is, from the beginning of the vector, but without going beyond j, which marks the end of the vector, increment i as an element that is in position i is less than the pivot, and the same for j. Hence, to the end of these two whiles above, all elements with smaller Dice that i are smaller than the pivot and all elements larger than j are larger than the pivot. It does this because we do not need to move in these elements, since they respect the fact that those of the left pivot are smaller than he and the right bigger.

After those two whiles we also know that the item[i] > x and item[j] < j, or i >= j.

If i < j, we know, then, that item[i] > x and item[j] < x. Soon, we both changed places and 'arranged' the vector until this point. Then we increase i and decrease j to analyze the next elements.

As for your doubt 2, the do...while(i <= j) and the while(i <= j) sao identicos, since inside the while it makes the check. Then went to like the fregues :P

Note: This code must be from an old reference, since it uses the word register, that "does nothing".

Another thing is that the quicksort in Haskell is much simpler, but this doing exactly the same thing:

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

The p and the pivot, lesser are all elements of the list smaller than p and greater the largest. Calls to the function filter that let the quicksort somewhat better.