Массив разделов на основе пивота

Question

Я написал простую реализацию для разбиения массива на основе pivot.Для простоты первый элемент в массиве принимается за элемент поворота.Ниже приведен код, который я написал

public static void partitionOnPivot(int[] a , int lo , int hi)
{

    int pivot = lo;

    while (lo < hi)
    {
        while(a[lo] <= a[pivot]) lo++;
        while(a[hi] > a[pivot]) hi--;

        if(lo < hi) //we are already done with these cases
        {
            ArrayUtil.swap(a, lo++, hi--);
        }
    }

    ArrayUtil.swap(a, pivot, lo);

}

Теперь для приведенного ниже массива

{26,84,98,45}

в одной точке, lo и hi будут стоять с индексом 1.

В этот момент 26 поменялся местами с 84, и на выходе получится {84, 26, 98, 45}.26 нужно было оставить в покое.

Я вносил некоторые изменения в течение достаточно долгого времени без какого-либо прогресса.Как мы справимся с этим угловым случаем?Есть ли какая-либо ошибка в программе?

Answer 1

Бьюсь об заклад,

ArrayUtil.swap(a, lo++, hi--);, где ваше нежелательное поведение закрадываетсяПоскольку ++ является постинкрементным, вы меняете верхний элемент своим стержнем, а затем увеличиваете его.

Answer 2

"в одном месте, и вот, и привет будут стоять в индексе 1" -> НЕПРАВИЛЬНО Из написанной вами программы ясно, что lo будет с индексом 1, а hi с индексом 0. Так что следующее условие if будет пропущено, и будет выполнена последняя строка, меняющая значения двух индексов

  if(lo < hi) //THE FOLLOWING STATEMENT WILL BE SKIPPED
   {
        ArrayUtil.swap(a, lo++, hi--);
   } 

Результирующий массив будет {84, 26, 98, 45}. что именно то, что вы получаете. Вы должны внести следующие изменения

while(a[lo] <= a[pivot]) lo++;
while(a[hi] > a[pivot]) hi--;

становится

while(a[lo + 1] <= a[pivot]) lo++;
while(a[hi - 1] > a[pivot]) hi--;

Также, как уже указывали другие, попробуйте изменить

ArrayUtil.swap(a, lo++, hi--);

до

ArrayUtil.swap(a, lo, hi);

P.S. Я думаю, что операторы увеличения и уменьшения - это зло. Нужно действительно обращать внимание на поведение post / pre при их использовании. Старайтесь избегать их как можно больше.

Answer 3

используйте этот оператор в конце внешнего цикла while

ArrayUtil.swap(a, pivot, hi);