Add in-place QuickSort and use it in SortedIterationKTypeVTypeHashMap. #31
Conversation
| final int[] order; | ||
| switch (algo) { | ||
| case MERGESORT: | ||
| order = IndirectSort.mergesort(0, x.length, Integer::compare); |
There was a problem hiding this comment.
There was a bug here where the comparator used was not indirect. I fixed that in the new SortTest.Algorithm.INDIRECT_MERGESORT.
| @@ -34,7 +34,8 @@ private IndirectSort() { | |||
| * Returns the order of elements between indices <code>start</code> and <code>length</code>, as | |||
| * indicated by the given <code>comparator</code>. | |||
| * | |||
| * <p>This routine uses merge sort. It is guaranteed to be stable. | |||
| * <p>This routine uses merge sort. It is guaranteed to be stable. It creates a new indices array, | |||
| * and clones it while sorting. | |||
| */ | |||
| public static int[] mergesort(int start, int length, IntBinaryOperator comparator) { | |||
| final int[] src = createOrderArray(start, length); | |||
There was a problem hiding this comment.
Wait... was it like this before? Becuase that version of mergesort that accepts an external array shouldn't clone it - it doesn't make sense? And right now the mergesort(int, int, comparator) creates a new array just so that it can be cloned in a call to sort(int[], comparator)...
There was a problem hiding this comment.
It was like this before. AFAIK merge sort requires a source and a destination array. Its memory requirement is O(n).
| /* | ||
| * HPPC | ||
| * | ||
| * Copyright (C) 2010-2020 Carrot Search s.c. |
There was a problem hiding this comment.
We should update the template (2020)....
There was a problem hiding this comment.
I tried 2021 but spotless corrected it :)
There was a problem hiding this comment.
I know. It's the template under gradle/validation/spotless/license-header.txt. Don't worry about it.
|
What do you think of this proposal Dawid? |
|
Uh, sorry - I thought this was silent consensus - this looks good to me! |
|
Thanks! I'll try to remember this silent consensus next time. |
|
...or just ping me. :) |
In the case of SortedIterationKTypeVTypeHashMap, we want to sort the key set of a delegate hash map. We know there are no duplicate keys, and they are randomly distributed, and we don't need to have a stable sort. Hence it is a good case to use an in-place Quick sort instead of IndirectSort merge sort (which needs a copy of the source array).
So with this change, SortedIterationKTypeVTypeHashMap sorts with in-place quick sort. It is faster and does not require a clone of the indices array anymore.
This new QuickSort implementation, with 3-way partitioning, works on a provided comparator and also a provided swapper.
I extracted the sort certification code from IndirectSortTest to move it to a new SortTest, which now tests both IndirectSort and QuickSort.