19

Design an efficient algorithm to sort 5 distinct - very large - keys less than 8 comparisons in the worst case. You can't use radix sort.

Sinan Ünür
  • 116,958
  • 15
  • 196
  • 339
DarthVader
  • 52,984
  • 76
  • 209
  • 300
  • 8
    If this is homework, and it sounds like it, please tell us what you have done and where you are stuck. – dmckee --- ex-moderator kitten Oct 07 '09 at 23:22
  • it s not a homework question. Yes i m taking algorithm class but it s just a question i m curious. I asked a similar question before I was curious if there s a better worst case. – DarthVader Oct 07 '09 at 23:23
  • I find the median in 6 comparisons and i did two more comparisons, which is 8 again. I m curious if there s a better solution to this. – DarthVader Oct 07 '09 at 23:24
  • I m sure 8 is the worst case, using merge sort. – DarthVader Oct 07 '09 at 23:28
  • quicksort is also 8. Cant use insertion sort, selection sort, heapsort, bubble sort, and the linear time sorting algorithms, such as radix sort. – DarthVader Oct 07 '09 at 23:30
  • The information-theoretical minimum is 7 comparisons (you have 2^7=128 possible outputs from asking 7 boolean questions, and there are 120 permutations of 5 numbers). That doesn't mean it's possible though. – Yuliy Oct 07 '09 at 23:46
  • There is an answer to it, which i dont know that s why i asked :) – DarthVader Oct 07 '09 at 23:51
  • This is weird, I could swear that we had this exact same question 2-3 weeks ago... – RBarryYoung Oct 08 '09 at 00:00
  • :) That was a median question. Finding the median of 5 keys which can be done with 6 comparisons, and which there was no correct answers. – DarthVader Oct 08 '09 at 00:06
  • "very large" means no hash-like sort? If not, you can sort this keys putting each one into a corresponding location of an array, then reading it from the beginning – Lopoc Oct 08 '09 at 00:40
  • :) very large means, you cant use linear time sorting, like counting sort, radix sort, bucket sort. – DarthVader Oct 08 '09 at 00:52
  • If you cannot sort, you can unroll the comparisons giving essentially all 120 possibilities in a LOT of nested ifs. – Thorbjørn Ravn Andersen Jun 29 '10 at 14:19
  • The best algorithm known was first published by H.B. Demuth in 1956, and can be found in chapter 5.3.1 of volume 3 of *The Art of Computer Programming*, by Donald Knuth. – Davislor Jun 10 '23 at 04:50

13 Answers13

37

Compare A to B and C to D. WLOG, suppose A>B and C>D. Compare A to C. WLOG, suppose A>C. Sort E into A-C-D. This can be done with two comparisons. Sort B into {E,C,D}. This can be done with two comparisons, for a total of seven.

