CODEWITHSUNDEEP
javaalgorithmbig-oquicksort
user4759923
user4759923

Reputation: 531

Java Quicksort quadratic runtime behaviour

I tried to implement an efficient sorting algorithm in Java. For this reason, I also implemented quicksort and use the following code:

public class Sorting {
    private static Random prng;

    private static Random getPrng() {
        if (prng == null) {
            prng = new Random();
        }
        return prng;
    }

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

    public static void sortInternal(int[] array, int start, int end) {
        if (end - start < 50) {
            insertionSortInternal(array, start, end);
        } else {
            quickSortInternal(array, start, end);
        }
    }

    private static void insertionSortInternal(int[] array, int start, int end) {
        for (int i=start; i<end - 1; ++i) {
            for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--) {
                ArrayUtilities.swap(array, ptr, ptr - 1);
            }
        }
    }

    private static void quickSortInternal(int[] array, int start, int end) {
        int pivotPos = getPrng().nextInt(end - start);
        int pivot = array[start + pivotPos];
        ArrayUtilities.swap(array, start + pivotPos, end - 1);
        int left = start;
        int right = end - 2;
        while (left < right) {
            while (array[left] <= pivot && left < right) {
                ++left;
            }
            if (left == right) break;
            while (array[right] >= pivot && left < right) {
                right--;
            }
            if (left == right) break;
            ArrayUtilities.swap(array, left, right);
        }
        ArrayUtilities.swap(array, left, end - 1);
        sortInternal(array, start, left);
        sortInternal(array, left + 1, end);
    }
}

ArrayUtilities.swap just swaps the two given elements in the array. From this code, I expect O(n log(n)) runtime behaviour. But, some different lengths of arrays to sort gave the following results:

10000 elements: 32ms

20000 elements: 128ms

30000 elements: 296ms

The test ran 100 times in each case, and then the arithmetic mean of the running times was calculated. But clearly, as opposed to the expected behaviour, the runtime is O(n^2). What's wrong with my algorithm?

Upvotes: 1

Views: 301

Answers (2)

hanif
hanif

Reputation: 674

In your insertion-sort implementation your array will be sorted in descending order, while in your quick-sort the array is sorted in ascending order. So replace(for descending order):

for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--)

with

for (int ptr=i; ptr>0 && array[ptr - 1] > array[ptr]; ptr--)

It also seems like your indexing is not correct. Try to replace:

sortInternal(array, 0, array.length - 1);

with:

sortInternal(array, 0, array.length);

And in the insertions sort first for loop you don't need to do end - 1, i.e. use:

for (int i=start; i<end; ++i)

Finally, add if (start >= end) return; at the beginning of the quick-sort method.

And as @ljeabmreosn mentioned, 50 is a little bit too large, I would have chosen something between 5 and 20.

Hope that helps!

Upvotes: 1

ljeabmreosn
ljeabmreosn

Reputation: 169

The QuickSort "optimized" with Insertion Sort for arrays with length less than 50 elements seems to be a problem.

Imagine I had an array of size 65, and the pivot happened to be the median of that array. If I ran the array through your code, your code would use Insertion Sort on the two 32 length subarrays to the left and right of the pivot. This would result in ~O(2*(n/2)^2 + n) = ~O(n^2) average case. Using quick sort and implementing a pivot picking strategy for the first pivot, the time average case would be ~O((nlog(n)) + n) = ~O(n(log(n) + 1)) = ~O(n*log(n)). Don't use Insertion Sort as it is only used when the array is almost sorted. If you are using Insertion Sort solely because of the real running time of sorting small arrays might run faster than the standard quick sort algorithm (deep recursion), you can always utilize a non-recursive quick sort algorithm which runs faster than Insertion Sort.

Maybe change the "50" to "20" and observe the results.

Upvotes: 0

Related Questions