Lomuto-Partition в быстрой сортировке

Question

Как мы знаем, в quicksort вы можете использовать Lomuto-Partition. Я проверил много ссылок и почти все они придумали следующую реализацию:

int L_partition(int *a, int l, int r) 
{ 
    int i, j, p, t; 

    p = a[r]; 
    i = l - 1; 

    for(j =l; j <= r-1; j++) { 
     if(a[j] <= p) { 
      i++; 

      t = a[j]; 
      a[j] = a[i]; 
      a[i] = t; 
     } 
    } 

    t = a[i+1]; 
    a[i+1] = a[r]; 
    a[r] = t; 

    return i+1; 
} 

Мой вопрос, почему I начинается с л-1 и имеют все +- вещей ? Я думаю, что начните только с l в порядке. Я тестирую программу ниже. И он дает тот же результат, что и предыдущий. Это намного проще, чем выше.

int L_partition2(int *a, int l, int r) 
{ 
    int i, j, p, t; 

    p = a[r]; 
    i = l; 

    for(j = l; j <= r-1; j++) { 
     if(a[j] <= p) { 
      t = a[j]; 
      a[j] = a[i]; 
      a[i] = t; 

      i++; 
     } 
    } 

    t = a[i]; 
    a[i] = a[r]; 
    a[r] = t; 

    return i; 

} 

Answer 1

Это точно так же вы просто сдвигая использование i.

Обратите внимание, что вы меняете i после свопинга, потому что ваш действует с самого начала, а исходная версия увеличивает его перед свопом. Но важно то, что swap использует всегда один и тот же элемент (в вашей версии и оригинале).