Beta
  • 96,650
  • 16
  • 149
  • 150
  • (a,b=> 1), (c,d=>1), (a,c=>1),(e, (a,c,d) => can be 3), (b, (e,c,d)=> can also be 3) Am i missing a point? – DarthVader Oct 08 '09 at 00:30
  • 1
    @unknown, to sort E into A-C-D, first compare E to C. Then if E>C compare E to A, otherwise compare E to D. Sorting B into {E,C,D} is the same. – Beta Oct 08 '09 at 00:44
  • 3
    This is known as Ford-Johnson algorithm aka merge insertion. This is the [link](https://www.jstor.org/stable/2308750?seq=1#page_scan_tab_contents) for the related paper published in 1959. If you have trouble accessing the link, please search for "The tournament problem". – D. Jones Nov 08 '16 at 10:36
22

This is pseudocode based on Beta's answer. Might have some mistakes as I did this in a hurry.

if (A > B)
    swap A, B
if (C > D)
    swap C, D
if (A > C)
    swap A, C
    swap B, D  # Thanks Deqing!

if (E > C)
    if (E > D)  # A C D E
        if (B > D)
            if (B > E)
                return (A, C, D, E, B)
            else
                return (A, C, D, B, E)
         else
            if (B < C)
                return (A, B, C, D, E)
            else
                return (A, C, B, D, E)

    else  # A C E D
        if (B > E)
            if (B > D)
                return (A, C, E, D, B)
            else
                return (A, C, E, B, D)
         else
            if (B < C)
                return (A, B, C, E, D)
            else
                return (A, C, B, E, D)
else
    if (E < A)  # E A C D
        if (B > C)
            if (B > D)
                return (E, A, C, D, B)
            else
                return (E, A, C, B, D)
         else
             return (E, A, B, C, D)

    else  # A E C D
        if (B > C)
            if (B > D)
                return (A, E, C, D, B)
            else
                return (A, E, C, B, D)
         else
            if (B < E)
                return (A, B, E, C, D)
            else
                return (A, E, B, C, D)
mic
  • 1,190
  • 1
  • 17
  • 29
Artelius
  • 48,337
  • 13
  • 89
  • 105
  • 1
    i wish i could pick two right answers :) Thanks for the effort though. Appreciated. – DarthVader Oct 08 '09 at 01:27
  • I don't understand, how the first 3 comparison gets `A-C-D`? E.g. for ABCD as 9,10,1,2 the first 3 comparison get A,C,D as 1-9-2, not we expected. I guess the 3rd comparison should be `swap A, C; swap B, D;` – Deqing Jun 16 '14 at 04:03
  • Well spotted! If (A > C) then A may also be greater than D, but we can't be sure without a comparison. But swapping (A,B) with (C,D) solves the problem; afterwards we know A>B, A>C, and C>D. Edited my answer. – Artelius Jul 15 '14 at 02:47
  • this might fail for 1 1 2 2 1 – Ray Tayek Feb 26 '15 at 05:43
  • 1
    I have tested it and it works correctly for 1 1 2 2 1, returning 1 1 1 2 2. – Artelius Mar 01 '15 at 23:56
  • Yeah rewrote this into C++ and it worked fine tested it in Debug/Release x64/x86 and yeah performed solid. I had a more simplified version that was 7 or 8 ifs but did less swapping of values but both come to about same speed in release mode with this being faster in x86 and slower in x64 for me but by so little it doesn't matter given i was doing 70mil sorts. Here's your pseudo code in C++ https://pastebin.com/raw/BqZQsJPN pastebins formatting made it a little weird btw. – Jeremy Trifilo Aug 02 '23 at 20:55
8

It has to be 7 or more comparisons.

There are 120 (5 factorial) ways for 5 objects to be arranged. An algorithm using 6 comparisons can only tell apart 2^6 = 64 different initial arrangements, so algorithms using 6 or less comparisons cannot sort all possible inputs.

There may be a way to sort using only 7 comparisons. If you only want to sort 5 elements, such an algorithm could be found (or proved not to exist) by brute force.

Artelius
  • 48,337
  • 13
  • 89
  • 105
7

Five items can be sorted with at most seven comparisons, because log2(5!) = 6.9. I suggest checking if any standard sorting algorithm achieves this number. If not, it should be quite easy to hard-code a comparison sequence because of the low number of required comparisons.

I suggest using this algorithm to find the comparison sequence:

  1. Create a list with all 120 permutations of [1..5].
  2. Try all (initially 5 * 4 = 20) possible comparisons and choose the one which splits the list into two most equally sized lists.
  3. Apply this split, then:
    • if the two splits contain only one element, terminate
    • otherwise, go to 2.

I wrote a small program to do this, and here is the result:

