Быстрая сортировка. Если элементы в массиве повторяются, то слева элементы должны быть строго меньше за пивот? а справа больше равны пивоту?
В алгоритме быстрой сортировке с повторяющимися элементами часто бывает такое что в левой части остаются элементы меньше равны опорному элемента,а в правой части больше равны опорному элементу. Может ли такое быть? на всех сайтах пишется что элементы равные опорному должны быть справа от опорного элемента ? вот код
void quickSort(Array& arr, int left, int right,int&comp,int&swaps)
{
int i = left;
int j = right;
int pivot = arr[(left + right) / 2];
while (i <= j)
{
comp++;
while (arr[i] < pivot)
{
i++;
comp++;
}
comp++;
while (arr[j] > pivot)
{
j--;
comp++;
}
if (i <= j)
{
swaps++;
swap(arr[i], arr[j]);
i++;
j--;
}
}
if (left < j)
{
quickSort(arr, left, j,comp,swaps);
}
if (i < right)
{
quickSort(arr, i, right,comp,swaps);
}
}