Quicksort implementation issue - Java

Hmm. So, is it just slower by a constant factor? It looks to me like you're doing maybe ~4 times as many array accesses as you need to, so you could speed it up by a small constant factor by being a bit more clever (e.g. by storing A[from] in a temporary variable and eliminating some unnecessary swaps).

But I don't see anything fundamentally wrong here that would make it more than about 10x slower than it should.

Also is the merge sort you're comparing to one that you wrote in Java too?

This is because of your choice of array to be sorted. You're using random numbers less than 1000 to fill your 6 million size array. This is going result in a lot of ties, which is quick sort's worst case situation.

If you change the RNG.nextInt(1000) to RNG.nextInt(size), you will see quick sort being faster than merge sort.

This is because of your choice of array to be sorted. You're using random numbers less than 1000 to fill your 6 million size array. This is going result in a lot of ties, which is quick sort's worst case situation.

If you change the RNG.nextInt(1000) to RNG.nextInt(size), you will see quick sort being faster than merge sort.

Was going to mention this. Quicksort is only faster than mergesort in certain scenarios.

Also an FYI quicksort has to sort completely random situations. If there's any semblance of order mergesort can be faster.

I'm not convinced that is the case, for three possibly related reasons:

1. I neglected to mention that I copied someone's implementation and it ran quicker than my merge_sort on this same input.

2. As well as I can remember my own code, I do nothing in the case of ties; It's just one check, move on. Swaps only happen when the accessed index has smaller value than the pivot, which is why I also believe that my code is doing the (almost) minimum number of swaps necessary (one swap for each index less than pivot lying on the right side of pivot).

3. quickSort's worst case involves choosing pivot values on either extreme ends, thus ending up doing the maximum number of swaps, i.e. n-1. E.g. Choosing 9 or 1 in the [9;8;7;6;5;4;3;2;1] array will both result in 8 swaps for the partitioning step; whereas choosing 4 in [4;4;4;4;4;4;4;4;4] will result in no swaps at all (just linear scan and comparison).

@ Corn: Randomized quickSort makes no assumptions about the input's order, due to the internal randomization step. (Random + more random = random // deterministic + random = random). Its runtime is "on average" O(nlogn) regardless what input is given, with a smaller constant coefficient than mergeSort's. Theoretically, quickSort's worst runtime is O(n^2), but this almost never happens (regardless of input). I still haven't quite mastered the proof, though.

1. Maybe you should paste their code here then.

2.3. The whole point is that quicksort is only fast when two partitions are roughly the same size. When you have a large number of duplicate values one partition will be much larger than the other, causing more recursive calls. In the case of the entire array being duplicates, it becomes the same as selection sort, i.e. O(n^2). You should be counting the number of comparisons there, not number of swaps.

When people discuss sorting algorithms, they generally assume there are no duplicate values.

When the array is passed into the function, does it passed as reference or by value?
If the array is cloned many times, it would slow down a lot; delete the intermediate arrays immediately when it become useless (vs. waiting for garbage collection) will help speeding up the recursive process;

I haven't deal with java for a long time, so I could be wrong.

When the array is passed into the function, does it passed as reference or by value?
If the array is cloned many times, it would slow down a lot; delete the intermediate arrays immediately when it become useless (vs. waiting for garbage collection) will help speeding up the recursive process;

I haven't deal with java for a long time, so I could be wrong.

It's passed by reference in Java so there's no problem there.

Merge sort is supposed to be faster than quick sort.
On worst case scenarios quick sort is O(n^2) while Merge sort is O(nlogn).

Profile your code. Find a Java profiler or use the poor man's profiler: run your code in the debugger, hit break a few times, see where it usually is when you break. Performance problems are often not where you think.

Merge sort is supposed to be faster than quick sort.
On worst case scenarios quick sort is O(n^2) while Merge sort is O(nlogn).

That's only in worst case.

1. Why is their implementation efficient even in the case of duplicates?

2. Why did I get StackOverFlow errors?

1. The magic is in this segment:

Code:

while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

It moves any value less than the pivot to one partition and any value larger than the pivot to the other partition. So any value equal to the pivot stays where they were. Whereas your code would move all values equal to the pivot to a single partition. I've never actually seen quick sort implemented their way. It's quite cool.


2. Essentially each duplicate value causes an extra recursive call. You ran out of memory for function stacks.

I can see how that makes sense. Leaving the equal values in both arrays lowers their concentration, which in turn lowers their probability of being picked, and even if they are picked, their effects are lowered due to low concentration. It's quite cool.

This would mean that for arrays of exact duplicates, this implementation would take just as long to run as mine does.

I can see how that makes sense. Leaving the equal values in both arrays lowers their concentration, which in turn lowers their probability of being picked, and even if they are picked, their effects are lowered due to low concentration. It's quite cool.

This would mean that for arrays of exact duplicates, this implementation would take just as long to run as mine does.

Er no? With an array of all duplicates, their implementation would still run as fast as merge sort whereas yours would be as slow as selection sort.

Er no? With an array of all duplicates, their implementation would still run as fast as merge sort whereas yours would be as slow as selection sort.

Let's see.

Theirs does:
- n comparisons
- n/2 swaps
- (50<>50) split
- The total work done outside of the recursion is O(n), and they have logn number of recursion layers.

Mine does:
- n comparisons
- no swaps
- (1<>n-1) split
- The total work done outside of the recursion is O(n) -albeit with a lower coefficient-, and I have n-1 number of recursion layers.

Seems to be the case. I should somehow circumvent this.

Ah, yes. Duplicate values would do it.

The other thing is, if you anticipate having to sort arrays with many duplicate values, you can also treat values equal to the pivot as a third "partition" and not recurse on it at all. This requires a bit more overhead but would yield O(n) time on an array of all duplicates, which is the best possible result.