6
\$\begingroup\$

I've just tried my hand at Quicksort, and I seem to have gotten it working (thanks to Stack Overflow). However, is it "true" Quicksort? And is it decently written?

public static void sort(List<Integer> arr, int left, int right) {
        int i = left - 1;
        int j = right + 1;
        if (right - i == 0 || right - i == 1) return;
        int v = arr.get(right);     

        for(;;) {
            while(arr.get(++i) < v);
            while(v < arr.get(--j) && j != 0)
                if(j == 1)break;
            if(i >= j)break;

            Collections.swap(arr, i, j);
        }
        Collections.swap(arr, i, right);

        sort(arr, left, i - 1);
        sort(arr, i, right);
}

I know I should use a regular array (int[]) for speed, but we can ignore that for now.

\$\endgroup\$
7
\$\begingroup\$
   int v = arr.get(right);     

I assume v holds the partitioned item. But I don't know what you mean by v, so you can make your variable names more clear. Java's convention is to use CamelCase for variable names, so you might want to do that.

   if (right - i == 0 || right - i == 1) return;

As I understand it, if right - i is either 0 or 1, the method will return. So why not just check if right - i is less than or equal 1?

    if (right - i <= 1) return;

It might be more readable to put your statements inside braces, I think:

        while(arr.get(++i) < v);
        while(v < arr.get(--j) && j != 0)

might be confusing: Perhaps it would be more understandable if you do this:

        while(v < arr.get(--j) && j != 0) {
            if(j == 1)break;
        }

Regarding that code, the condition j != 0 will never be false because the loop will stop when j becomes 1. I think you can eliminate the if statement like this:

        while(v < arr.get(--j) && j > 1);

Currently your method signature is:

public static void sort(List<Integer> arr, int left, int right)

If we want to sort all items, we might call it as:

sort(list, 0, list.size()-1);

It might be better to write an overloaded method for convenience, Like this:

public static void sort(List<Integer> arr) {
    sort(arr, 0, arr.size()-1);
}

Now if someone wants to sort all items in the list, they don't have to provide the beginning and end of the sort.

\$\endgroup\$
  • \$\begingroup\$ Hm, okay. All your suggestions make sense. I'm usually better about var names, actually. Don't recall why I used v. \$\endgroup\$ – IHazABone Apr 28 '15 at 18:09
  • \$\begingroup\$ I'd vote your answer up but not enough rep on this subforum. \$\endgroup\$ – IHazABone Apr 28 '15 at 18:10
3
\$\begingroup\$

Your title specifically lists efficiency as being significant.

If someone were to call your sort as:

List<integer> values = new LinkedList<>();
values.addAll(........);
sort(values, 0, values.size() - 1);

Then your sort would be horribly slow.

The reason is that these lines:

    Collections.swap(arr, i, j);
.....
Collections.swap(arr, i, right);

are not efficient when it comes to Linked Lists. Those lines would require a scan of the entire list because LinkedLists are not suited for high-performance random access. An ArrayList would be fine.... but, you don't always have an Arraylist

Additionally, note that there is no reason why you have to fix the Generic type at <Integer>. You force your comparator to do an "auto-unbox" of the values here:

int v = arr.get(right);     

and also in the arr.get(...) calls in the checks.

If you change your method signature to be a generic method like:

public static <T extends Comparable<? extends T>> void sort(List<T> arr, int left, int right)

Then you will be able to use the compareTo methods for comparisons.... like:

    T valus = arr.get(right);     

    for(;;) {
        while(value.compareTo(arr.get(++i)) >= 0);
        while(value.compareTo(arr.get(--j)) < 0 && j != 0)

Note, now that I am looking at the code more carefully, I see some problems in there.....

  1. Your method will do odd things if there are duplicate values in the input... right? You need a <= or >= somewhere. I put it on the first loop.
  2. you do not handle null values in the input (nor do I).
\$\endgroup\$
  • \$\begingroup\$ I assume no null values. Nothing weird happens with duplicate numbers. \$\endgroup\$ – IHazABone Apr 28 '15 at 18:58
  • \$\begingroup\$ Thanks for everything else, though. \$\endgroup\$ – IHazABone Apr 28 '15 at 18:58
3
\$\begingroup\$
int i = left - 1;
int j = right + 1;
if (right - i == 0 || right - i == 1) return;

This might be right.. or left, or i, but is there a quick way to sort it out? To understand it, I must back-substitute i, assume which of your bounds are inclusive (lets hope, "left" included, "right" excluded as with Arrays.sort?), and rewrite it as

int length = right - left;
// right - i == length + 1
if (length == -1 || length == 0) return;

but I'd expect something like

if (length <= 1) return;

which needs no comment as there's obviously nothing to sort.

Your condition is different and that's either wrong or you interpret the inputs differently.

You don't have to document like this, but the bare minimum is

Sort the array from left (included) to right (excluded).


I'm sure this will blow performance to the land where bubble-sort lives whenever you start with a sorted sequence:

int v = arr.get(right);     

Let's call v threshold or pivot.

\$\endgroup\$
2
\$\begingroup\$

Duck Typing QuickSorts

Tony Hoare's QuickSort was considered quick in 1962. But it was not because it has 0(n log n) average performance. Merge sorting was already established [Knuth credits Von Neumann in 1945] and has better worst case performance than QuickSort.

What made QuickSort a quick sort was it's space efficiency. Hoare's insight was in-place sorting. QuickSort was quicker because in-place sorting meant more blocks could be read from tape into fast memory on each IO cycle [and likewise written]. The speed improvement came from reduced latency. Because IO then as now was so much slower than fast memory, the practical performance improvement on non-trivial data was massive.

It's common to illustrate functional programming using a double filter for the pivot and to call it a "quicksort". These necessarily avoid inplace mutations.

Consider this page of examples in Python. If you consider the Python examples to be quicksorts, then clearly the code under review is a quicksort. If you don't then...

Garbage Out

Because the Java manages memory deallocation via garbage collection; because the JVM offers just-in-time compilation that may perform arbitrary optimizations of the bytecode, and different ones at different times based on how much time it has due to what else is running; and because modern CPU's utilize multiple levels of caching, simple definitions of "in place" become increasingly brittle the more absolute our definition of "true quicksort" becomes. Welcome to the effects of post modernism in computing.

Practical Improvement

Issues of truth aside, the performance of QuickSort degrades toward worst case 0(n^2) if the data is sorted in reverse order. Hoare advised selecting the pivot at random rather than sequentially. That is randomly selecting the pivot from the interval [i, j] makes worst case performance statistically unlikely for any interestingly sized data. Of course, if the data source is known to be random then it's a waste of time. On the other hand, in the real world many data sources aren't random.

Final Remarks

There are many sound insights in the other code reviews, and there's no point in chewing the same ground.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.