Quicksort - причина для проверки равенства

Многие примеры в Интернете о Quicksort (на Java) близки к этому:

private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];

    while (i <= j) {

      while (numbers[i] < pivot) {
        i++;
      }

      while (numbers[j] > pivot) {
        j--;
      }

      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }

    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
}

То, о чем я озадачился, - это то, что есть те равенства:

1) while (i <= j) вместо while (i < j)

2) if (i <= j) вместо if (i < j)

Существуют ли какие-либо граничные случаи, когда это равносильно? Из моего понимания, если бы мы имели if(i == j), тогда мы бы в основном обменивали одно и то же значение с тем же значением.

Кто-нибудь может решить эту загадку для меня?

Ответы

Ответ 1

Предположим, что условие заменено на i < j.

Давайте посмотрим, что произойдет для такого массива, как:

5,4,3,2,1

Цикл while завершится с i = 2 и j = 2, а у нас будут перекрывающиеся вызовы функции quicksort, и эти вызовы будут:

quicksort(0,2) and quicksort(2,4)

тогда как если бы у нас было это условие i<=j, цикл завершился бы с i = 4 и j = 1, и теперь мы имели бы вызовы как:

quicksort(0,1) and quicksort(3,4)

которые являются правильными вызовами.

Итак, в принципе вы правы, нет смысла обменивать одни и те же элементы, но автор кода должен был исключить его, чтобы избежать необходимости добавления дополнительного условия, которое вам не нужно менять, когда я равно j