C++ QuickSort not clear

Question

Я пытаюсь понять механизм быстрой сортировки, но до сих пор я не могу понять это. Согласно википедии, этапы:

1. Выберите элемент, называемый стержнем, из списка.

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

3. Рекурсивно применяйте вышеуказанные шаги к подэлементу элементов с меньшими значениями и отдельно подэлемент элементов с большими значениями.

И это код:

int partition(int arr[], int left, int right) 
    { 
      int i = left, j = right; 
      int tmp; 
      int pivot = arr[(left + right)/2]; 

      while (i <= j) { 

       while (arr[i] < pivot) 
         i++; 
       while (arr[j] > pivot) 
         j--; 
       if (i <= j) { 
         tmp = arr[i]; 
         arr[i] = arr[j]; 
         arr[j] = tmp; 
         i++; 
         j--; 
       } 
      } 
      return i; 
    } 
    void quickSort(int arr[], int left, int right) { 
      int index = partition(arr, left, right); 
      if (left < index - 1) 
       quickSort(arr, left, index - 1); 
      if (index < right) 
       quickSort(arr, index, right); 
    } 

Все как-то мне ясно, кроме одного. Почему функция перегородки возвращает i, а не j?

Answer 1

Я нашел эту программу (и выход) here. Посмотрите,

#include <iostream> 
using namespace std; 

const int INPUT_SIZE = 10; 

// A simple print function 
void print(int *input) 
{ 
    for (int i = 0; i < INPUT_SIZE; i++) 
     cout << input[i] << " "; 
    cout << endl; 
} 

// The partition function 
int partition(int* input, int p, int r) 
{ 
    int pivot = input[r]; 

    while (p < r) 
    { 
     while (input[p] < pivot) 
      p++; 

     while (input[r] > pivot) 
      r--; 

     if (input[p] == input[r]) 
      p++; 
     else if (p < r) 
     { 
      int tmp = input[p]; 
      input[p] = input[r]; 
      input[r] = tmp; 
     } 
    } 

    return r; 
} 

// The quicksort recursive function 
void quicksort(int* input, int p, int r) 
{ 
    if (p < r) 
    { 
     int j = partition(input, p, r);   
     quicksort(input, p, j-1); 
     quicksort(input, j+1, r); 
    } 
} 

int main() 
{ 
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600}; 
    cout << "Input: "; 
    print(input); 
    quicksort(input, 0, 9); 
    cout << "Output: "; 
    print(input); 
    return 0; 
} 

OUTPUT:- 
Input: 500 700 800 100 300 200 900 400 1000 600 
Output: 100 200 300 400 500 600 700 800 900 1000