изменить стержень в моем алгоритме быстрой сортировки Java

Question

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

public int[] quickSort( int[] a, int start, int end){

    int l = start;
    int r = end;

    int pivotIndex = start; //<---- first element in the array as pivot! 

    // must be at least two elements
    if ( end - start >= 1){

        // set pivot
        int pivot = a[pivotIndex];


        while ( r > l ){
            // scan from the left
            while ( a[l] <= pivot && l <= end && r > l  ){
                l++;
            }
            while ( a[r] > pivot && r >= start && r >= l){
                r--;
            }
            if ( r > l ){
                this.swap(a, l, r);
            }
        }
        this.swap(a, pivotIndex, r);

        System.out.println("calling quickSort on " + start + " and " + (r-1));                 
        quickSort(a, pivotIndex, r - 1); // quicksort the left partition
        System.out.println("calling quickSort on " + (r+1) + " and " + end);
        quickSort(a, r + 1, end);   // quicksort the right partition

    } else {
        return a;
    }

    return a;
}    

И это работает хорошо, но если я изменю pivotIndex наскажем int pivotIndex = end; я получаю такой результат:

run:
2, 8, 7, 1, 3, 5, 6, 4, 
2, 8, 7, 1, 3, 5, 6, 4, 
swapping l:8 and r:4
2, 4, 7, 1, 3, 5, 6, 8, 
swapping l:7 and r:3
2, 4, 3, 1, 7, 5, 6, 8, 
swapping l:8 and r:1
calling quickSort on 0 and 2
calling quickSort on 4 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
swapping l:7 and r:1
2, 4, 3, 8, 1, 5, 6, 7, 
swapping l:7 and r:1
calling quickSort on 4 and 3
calling quickSort on 5 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
swapping l:5 and r:1
2, 4, 3, 8, 7, 1, 6, 5, 
swapping l:5 and r:1
calling quickSort on 5 and 4
calling quickSort on 6 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
swapping l:6 and r:1
2, 4, 3, 8, 7, 5, 1, 6, 
swapping l:6 and r:1
calling quickSort on 6 and 5
calling quickSort on 7 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
BUILD SUCCESSFUL (total time: 1 second)

Как заставить алгоритм работать с pivotIndex как любым индексом 0 to a.length

Answer 1

Вы можете просто поменять выбранную вами опорную точку с первым элементом в массиве, прежде чем начинать сортировку, таким образом, она будет работать точно так же, как и раньше.

int l = start;
int r = end;

this.swap(a, choosePivot(), start); 
int pivotIndex = start; 

Answer 2

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

/* Selecting the pivot to be a random-ish element
   and pivotIndex to be beginning, since we don't know
   where it will be until we loop through the list */
int pivot = a[someInt];
int pivotIndex = begin-1;
//have to keep track of where the pivot actually is in the list
int currentPivotIndex = someInt;

for(int i = begin; i <= end; i++) {
    if(a[i] <= pivot) {
        //for each element less than the pivot
        //the pivotIndex moves by one
        pivotIndex++;
        //place the element to the left of the pivot
        this.swap(a, pivotIndex, i);
        //update currentPivotIndex if needed
        if(a[pivotIndex] == pivot) {
            currentPivotIndex = pivotIndex;
        }
    }
}
//put the pivot in its place
this.swap(a, pivotIndex, currentPivotIndex);

Answer 3

Это странное поведение, которое, скорее всего, вызвано тем, что ваш элемент pivot участвует в разбиении.

В первой строке вывода указано swapping l:8 and r:4, но это должно было быть swapping l:8 and r:3.Потому что 4 - это элемент pivot, и он не принадлежит ни разделу слева, ни разделу справа.Это элемент в середине перегородок.Он должен быть изолирован во время разбиения.

Чтобы исправить эту проблему, после выбора оси передвиньте ее до конца.Т.е., во-первых, замените pivot последним элементом массива.Следовательно, вы можете изолировать его от процесса разбиения.Затем начните цикл while с l = start and r = end - 1, потому что end в данный момент является пивотом.Оставить это в покое.После того, как вы закончите с разбиением, восстановите стержень в середине двух разделов.Середина - это место, где l и r встречаются.

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

Не имеет прямого отношения, но ваш выбор элемента pivot оказывает огромное влияние на производительность быстрой сортировки.С его текущей версией, попадание в худшем случае (O(n^2)) вполне вероятно.Проще говоря, вы можете выбрать его случайным образом, что создает O(nlogn) сложность с высокой вероятностью.