Может кто-нибудь объяснить мне эту реализацию 3-way-quicksort

Question

Я немного растерялся, пытаясь понять этот код, после первой итерации время функция сортировки вызывается снова, несколько раз, и значения, передаваемые в «сортировку», меняются:

sort(a, lo, lt - 1, c);
sort(a, gt + 1, hi, c);

IНе понимаю почему, что означает изменение этих индексов и как это влияет на сортировку.Я попытался отладить этот кусок кода, и мне кажется, что эти изменения индекса ограничивают область сортировки либо правой стороной массива, либо левой, где после первой итерации большинство больших и меньших значений должно быть,Кто-нибудь может пролить свет на это и уточнить назначение этих двух строк кода?

public class Quick3Way{

    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);
        System.out.println(Arrays.toString(a));
        sort(a, 0, a.length - 1);
    }

    public static void sort(Object[] a, Comparator c)
    {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1, c);
    }


    public static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;

        // partition
        int i = lo;
        int lt = lo;
        int gt = hi;

        while (i <= gt){
            if      (less(a[i], a[lt]))     exch(a, i++, lt++);

            else if (less(a[lt], a[i]))     exch(a, i, gt--);
            else                            i++;
        }

        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    public static void sort(Object[] a, int lo, int hi, Comparator c)
    {
        if (hi <= lo) return;

        // partition
        int i = lo;
        int lt = lo;
        int gt = hi;

        while (i <= gt){
            if (less(a[i], a[lt], c))       exch(a, i++, lt++);
            else if (less(a[lt], a[i], c))  exch(a, i, gt--);
            else                            i++;
        }

        sort(a, lo, lt - 1, c);
        sort(a, gt + 1, hi, c);
    }


    // test client
    public static void main(String[] args)
    {
        Integer[] arraypart = { 1,1,2,2,3,4,5,6,710,30,0,50};
        Integer[] arraysort = new Integer[arraypart.length];
        System.arraycopy(arraypart, 0, arraysort, 0, arraypart.length);

        System.out.print("Original:\t");
        for (int str : arraypart)
            System.out.print(str);
        System.out.println();

        System.out.print("Full sort:\t");
        Quick3Way.sort(arraysort);
        for (int str : arraysort)
            System.out.print(str);
        System.out.println();
    }

    // private
    private static void exch(Comparable[] a, int i, int j)
    {
        System.out.println(Arrays.toString(a));
        Comparable tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        System.out.println(Arrays.toString(a));
    }

    private static void exch(Object[] a, int i, int j)
    {
        Object tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    private static boolean less(Comparable a, Comparable b)
    { return a.compareTo(b) < 0; }

    private static boolean less(Object a, Object b, Comparator c)
    { return c.compare(a, b) < 0; }
}

Answer 1

Прежде всего, я не уверен, что этот код является трехсторонней быстрой сортировкой, я думаю, что это просто обычная быстрая сортировка, хотя было бы неплохо, если бы кто-то еще мог проверить код и убедиться в этом.Но что касается этих двух строк, надеюсь, поможет следующее:

, поэтому вы выбрали элемент разворота.Давайте назовем это x

, тогда вы сделаете два раздела.Таким образом, теперь список содержит все, что меньше x (необязательно отсортировано), СЛЕДУЕТ ПО Х, СЛЕДУЕТ ПО всему, что больше x (необязательно отсортировано).

Так что вы точно знаете, что x находится в нужном месте.Теперь вам нужно отсортировать части по обе стороны от х.Вот где появляется этот код:

sort(a, lo, lt - 1, c);
sort(a, gt + 1, hi, c);

примерно переведено на:

sort (the_list, from_start, to_one_before_x, with_this_comparitor);

sort (the_list, from_one_after_x,to_end, with_this_comparitor);

Очевидно, что когда алгоритм повторяется, вы можете заменить from_start на from_start_of_partition и from_end на from_end_of_parition и т. д.