Comparison 1: 0-1 [60|60] // First comparison item 0 with item 1, splits case 60/60
Comparison 2: 2-3 [30|30] // Second comparison for the first half of the first comparison
Comparison 3: 0-2 [15|15] // Third comparison for the first half of the second comparison for the first half of first comparison
Comparison 4: 2-4 [8|7]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 3-4 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-3 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 3: 0-3 [15|15] // Third comparison for the second half of the second comparison for the first half of first comparison
Comparison 4: 3-4 [8|7]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 2-4 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-2 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 2: 2-3 [30|30] // Second comparison for the second half of the first comparison
Comparison 3: 0-3 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-2 [3|4]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 2-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 4: 3-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 3: 0-2 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-3 [3|4]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 3-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 4: 2-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]

But now the question is how to implement this in an efficient way. Maybe one could use a look-up table to store the comparison sequence. I am also not sure how to derive the ordered output from this comparison sequence in an efficient way.

Sorting the result from above by the comparison reveals an obvious structure for the first comparisons, but it becomes harder with an increasing amount of comparisons. All blocks are symmetric around the middle, indicated by -----.

Comparison 1: 0-1 [60|60]

Comparison 2: 2-3 [30|30]
Comparison 2: 2-3 [30|30]

Comparison 3: 0-2 [15|15]
Comparison 3: 0-3 [15|15]
-----
Comparison 3: 0-3 [15|15]
Comparison 3: 0-2 [15|15]

Comparison 4: 2-4 [8|7]
Comparison 4: 0-4 [8|7]
Comparison 4: 3-4 [8|7]
Comparison 4: 0-4 [8|7]
-----
Comparison 4: 0-4 [7|8]
Comparison 4: 3-4 [7|8]
Comparison 4: 0-4 [7|8]
Comparison 4: 2-4 [7|8]

Comparison 5: 3-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-3 [4|3]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-2 [4|3]
-----
Comparison 5: 0-2 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-3 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 3-4 [4|4]

Comparison 6: 1-3 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [1|2]
-----
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 2-4 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]

Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
-----
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
Daniel Brückner
  • 59,031
  • 16
  • 99
  • 143
  • Nice answer, I know that. Using comparison tree. There are 5! possible answer which is log120. But which algorithm to find this route? – DarthVader Oct 07 '09 at 23:42
4

FWIW, here's a compact and easy to follow Python version with tests to make sure it works:

def sort5(a, b, c, d, e):
    'Sort 5 values with 7 Comparisons'
    if a < b:      a, b = b, a
    if c < d:      c, d = d, c
    if a < c:      a, b, c, d = c, d, a, b
    if e < c:
        if e < d:  pass
        else:      d, e = e, d
    else:
        if e < a:  c, d, e = e, c, d
        else:      a, c, d, e = e, a, c, d
    if b < d:
        if b < e:  return b, e, d, c, a
        else:      return e, b, d, c, a
    else:
        if b < c:  return e, d, b, c, a
        else:      return e, d, c, b, a

if __name__ == '__main__':
    from itertools import permutations

    assert all(list(sort5(*p)) == sorted(p) for p in permutations(range(5)))
Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
3

According to Wikipedia:

Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known."

Presumably this means there is no known tractable (efficient) algorithm for determining an exactly optimal comparison sort.

Managu
  • 8,849
  • 2
  • 30
  • 36
  • 1
    He doesn't need a formula, just the answer for n=5. The quote says that it's a hard problem even for small n, but it doesn't mean that small. There's a hard lower limit of 7 on the worst case, and a known solution that gets it in 7 at worst. Who cares how hard it is for n=6? – Steve Jessop Oct 08 '09 at 10:37
3

Sorting networks have a restricted structure, so don't answer the original question; but they're fun.
List of Sorting Networks generates nice diagrams or lists of SWAPs for up to 32 inputs. For 5, it gives

There are 9 comparators in this network, grouped into 6 parallel operations.  
[[0,1],[3,4]]  
[[2,4]]  
[[2,3],[1,4]]  
[[0,3]]  
[[0,2],[1,3]]  
[[1,2]]
denis
  • 21,378
  • 10
  • 65
  • 88
2

I have written a C implementation of the solution to this problem which can be found here: Sorting 5 elements using 7 comparisons

My code is well commented with an explanation of why it is working.

