Быстрая сортировка в Java

176
27 апреля 2018, 15:09

Всем привет.

По запросу "quicksort array Java" гуглится чаще всего такой алгоритм:

public class Main {
public static void main(String[] args) {
    int[] x = { 9, 2, 4, 7, 3, 7, 10 };
    System.out.println(Arrays.toString(x));
    int low = 0;
    int high = x.length - 1;
    quickSort(x, low, high);
    System.out.println(Arrays.toString(x));
}
public static void quickSort(int[] arr, int low, int high) {
    if (arr == null || arr.length == 0)
        return;
    if (low >= high)
        return;
    // pick the pivot
    int middle = low + (high - low) / 2;
    int pivot = arr[middle];
    // make left < pivot and right > pivot
    int i = low, j = high;
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // recursively sort two sub parts
    if (low < j)
        quickSort(arr, low, j);
    if (high > i)
        quickSort(arr, i, high);
}

}

В связи с этим несколько вопросов:

1) Зачем вообще передается аргумент low, если нижняя граница массива всегда = 0?

2) Опорная точка (middle) высчитывается следующим образом:

int middle = low + (high - low) / 2;

Как мы знаем, low всегда = 0.

Почему если убрать из этого выражения "low +" , то результатом становится StackOverflowError? Как может прибавление ноля на что-то влиять?

int middle = (high - low) / 2; --> StackOverflowError

3) При этом если вместо

int middle = (high - low) / 2;

написать

int middle = (high + low) / 2;

то все работает. Опять же - каким образом может на что-то влиять сложение ноля вместо вычитания?

Заранее спасибо за ответы.

Answer 1

Нижняя граница массива редко когда 0. Метод quickSort рекурсивный. При каждом вызове он разбивает массив на две части и вызывает сам себя для каждой из частей. Так продолжается до тех пора, пока сортируемая часть не станет слишком маленькой. Если убрать low + то перестанет работать базовое ограничение и метод будет вызывать себя до тех пор, пока не исчерпает стек.

READ ALSO
Сгруппировать сумму по дням

Сгруппировать сумму по дням

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

223
Создание dll c++. Описание интерфейса. Visual Studio

Создание dll c++. Описание интерфейса. Visual Studio

Подскажите, пожалуйста, мне необходимо создать библиотеку преобразования данных в определенный формат

248
Строковый тип в switch case

Строковый тип в switch case

Можно ли написать конструктор switch case со строковым типом переменных C++ ???

183
Как правильно положить в буфер число размером более чем 1 байт?

Как правильно положить в буфер число размером более чем 1 байт?

Работаю программистомМои программы успешно работают

226