First and last pivot element vs generic placement with very large N-CodePudding

I've implemented a QuickSort algorithm along with a Time-Complexity control. It works fine with smaller N but once i get closer to larger N the StackOverflow is inevitable. Im thinking that having the pivot element as the last element might be what's causing this.

My first thought was to simply always use the middle element as the pivot element to avoid this but since the test-program throws an 'unsorted exception', it's not a valid solution.

Any ideas how i can work my way around this?

public class QuickSorter implements IntSorter{

int partition (int a[], int lo, int hi) {
    int pivot = a[hi]; // pivot element
    int i = (lo - 1);

    for (int j = lo; j <= hi - 1; j  ) {
        if (a[j] < pivot) {
            i  ;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    int temp = a[i 1];
    a[i 1] = a[hi];
    a[hi] = temp;
    return (i   1);
}



@Override
public void sort(int[] a) {

    int lo = 0;
    int hi = a.length-1;
    if (lo < hi) {
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p   1, hi);
    }
}

private void sort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p   1, hi);
    }
}
}

Testcode:

private static void testSort(IntSorter sorter, int firstN, boolean ordered) {
    double t1 = 0;
    int N = firstN/2;

    while (t1 < 0.7 && N < 10000000) {
        N *= 2;
        int[] a = create(N, ordered);
        t1 = timeit(sorter, a);
        System.out.println("T(" N ")=" t1);
        ArrayUtil.testOrdered(a);
    }
    int[] a = create(4*N, ordered);
    double t4 = timeit(sorter, a);
    ArrayUtil.testOrdered(a);
    double t01 = t1 / (N   * Math.log(N  )); 
    double t04 = t4 / (4*N * Math.log(4*N));
    System.out.println("T(" 4*N ")=" t4 " growth per N log N: " t04/t01);
    if (t04/t01 > 1.25) {
        System.out.println(sorter.getClass().getName() ".sort appears not to run in O(N log N) time");
        System.exit(1);
    }
}

public static void testOrdered(int[] a) {
    int N = a.length;
    for (int i = 1; i < N; i  ) {
        if (a[i] < a[i-1]) {
            throw new SortingException("Not sorted, a[" (i-1) "] > a[" i "]");
        }
    }
}

CodePudding user response：

As Thomas comments, using the middle element as the pivot should work fine. It's a common choice, actually, because it works well with input arrays that happen to be already fully or partially sorted.

As for avoiding stack overflow, a common approach is to only recurse on the shorter part after a partitioning step - this ensures at least a halving of the array being processed at each level, so e.g. a 1,000,000 element array will have a maximum call depth of roughly 20 ( log2(1,000,000) ).

So, instead of

private void sort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p   1, hi);
    }
}

You do

private void sort(int[] a, int lo, int hi) {
    while (lo < hi) {
        int p = partition(a, lo, hi);
        // recurse on smaller part, loop on larger part
        if (((p - 1) - lo) > (hi - (p   1))) {
          sort(a, p   1, hi);
          hi = p - 1;
        }
        else {
          sort(a, lo, p - 1);
          lo = p   1;
        }
    }
}

CodePudding user response：

Shuffle the array before sorting with the method below seems to have fixed the issues i had aswell

public void shuffle(int[] a) {
    int N = a.length;
    Random randomGenerator = new Random();
    for (int i = 0; i < N; i  ) {
        int r = i   randomGenerator.nextInt(N-i);     // between i and N-1
        int t = a[i]; a[i] = a[r]; a[r] = t;
    }
}