Quicksort в Java с Lomuto раздела или Хоара раздел


Я разработал быстрая сортировка на Java, которые могут работать с обеими стратегии раздел Lomuto, или стратегии раздел Хоара.

Как их правильно отсортировать массив.

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

Есть ли причина, чтобы использовать один против другого?

Вот это:

public class QuickSort {

    public static void main(String... args) {
        int array[] = {2, 3, 4, 1, 11, 5, 7, 0, 10, -1, 99, 23};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }


    public static void quickSort(int array[]) {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int array[], int l, int r) {
        if (l >= r) {
            return;
        }
        int p = lomutoPartition(array, l, r);//hoarePartition(array, l, r);//lomutoPartition(array, l, r);
        quickSort(array, l, p - 1);
        quickSort(array, p + 1, r);
    }

    private static int lomutoPartition(int array[], int l, int r) {
        //pivot chosen
        int pivot = array[r];
        int i = l - 1;
        for (int j = l; j < r; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, r);
        return i + 1;
    }


    private static int hoarePartition(int array[], int l, int r) {
        int pivot = array[r];
        int left = l;
        int right = r;
        while (true) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left >= right) {
                return left;
            }
            swap(array, left, right);
        }
    }

    private static void swap(int array[], int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

}


392
4
задан 19 марта 2018 в 09:03 Источник Поделиться
Комментарии
1 ответ


public static void main(String... args) {
int array[] = {2, 3, 4, 1, 11, 5, 7, 0, 10, -1, 99, 23};
quickSort(array);
System.out.println(Arrays.toString(array));
}

Мне нравится, что вы тестируете ваш код, но вы должны визуально проверить правильность вашей программы. Лучше было бы использовать систему тестирования и автоматизировать эту задачу.


private static void quickSort(int array[], int l, int r) {

Одной буквы имена переменных, трудно читать.
Было бы лучше использовать left и rightздесь.
Кроме того, lhs и rhs общие сокращения для "левой" и "правой стороны".
Мне плевать на них, но они достаточно распространены, что я позволяю им скользить через анализ кода на работе.


   int p = lomutoPartition(array, l, r);//hoarePartition(array, l, r);//lomutoPartition(array, l, r);

Здесь мертвый код...
Произошло это потому, что вы физически изменить код для того, чтобы переключаться между двумя различными стратегиями.
Лучше бы на деле реализовать стратегию шаблон.

Вы можете создать PartitioningStrategy как это.

interface PartitioningStrategy {
int partition(int numbers[], int left, int right);
}

И тогда есть две реализации.

public class HoarePartitioningStrategy implements PartitioningStrategy {
public int partition(int numbers[], int left, int right) {
//...
}
}

public class LomutoPartitioningStrategy implements PartitioningStrategy {
public int partition(int numbers[], int left, int right) {
//...
}
}

Затем вы можете решить, какую стратегию использовать в main.

public static void main(String... args) {
int array[] = {2, 3, 4, 1, 11, 5, 7, 0, 10, -1, 99, 23};
quickSort(array, new LomutoPartitioningStrategy());
System.out.println(Arrays.toString(array));
}

Хорошие и чистые. Держит ваш код открыт для расширения, но закрыты для модификации.

1
ответ дан 19 марта 2018 в 11:03 Источник Поделиться