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

Question

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

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

Чтобы сделать это проще, я просто использовал один указатель и начинаю обход элементов от начала до шага меньше конца, где лежит мой элемент разворота. Я предполагаю, что моя точка разворота находится в начале, поэтому я сохраняю другую переменную для хранения моего сводного индекса. В случае, если я нахожу какой-либо элемент меньше, чем мой элемент pivot, я делаю перестановку между моим предполагаемым pivot-индексом и текущим пройденным индексом и увеличиваю pivot-index на 1. В конце цикла у меня есть позиция для моего pivot ready, который я возвращаю.

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

Пожалуйста, помогите. С уважением

package com.algorithm.sorting;

public class QuickSort {

    public static void main(String[] args) {
            int a[] = { 5, 33, 45454, 43254, 2, 67, 8, 78, 8, 8, 8, 85654, 5, 4, -1, -1, 1, 234, 24, 43, 4, -7, 45, 4, -5,
                            544, 9, 8, 7, 6, 5, 4, 3, 2, 11, 2, 3, 4, 5, 6, 7, 8, 9 };
            quicksort(a);
            for (Integer i : a) {
                    System.out.println(i);
            }
    }

    public static void quicksort(int[] array) {
            quicksort(array, 0, array.length - 1);
    }

    private static void quicksort(int[] array, int start, int end) {
            if (start < end) {
                    int pivotIndex = partition(array, start, end);
                    quicksort(array, start, pivotIndex - 1);
                    quicksort(array, pivotIndex + 1, end);
            }
    }

    private static int partition(int[] array, int start, int end) {
            int pIndex = start;
            int mid = start + ((end - start) / 2);
            int temp = array[mid];
            array[mid] = array[end];
            array[end] = temp;

            int pivot = array[end];

            for (int i = start; i <= end - 1; i++) {
                    if (array[i] < pivot) {

                            temp = array[i];
                            array[i] = array[pIndex];
                            array[pIndex] = temp;
                            pIndex++;
                    }
            }
            array[end] = array[pIndex];
            array[pIndex] = pivot;
            return pIndex;
    }

}

(программа такая же, как я разместил в http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-quicksort.html, но теперь, когда я запутался в этом замешательстве, я хочу исправить себя и что я выложил)

Answer 1

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