Given that the first element is the core, why shouldn't the index exceed the border of the array?

Question

Inside two while partition loops , why does it seem that if the index exceeds the bounds of the array, it is not considered at first sight? [This is the correct code from Big Java, I "I already tested, only the index confuses me"

public void sort(int from, int to)
   {
      if (from >= to) return;
      int p = partition(from, to);
      sort(from, p);
      sort(p + 1, to);
   }

   private int partition(int from, int to)
   {
      int pivot = a[from];
      int i = from - 1;
      int j = to + 1;
      while (i < j)
      {
         i++; while (a[i] < pivot) i++;//here
         j--; while (a[j] > pivot) j--;//here
         if (i < j) swap(i, j); 
      }
      return j;
   }

Answer 1

Since the core is selected from a single array and because of how the logic of the algorithm is implemented, you never need to check that the indices go out of bounds. At some point, the conditions must be true.

The correctness of the algorithm can be proved using cycle invariants.

1. private int partition(int from, int to)
2. {
3.    int pivot = a[from];
4.    int i = from - 1;
5.    int j = to + 1;
6.    while (i < j)
7.    {
8.        i++; 
9.        // at least one of a[i]...a[to] is greater than or equal to pivot 
10.       while (a[i] < pivot) i++;
11.       j--; 
12.       // at least one of a[from]...a[j] is less than or equal to pivot
13.       while (a[j] > pivot) j--;//here
14.       if (i < j) swap(i, j);
15.       // if i < j then at least one of a[i + 1]...a[to] is greater than or equal to pivot
16.       // if i < j then at least one of a[from]...a[j - 1] is less than or equal to pivot
17.   }
18.   return j;
19. }

9 12 ( 15, 16) , 6 17. , i j .

9, 12 .

1- , a[from] i = from.

( 1- ) i, j. i < j, 15. i 8 9 , 15. , 9 6 17.

pivot , [to], . .

sort(from, p == to ? p - 1 : p);
sort(p + 1, to);

sort(from, p);
sort(p + 1, to);

Answer 2

partition , i j pivot, - < >. . , .

int[] a;

private void sort() {
    sort(0, a.length - 1);
}

public void sort(int from, int to) {
    if (from >= to) {
        return;
    }
    int p = partition(from, to);
    sort(from, p);
    sort(p + 1, to);
}

private int partition(int from, int to) {
    int pivot = a[from];
    int i = from - 1;
    int j = to + 1;
    while (i < j) {
        i++;
        while (a[i] < pivot) {
            i++;
        }
        j--;
        while (a[j] > pivot) {
            j--;
        }
        if (i < j) {
            swap(i, j);
        }
    }
    return j;
}

private void swap(int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

public void test() {
    System.out.println("Hello");
    a = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    sort();
    System.out.println(Arrays.toString(a));
}

, numbers[low], - .

Answer 3

pivot, i < pivotIndex < j. ( , from <= to, increment/decment ).

In all iterations after the first indexes may become less fromor more than to, as i < jand swap-call in the last iteration of the loop placed element that creates the appropriate conditions for the cycle falsewhen the indexes iand jrespectively for the element in the position j a[j] > pivotwas false, but this element has been moved to position i < j, and for the element in the position i a[i] < pivotit was false, but this element was moved to the position j > i.