Bug in quicksort implementation

Question

I have to implement quicksort. From Programming Pearls here is the code:

public class Quick{
    public static void quicksort(int x[], int l, int u)
    {
        if (l>=u)
            return;
        int t = x[l];
        int i = l;
        int j = u;

        do
        {
            i++;
        } while (i<=u && x[i]<t);

        do
        {
            j--;
            if (i>=j) break;
        } while (x[j]>t);

        swap(x, i, j);
        swap(x, l, j);

        quicksort(x, l  , j-1);
        quicksort(x, j+1, u  );
    }

    public static void main(String[]args)
    {
        int x[] = new int[]{55,41,59,26,53,58,97,93};
        quicksort(x, 0, x.length-1);
        for (int i=0; i<x.length; i++)
        {
            System.out.println(x[i]);
        }
    }

    public static void swap(int x[], int i, int j)
    {
        int s = x[i];
        x[i] = x[j];
        x[j] = s;
    }
}

It does not work. Here is output:

59
41
55
26
53
97
58
93

Why doesn't it work?

Answer 1

Should be:

int t=x[l]; 
int  i=l; 
->    int  j=u + 1; 

In addition, you have translated the psuedo-code incorrectly: Here it is in C# (Very similiar to C, just change the array declarations):

public static class Sort
{
    public static void quicksort(int[] x, int l, int u)
    {
        if (l >= u)
            return;

        int t = x[l];
        int i = l;
        int j = u + 1;

        while (true)  // In C, make this while(1)
        {
            do
            {
                i++;
            } while (i <= u && x[i] < t);

            do
            {
                j--;
            } while (x[j] > t);

            if (i >= j)
                break;

            swap(x, i, j);
        }

        swap(x, l, j);

        quicksort(x, l, j - 1);
        quicksort(x, j + 1, u);
    }


    public static void swap(int[] x, int i, int j)
    {
        int s = x[i];
        x[i] = x[j];
        x[j] = s;
    }

Calling with this:

    static void Main(string[] args)
    {
        int[] x = new int[] { 55, 41, 59, 26, 53, 58, 97, 93 };

        Sort.quicksort(x, 0, x.Length - 1);
        for (int i = 0; i < x.Length; i++)
        {
            Console.WriteLine(x[i]);
        }
    }

Produces:

26
41
53
55
58
59
93
97

Answer 2

It seems like this has been answered.

Since it is in the algorithms tag I want to say - I came across this neat website which shows the sorting in progress.

Check it out, I am sure you will enjoy it :)