Разбиение массива в Pivot

Question

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

Идея алгоритма проста.

Есть два указателяодин в начале массива и один в конце массива.Если элементы, на которые указывает i, меньше, чем pivot, продолжайте пропускать его, пока мы не найдем больший элемент;и продолжайте уменьшать j, пока мы не найдем элемент больше, чем меньший элемент.[Это общий алгоритм]

Теперь код

private  static void sortByPivot(int[] a)
{

    Random r = new Random();
    int index = r.nextInt(a.length);
    int pivot = a[index];

    System.out.println("pivot = " + pivot);

    int i =0 , j = a.length -1;

    while(true)
        {

            while(a[i] <= pivot) i++;

            while( j >0 && a[j] >= pivot) j--;

            if(i <= j)
            {
                break;
            }
            else{
                swap(a,i,j);
               }

        }

        swap(a,i,index); //swap the pivot and the i
}

Процедура обмена:

private static void swap(int[] a, int i , int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Когда я запускаю этотсо следующим массивом

  int[] a = {46,3,8,4,2,6,244,76} 

и когда для оси выбран 4, выходной результат будет

         4 3 8 46 2 6 244 76 

Для некоторых других точек, находящихся в ребре, я получаю исключение нулевого указателя.

Есть ли недостатки в реализации.Логика мне кажется правильной.Я пробовал это довольно давно, но я не могу это исправить.

Answer 1

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

Обратите внимание, что вы должны поменять местами значения a[i] и a[j], если i <= j, а также выйти из цикла.Вы делаете это в другом месте, что неправильно, потому что, если a[i] больше, чем пивот, и a[j] меньше, чем пивот, к тому времени, когда вы достигнете if, тогда они должны быть заменены, если i <= j.

Answer 2

Логика неверна. Вы только что написали код. Просто найдите минутку и запустите эту программу на любом входе, и вы сразу найдете недостаток.

Лучше было бы использовать подход, изображенный здесь на wikipedia Это встроенная версия разбиения массива, используемого в быстрой сортировке. Надеюсь, это решит вашу проблему.

Answer 3

Если вы просто пытаетесь все это отсортировать (я знаю, вы сказали «раздел», но будет ли это проблемой, если все будет отсортировано?) Для этого есть встроенные методы

java.util.Arrays.sort(int[] a)
java.util.Arrays.sort(int[] a, int fromIndex, int toIndex)

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Arrays.html

Если вам нужно сделать это самостоятельно (домашнее задание!), Попробуйте отладочный подход, описанный выше;напишите на бумаге, что вы ожидаете, затем полностью пройдитесь, чтобы увидеть, что происходит