Why is my quick sort so slow?

Question

I am practicing writing sorting algorithms as part of some interview preparation, and I am wondering if anybody can help me spot why this quick sort is not very fast? It appears to have the correct runtime complexity, but it is slower than my merge sort by a constant factor of about 2. I would also appreciate any comments that would improve my code that don't necessarily answer the question.

Thanks a lot for your help! Please don't hesitate to let me know if I have made any etiquette mistakes. This is my first question here.

private class QuickSort implements Sort {

        @Override
        public int[] sortItems(int[] ts) {
            List<Integer> toSort = new ArrayList<Integer>();
            for (int i : ts) {
                toSort.add(i);
            }
            toSort = partition(toSort);
            int[] ret = new int[ts.length];
            for (int i = 0; i < toSort.size(); i++) {
                ret[i] = toSort.get(i);
            }
            return ret;
        }

        private List<Integer> partition(List<Integer> toSort) {
            if (toSort.size() <= 1)
                return toSort;
            int pivotIndex = myRandom.nextInt(toSort.size());
            Integer pivot = toSort.get(pivotIndex);
            toSort.remove(pivotIndex);
            List<Integer> left = new ArrayList<Integer>();
            List<Integer> right = new ArrayList<Integer>();
            for (int i : toSort) {
                if (i > pivot)
                    right.add(i);
                else
                    left.add(i);
            }
            left = partition(left);
            right = partition(right);
            left.add(pivot);
            left.addAll(right);
            return left;
        }

}

Thanks a ton, everybody who helped!

This is my much improved class for posterity:

private class QuickSort implements Sort {

        @Override
        public int[] sortItems(int[] ts) {
            int[] ret = ts.clone();
            partition(ret,0,ret.length);
            return ret;
        }

        private void partition(int[] toSort,int start,int end) {
            if(end-start<1) return;
            int pivotIndex = start+myRandom.nextInt(end-start);
            int pivot = toSort[pivotIndex];
            int curSorted = start;
            swap(toSort,pivotIndex,start);
            for(int j = start+1; j < end; j++) {
                if(toSort[j]<pivot) {
                    if(j!=curSorted+1) 
                        swap(toSort,curSorted,curSorted+1);
                    swap(toSort,j,curSorted++);
                }
            }
            // Now pivot is at curSorted
            partition(toSort,start,curSorted);
            partition(toSort,curSorted+1,end);
        }
    }

Just throwing this out there, but quick sort is actually fastest when the array's numbers are completely random, as opposed to merge sort in which case the order doesn't matter. — sj755, Jan 01 '11 at 07:06
I suggest you have a look at the quick sort code in Collections. It is fairly fast and efficient. Or you could just use it. — Peter Lawrey, Jan 01 '11 at 09:53

score 10 · Accepted Answer · answered Jan 01 '11 at 07:03

10

One of the biggest advantages of Quicksort is that it can be implemented as an in-place algorithm. Don't create new lists, sort the elements in-place instead.

answered Jan 01 '11 at 07:03

James McNellis

348,265
75
913
977

as well , see if your input is not nearly sorted! – TalentTuner Jan 01 '11 at 07:05
4

@Saurabh: There's really no reason to do that. Quicksort only exhibits perverse quadratic performance for sorted input if you always select the leftmost element as the pivot. With a randomly selected or median-of-three pivot, this isn't a problem (in the OP's code, the pivot is selected randomly). – James McNellis Jan 01 '11 at 07:08
@James: Even though what you say is accurate, randomly selecting the pivot _has_ inputs (depending on the random choices) for which the performance will degrade. So even though Saurabh's comments are not entirely accurate, the motivation for the comment is still worthy of consideration: pathological data/corner cases etc. – Jan 06 '11 at 21:29
@Moron: Kind of. The fact that for some inputs, certain Quicksort implementations have quadratic time complexity is just a known fact about the algorithm. That's not really pathological. It is, however, pathological, when it takes quadratic time to sort already sorted input, because it's unreasonable. For most use cases, it's quite likely that the data will already be sorted or mostly sorted. The likelihood of random pivot selection requiring quadratic time to sort a sequence is much, much lower (almost insignificant). – James McNellis Jan 06 '11 at 21:36
That said, if I recall correctly, this is one of several reasons that Bob Sedgewick used to demonstrate why a median-of-three pivot selection is in most cases preferable to a random pivot selection. – James McNellis Jan 06 '11 at 21:37
@James: If the input is random, then it does not make any difference whether you select the leftmost or a random element as the pivot. The likelihood of performance degradation is the same... It is just harder to predict the "bad" inputs in the latter case. I guess we differ on what we mean by Pathological :-) Anyway, I guess you understood what I was trying to say. – Jan 06 '11 at 21:42

meriton · Answer 2 · 2011-01-01T17:01:10.260

In addition to not reusing lists, you convert between Integer and int in each step:

        for (int i : toSort) {  // converts from Integer to int
            if (i > pivot)
                right.add(i);  // converts from int to Integer
            else
                left.add(i);   // converts from int to Integer
        }

Note that conversion from int to Integer in general requires a new object to be created.

And finally random.nextInt() might be a non-trivial operation. Perhaps it would be better to only select a random pivot if the toSort exceeds a certain size and use a simpler pivor selection strategy otherwise (Measure it!).

Why is my quick sort so slow?

2 Answers2

Linked