### Implement the Thanos sorting algorithm

• vrwim

2 years ago

The sorting algorithm goes like this:

While the list is not sorted, snap half of all items (remove them from the list). Continue until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give different results based on implementation.

The item removal procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure. Your algorithm may decide to remove either the first half or the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not mentioned.

The input list can contain an arbitrary amount of items (within reason, let’s say up to 1000 items), not only perfectly divisible lists of 2^n items. You will have to either remove (n+1)/2 or (n-1)/2 items if the list is odd, either hardcoded or decided randomly during runtime. Decide for yourself: what would Thanos do if the universe contained an odd amount of living things?

The list is sorted if no item is smaller than any previous item. Duplicates may occur in the input, and may occur in the output.

Your program should take in an array of integers (via stdin or as parameters, either individual items or an array parameter), and return the sorted array (or print it to stdout).

Examples:

// A sorted list remains sorted[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]// A list with duplicates may keep duplicates in the result[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] ->  // Removing the first half[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half

[1, 2, 4, 3, 5] could give different results:

// Removing every second item:[1, 2, 4, 3, 5] -> [1, 4, 5]

or:

// Removing the first half of the list[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed

or:

// Removing the last half of the list[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed

or:

// Taking random items away until half (in this case (n-1)/2) of the items remain[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> Having a test case which actually requires multiple snaps for multiple different snapping algorithms would be very helpful. Don't we need to sort and eliminate half of the answers... Suggested test case: [9, 1, 1, 1, 1]. My own algorithm failed on this input

• 2 years ago

# Python 3, 3842 39 bytes

q=lambda t:t>sorted(t)and q(t[::2])or t

Try it online!

-3 bytes thanks to @JoKing and @Quuxplusone 40 bytes 39 bytes thanks to TFeld's observation that any permutation != sorted(t) must be > sorted(t).

• 2 years ago

# R, 41 bytes

x=scan();while(any(x-sort(x)))x=x[!0:1];x

Try it online! is.unsorted rather than any(...) would also be 41 bytes. This base method is 44 bytes as a recursive function, might be golfable: Try it online!

• 2 years ago

# Python 2, 39 bytes

f=lambda l:l>sorted(l)and f(l[::2])or l

Try it online!

• 2 years ago

# Brachylog (v2), 6 bytes

≤₁|ḍt↰

Try it online!

This is a function submission. Input from the left, output to the right, as usual. (The TIO link uses a command-line argument that automatically wraps the function into a full program, so that you can see it in action.)

## Explanation

≤₁|ḍt↰≤₁       Assert that {the input} is sorted {and output it}  |      Handler for exceptions (e.g. assertion failures):   ḍ     Split the list into two halves (as evenly as possible)    t    Take the last (i.e. second) half     ↰   Recurse {and output the result of the recursion}

## Bonus round

≤₁|⊇ᵇlᵍḍhtṛ↰

Try it online!

The snap's meant to be random, isn't it? Here's a version of the program that choses the surviving elements randomly (while ensuring that half survive at each round).

≤₁|⊇ᵇlᵍḍhtṛ↰≤₁            Assert that {the input} is sorted {and output it}  |           Handler for exceptions (e.g. assertion failures):   ⊇ᵇ         Find all subsets of the input (preserving order)     lᵍ       Group them by length       ḍht    Find the group with median length:         t      last element of        h       first       ḍ        half (split so that the first half is larger)          ṛ   Pick a random subset from that group           ↰  Recurse

This would be rather shorter if we could reorder the elements, but whyever would a sorting algorithm want to do that? One byte per infinity stone. @djechlin the infinity *byte* is why you must go for the head and especially the jaw.

• 2 years ago

# Perl 6, 30 bytes

$!={[<=]($_)??$_!!.[^*/2].&$!}

Try it online!

Recursive function that removes the second half of the list until the list is sorted.

### Explanation:

$!={ } # Assign the function to$!    [<=]($_)?? # If the input is sorted$_                  # Return the input                !!                # Else                  .[^*/2]         # Take the first half of the list (rounding up)                         .&\$!     # And apply the function again

• 2 years ago

# C# (Visual C# Interactive Compiler), 76 bytes

g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}

Try it online!

• 2 years ago

# Wolfram Language (Mathematica), 30 bytes

#//.x_/;[email protected]!=x:>x[[;;;;2]]&

Try it online!

@Doorknob saved 12 bytes Instead of taking the first half, you could save some bytes by taking every other element (x[[;;;;2]]). @Doorknob yes of course... thought there could be some savings by using OrderedQ, but couldn't make it work @GregMartin I used OrderedQ in my very first approach (see edits)

• 2 years ago

# Java 10, 106 97 bytes

L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}

-9 bytes thanks to @OlivierGrégoire.

Try it online.

Only leave the first halve of the list every iteration, and removes $$\\frac{n+1}{2}\$$ items if the list-size is odd.

Explanation:

L->{               // Method with Integer-list as both parameter and return-type  for(;;           //  Loop indefinitely:      L=L.subList(0,L.size()/2)){                   //    After every iteration: only leave halve the numbers in the list    int p=1<<31,   //   Previous integer, starting at -2147483648        f=1;       //   Flag-integer, starting at 1    for(int i:L)   //   Inner loop over the integer in the list:      f=p>(p=i)?   //    If a>b in a pair of integers a,b:         0         //     Set the flag to 0        :          //    Else (a<=b):         f;        //     Leave the flag the same    if(f>0)        //   If the flag is still 1 after the loop:      return L;}}  //    Return the list as result n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b @EmbodimentofIgnorance this happens because reduce is a terminal operation that closes the stream. You won't ever be able to call reduce twice on the same stream. You can create a new stream, though. 97 bytes @OlivierGrégoire That order looks so simple now that I see it.. Sometimes it takes a look from another angle to see the obvious others initially miss I guess. :) Thanks! No worries, it wasn't obvious: I worked to get there. I tested at least 10 versions before finding that one ;)

• 2 years ago

# JavaScript (ES6),  49  48 bytes

Saved 1 byte thanks to @tsh

Removes every 2nd element.

f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a

Try it online! p++&1 -> a^=1

• 2 years ago

# Ruby, 37 bytes

->r{r=r[0,r.size/2]while r.sort!=r;r}`

Try it online! 36 bytes recursively