quicksort interpretation

Question

quicksort interpretation

Navigation

#1 by (4 votes)

6

I've learned Haskell, and now I'm beginning to learn C. I've been trying to get my quicksort code in Haskell to C but I did not succeed. 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 table tests, I compiled and executed with some entries and I did not find out why to put && i<right and && j>left within the while whereas item[i]<x and x<item[j] already do the due checks.

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

c quicksort

asked by anonymous 30.08.2014 / 03:16

1 answer

The type of an operating system can be microkernel + monolithic? Copy everything before the first blank line

score 4 · Accepted Answer

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.

The quicksort function of your example is just a wrapper for the function qs .

The function qs and the one that does the steps that I described above:

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

x and our pivo, in this case always the element that is in the middle of the vector (I will not get into the merit of the discussion if this is a good pivo or no).

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

Now, what does it do, and from the beginning of the vector, but without j , which marks the end of the vector, increment i as an element that is in i position is less than the pivo, and the same as j . Therefore, end of these two whiles above, all elements with lower index which i are smaller than pivo and all elements greater than j are larger than the pivo. He does it because we do not have to move these elements, since they respect the fact that those of the left of the pivot are smaller than it and the right ones are larger.

After these two whiles we also know that item[i] > x e item[j] < j , or i >= j .

If i < j , we then know that item[i] > x and item[j] < x . So we change places and we 'tidy up' the vector until this Score. Then we increment i and decrement j to analyze the next elements.

As for your doubts 2, do...while(i <= j) and while(i <= j) are identical, since within the while it does the verification. So was the I like the fregues: P

Note: This code must be of some old reference, since it uses the word register , which "does nothing".

Another thing is that 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 pivo, lesser are all list elements that are less than p and greater the largest. Calls to filter function make quicksort a bit better.