Приращение/уменьшение во время целочисленной свопинга в реализации быстрой сортировки

Question

Я пытаюсь реализовать quicksort на C#. Я нашел код очень похожий на мой код ниже в Интернете:

public void Sort(List<int> list, int low, int high) 
    { 
     int i = low; 
     int j = high; 

     IComparable pivot = list[(low + high)/2]; 

     while (i <= j) 
     { 
      while (list[i].CompareTo(pivot) < 0) 
      { 
       i++; 
      } 
      while (list[j].CompareTo(pivot) > 0) 
      { 
       j--; 
      } 
      if (i <= j) 
      { 
       int temp = list[i]; 
       list[i++] = list[j]; // ?? 
       list[j--] = temp; // ?? 
      } 
     } 

     if (j > low) 
     { 
      Sort(list, low, j); 
     } 
     if (i < high) 
     { 
      Sort(list, i, high); 
     }    
    } 

код работает отлично, но я не могу понять, почему я и J необходимости увеличиваться и уменьшаться при замене целых чисел в списке [I] и список [J].

Я новичок в сортировке алгоритмов. Я был бы очень благодарен за любые идеи.

Answer 1

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

Рассмотрим следующий пример.

4 1 7 3 5 4 8 1 9 
      ↑   ↑    ↑ 
      i  pivot   j 

значение в i больше pivot, и один на j меньше, что делает их право на своп. Однако, как только своп готов, бессмысленно повторять сравнение тех же двух элементов, поскольку мы уже знаем, что они находятся в правильном месте. Таким образом, мы продвигаем i и j как часть той же операции.

4 1 1 3 5 4 8 7 9 
       ↑ ↑   ↑ 
       i pivot  j 

Редактировать: Операции являются постфикса, то есть они сделаны после задания. Следующие были бы эквивалентны:

int temp = list[i]; 
list[i] = list[j]; 
i = i + 1; 
list[j] = temp; 
j = j + 1;