Ошибка в реализации быстрой сортировки

Question

Я должен реализовать быструю сортировку. Из Programming Pearls вот код:

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;
    }
}

Не работает. Вот вывод:

59
41
55
26
53
97
58
93

Почему это не работает?

Answer 1

Должно быть:

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

Кроме того, вы неправильно перевели псевдо-код: здесь он находится на C # (очень похоже на C, просто измените объявления массива):

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;
    }

Вызов с этим:

    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]);
        }
    }

Производит:

26
41
53
55
58
59
93
97

Answer 2

Кажется, что на это уже ответили.

Так как это находится в теге алгоритмов, я хочу сказать - я наткнулся на этот аккуратный веб-сайт , который показывает процесс сортировки.

Проверьте это, я уверен, вам понравится:)