Добрый вечер Уважаемые эксперты. Изучая алгоритм быстрой сортировки у меня возникли проблемы.
Использовал алгоритм с этого сайта Алгоритм быстрой сортировки. А именно - просто алгоритм, начальный, не модернизировал и ничего далее с ним не делал(см.Приложение). Написал программу, которая реализует данный алгоритм, она работает отлично. Но все же сколько всего не перечитывал не смог понять как же он все таки перемещается по массиву. Для того чтобы объяснить приведу часть исследования:
При сортировке данной последовательности -
a[0]=2 a[1]=3 a[2]=4 a[3]=2 a[4]=4 a[5]=2 a[6]=1 a[7]=3 a[8]=1 a[9]=3 a[10]=1
Ход сортировки следующий:
1)2 3 4 2 4 2 1 3 1 3 1
2)1 1 1 2 4 2 4 3 3 3 2
3)1 1 1 2 4 2 4 3 3 3 2
4)1 1 1 2 4 2 4 3 3 3 2
5)1 1 1 2 2 2 3 3 3 4 4
6)1 1 1 2 2 2 3 3 3 4 4
7)1 1 1 2 2 2 3 3 3 4 4
8)1 1 1 2 2 2 3 3 3 4 4
9)1 1 1 2 2 2 3 3 3 4 4
Жирным шрифтом я выделил опорный элементы в данном шаге.
В начале понятно движение - 1 - 2 шаг. А дальше опорный элементы пошли вправо, особенно 4 шаг. Долго сидел, думал над тем, как это происходит если j то передавалась как R и она теперь находится в самом начале. То как выбирается последовательность и опорный элемент аж с позиции под номером 7, если считать с нуля.
Пожалуйста, объясните из чего вытекают данные шаги.



Приложение:
Вызов функции:
q( a, 0, n - 1 );
Функция:
void q(int *a,int L,int R)
{
int i,j,k,temp;
i=L;
j=R;
k = a[(L + R)/2];
while (i<=j)
{
while (a[i]<k) i++;
while (k<a[j]) j--;
if (i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}
if (L<j) q(a,L,j);
if (i<R) q(a,i,R);
}