as2d3
  • 802
  • 2
  • 10
  • 27
1

Sample sequence of operations, using mergesort (the merge function below will merge two sorted sublists into a single sorted combined list):

elements[1..2] <- merge(elements[1..1], elements[2..2]) # 1 comparison
elements[3..4] <- merge(elements[3..3], elements[4..4]) # 1 comparison
elements[3..5] <- merge(elements[3..4], elements[5..5]) # 1-2 comparisons
elements[1..5] <- merge(elements[1..2], elements[3..5]) # 2-4 comparisons
yfeldblum
  • 65,165
  • 12
  • 129
  • 169
1

A B C D E

A
| C D E     - 1 Comparison
B

A C
| | E       - 1 Comparison
B D

  A
 / \
B   C   E   - 1 Comparison
     \
      D

E needs 3 comparisons. It should be compared to A, C, D

Try A-C-D-E in that order.

Overall there will be nine comparisons -- not very performant.

George Stocker
  • 57,289
  • 29
  • 176
  • 237
DarthVader
  • 52,984
  • 76
  • 209
  • 300
0

Others have stated that there are 5! = 120 arrangements (permutations) to handle, so you need 7 comparisons. To identify the permutation, in principle, you can construct a big nested if statement 7 comparisons deep. Having identified the permutation, a precalculated swap/rotation sequence can be applied.

The first problem is that the choice of second comparison depends on the result of the first comparison and so on. The trick at each stage is to choose a good comparison to divide the current set of possible permutations into two equal subsets. Simplest approach - evaluate the split that each comparison would achieve until you find a suitably balanced one. Exit early if you find a perfect balance, but be aware that perfect balance won't always be possible as we don't have exactly 2^7=128 permutations - in some (I assume 8) cases, we only need six comparisons.

The second problem is designing the swap/rotation sequences for each of the 120 possible permutations, and that's probably a dynamic programming thing. Probably requires recursive search of an if-I-do-this, the next result is that, then recurse "game tree", and you should really cache intermediate results IOW. Too tired to figure out the details ATM, sorry.

You might put all the steps into a digraph that fans out (identifying the permutation), then fans back in (applying each reordering step). Then, probably run it through a digraph minimisation algorithm.

Wrap this up in a code generator and you're done - your own algorithmically near-perfect 5 item sorter. The digraph stuff kind of implies gotos in the generated code (esp. if you minimise), but people tend to turn a blind eye to that in generated code.

Of course all this is a bit brute force, but why bother with elegance and efficiency - odds are you'll only run the working generator once anyway, and the problem size is small enough to be achievable (though probably not if you do independent naive "game tree" searches for each permutation).

0

For sorting networks, it is not possible to have less than 9 comparisons to sort 5 items when the input is not known. The lower bound has been proven for sorting networks up to 10. See https://en.wikipedia.org/wiki/Sorting_network.

Correctness of sorting networks could be verified by the Zero-one principle as mentioned in The Art of Computer Programming, Vol 3 by Knuth. That is, if a sorting network can correctly sort all permutations of 0s and 1s, then it is a correct sorting network. None of the algorithms mentioned on this post passed the Zero-one test.

In addition, the lower bound says that comparison based sorts cannot have less than ceil(log(n!)) comparators to correctly sort, however, it does not mean that this is achievable.

OrientalSiru
  • 63
  • 5
0

Here is C++ implementation which sorts 5 elements in <= 7 comparisons. Was able to find 8 cases which can be sorted in 6 comparisons. That makes sense if we imagine full binary tree with 120 leaf nodes, there will be 112 nodes at level 7 and 8 leaf nodes at level 6. Here is the full code that is tested to work for all possible permutations.

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <numeric>

using namespace std;

ostream& operator << ( ostream& os, vector<int> v )
{
    cout << "[ ";
    for ( auto x: v ) cout << x << ' ';
    cout << "]";
    return os;
}

class Comp {
    int count;
public:
    Comp(): count{0}{}
    bool isLess( vector<int> v, int i, int j ) {
        count++;
        //cout << v << "Comparison#" << count << ": " << i << ", " << j << endl;
        return v[ i ] < v[ j ];
    }
    int getCount() { return count; }
};


int mySort( vector<int> &v )
{
    Comp c;
    if ( c.isLess( v, 1, 0 ) ) {
        swap( v[ 0 ], v[ 1 ] );
    }
    if ( c.isLess( v, 3, 2 ) ) {
        swap( v[ 2 ], v[ 3 ] );
    }
    // By now (0, 1) (2, 3) (4)
    if ( c.isLess( v, 0, 2 ) ) {
        // ( 0, 2, 3 ) (1)
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 2 ], v[ 3 ] );
    } else {
        // ( 2, 0, 1 ) ( 3 )
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 0 ], v[ 1 ] );
    }
    // By now sorted order ( 0, 1, 2 ) ( 3 ) ( 4 ) and know that 3 > 0
    if ( c.isLess( v, 4, 1 ) ) {
        if ( c.isLess( v, 4, 0 ) ) {
            // ( 4, 0, 1, 2 ) ( 3 ) ( ... )
            v.insert( v.begin(), v[4] );
            // By now ( 0, 1, 2, 3 ) ( 4 ) ( ... ) and know that 4 > 1
            if ( c.isLess( v, 4, 2 ) ) {
                // ( 0, 1, 4, 2, 3 ) ( ... )
                v.insert( v.begin() + 2, v[4] );
            } else {
                if ( c.isLess( v, 4, 3 ) ) {
                    // ( 0, 1, 2, 4, 3 ) ( ... )
                    v.insert( v.begin() + 3, v[4] );
                } else {
                    // ( 0, 1, 2, 3, 4 ) ( ... )
                    v.insert( v.begin() + 4, v[4] );
                }
            }
            // ( 1 2 3 4 5 ) and trim the rest
            v.erase( v.begin()+5, v.end() );
            return c.getCount(); /////////// <--- Special case we could been done in 6 comparisons
        } else {
            // ( 0, 4, 1, 2 ) ( 3 ) ( ... ) 
            v.insert( v.begin() + 1, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 2 ) ) {
            // ( 0, 1, 4, 2 ) ( 3 ) ( ... )
            v.insert( v.begin() + 2, v[4] );
        } else {
            // ( 0, 1, 2, 4 ) ( 3 ) ( ... )
            v.insert( v.begin() + 3, v[4] );
        }
    }
    // By now ( 0, 1, 2, 3 ) ( 4 )( ... ): with 4 > 0
    if ( c.isLess( v, 4, 2 ) ) {
        if ( c.isLess( v, 4, 1 ) ) {
            // ( 0, 4, 1, 2, 3 )( ... )
            v.insert( v.begin() + 1, v[4] );
        } else {
            // ( 0, 1, 4, 2, 3 )( ... )
            v.insert( v.begin() + 2, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 3 ) ) {
            // ( 0, 1, 2, 4, 3 )( ... )
            v.insert( v.begin() + 3, v[4] );
        } else {
            // ( 0, 1, 2, 3, 4 )( ... )
            v.insert( v.begin() + 4, v[4] );
        }
    }
    v.erase( v.begin()+5, v.end() );
    return c.getCount();
}

#define TEST_ALL
//#define TEST_ONE

int main()
{
#ifdef TEST_ALL
    vector<int> v1(5);
    iota( v1.begin(), v1.end(), 1 );
    do {
        vector<int> v2 = v1, v3 = v1;
        int count = mySort( v2 );
        if ( count == 6 )
            cout << v3 << " => " << v2 << " #" << count << endl;
    } while( next_permutation( v1.begin(), v1.end() ) );
#endif

#ifdef TEST_ONE
    vector<int> v{ 1, 2, 3, 1, 2};
    mySort( v );
    cout << v << endl;
#endif
}
vamsi
  • 29
  • 3