101
\$\begingroup\$

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] -> [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] -> [4]
\$\endgroup\$
3
  • \$\begingroup\$ Having a test case which actually requires multiple snaps for multiple different snapping algorithms would be very helpful. \$\endgroup\$ Mar 26, 2019 at 11:01
  • 26
    \$\begingroup\$ Don't we need to sort and eliminate half of the answers... \$\endgroup\$
    – Sumner18
    Mar 26, 2019 at 14:32
  • 4
    \$\begingroup\$ Suggested test case: [9, 1, 1, 1, 1]. My own algorithm failed on this input \$\endgroup\$ Mar 26, 2019 at 21:03

46 Answers 46

1
2
1
\$\begingroup\$

Python 2, 51 bytes

a=input()
while a!=sorted(a):a=a[:len(a)/2]
print a

nice!

\$\endgroup\$
1
\$\begingroup\$

Pip -xp, 12 11 bytes

$<=a?afVUWa

Takes the list as a command-line argument in Pip list format, e.g. [1;2;4;3;5]. The -x flag makes sure this is treated as a list rather than a string, and the -p flag formats the output list in the same way. Try it here!

(Pip Classic doesn't support the -x flag, but here's a simulated version: Try it online!)

Explanation

A recursive solution:

$<=a?afVUWa
   a         ; First argument (the list)
$<=          ; Fold on <= (truthy if each element is <= the one after it)
    ?        ; If truthy, return:
     a       ;  The list unchanged
             ; Otherwise, return:
      f      ;  The main function
       V     ;  called with the following arglist:
        UWa  ;   Unweave the list into two sublists of every other element

For example, UW[1;2;4;3;5] returns [[1;4;5];[2;3]]. This list is passed as the arglist to the recursive call, as if we had called f with the arguments [1;4;5] and [2;3]. Since our function only uses its first argument, though, this is equivalent to simply recursing with an argument of [1;4;5].

\$\endgroup\$
0
\$\begingroup\$

Retina, 38 bytes

\d+
*
/(_+),(?!\1)/+`,_+(,?)
$1
_+
$.&

Try it online! Takes comma-separated numbers. Explanation:

\d+
*

Convert to unary.

/(_+),(?!\1)/+`

Repeat while the list is unsorted...

,_+(,?)
$1

... delete every even element.

_+
$.&

Convert to decimal.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 66 bytes

Snaps off the second half of the list each iteration (n/2+1 elements if the length is odd).

Try it online!

Takes input as a pointer to the start of an array of int followed by its length. Outputs by returning the new length of the array (sorts in-place).

t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}

Ungolfed version:

t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
  l: // jump label, will be goto'ed after each snap
  for(i = 0; i < n - 1; ) { // go through the whole array …
    if(a[i] > a[++i]) { // … if two elements are in the wrong order …
      n /= 2; // … snap off the second half …
      goto l; // … and start over
    }
  }
  a = n; // implicitly return the new length
}
\$\endgroup\$
1
  • \$\begingroup\$ Suggest ~i+n instead of i<n-1 \$\endgroup\$
    – ceilingcat
    Apr 12, 2019 at 17:19
0
\$\begingroup\$

Clojure, 65 bytes

(defn t[l](if(apply <= l)l(recur(take(/(count l)2)(shuffle l)))))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 45? \$\endgroup\$
    – ASCII-only
    Mar 28, 2019 at 6:36
  • \$\begingroup\$ 43? 42? \$\endgroup\$
    – ASCII-only
    Mar 28, 2019 at 6:42
0
\$\begingroup\$

MATLAB, 57 bytes

Callable as f(a), where a=[1,2,3,4,5]

f=@(x)eval('while~isequal(sort(x),x);x=x(1:end/2);end;x')

Example of usage:

>> a = [1, 2, 4, 3, 5];
>> f(a)

a =
     1     2
\$\endgroup\$
0
\$\begingroup\$

Zsh, 51 bytes

56 (+5) to call the function, 47 (-4) if not a function, but saved as an executable with a proper #! header (replace the recursive f call with $0).

f(){[ "$*" = "${${(n)@}[*]}" ]&&<<<$@||f $@[0,#/2]}

Try it online!

There is no "is-sorted" builtin in zsh, but there are some "sort-array" builtins. We use the parameter expansion flag n, but o or i would also work. We then have to use [*] and quote to induce joining. This is shorter than alternatives (like zipping them together and comparing pairwise).

\$\endgroup\$
0
\$\begingroup\$

C++ 17 , 589 bytes

I used recursion to solve it. Submitted this solution in codeforces and got accepted. Btw, I still can't stop laughing! I mean seriously, Thanos sort!

#include <bits/stdc++.h> 
using namespace std;int n, *a; int f(int start123, int end123){int start, end;start = start123; end = end123;if(start == end){    return 1; }int ret=0, temp=0;bool flag  = true;for(int i=start; i<end; i++){ if(a[i]<=a[i+1]){   ret++; }else{    flag=false; break; } }int mid = (start+end)>>1; if(flag){    ret=ret+1; }else{ int a,b; a =  f(start, mid);b = f(mid+1, end);ret = max( a, b );}return ret;}int main(int argc, char const *argv[]){    cin>>n;a = new int[n+10];for(int i=1; i<=n; i++){cin>>a[i];}int ans = f(1,n);cout<<ans<<"\n";if(!a)delete[] a;return 0;}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Hi and welcome to PPCG, the criterion of this question is code-golf, that means we are trying to solve the problem in as few bytes as possible. Typically people will post the number of bytes for their answer along with the answer (so for yours: 1120 bytes), your aim should be to reduce this! May I recommend starting by removing all unneccesary whitespace, naming your variables with single characters and looking at tips for golfing in c++ \$\endgroup\$ Apr 2, 2019 at 14:35
  • \$\begingroup\$ Thank you Expired Data. I'll try to do better next time \$\endgroup\$ Apr 3, 2019 at 6:26
0
\$\begingroup\$

F# (.NET Core), 67 61 bytes

let rec t l=if l=(List.sort l)then l else t l.[0..l.Length/2]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 32 bytes

{($_,*[^*/2]...{[<=] @$_})[*-1]}

-2 bytes thanks to Jo King

Try it online!

\$\endgroup\$
0
0
\$\begingroup\$

Perl 5 -a, 50 bytes

@b=sort{$a-$b}@F while"@b"ne"@F"&&($#F/=2);say"@F"

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Rust (2018 edition), 79 78 bytes

|v:&mut Vec<_>|while{let q=&mut v.clone();q.sort();q<v}{v.resize(v.len()/2,0)}

Try it online!

This will be golfable if slice::is_sorted gets stabilized, but right now the required feature flag offsets all gains.

\$\endgroup\$
3
  • \$\begingroup\$ feature flags are free though :P - they just count as a separate language \$\endgroup\$
    – ASCII-only
    May 6, 2019 at 14:02
  • \$\begingroup\$ @ASCII-only for Rust, feature flags are not commandline arguments, but special syntax in the code itself. \$\endgroup\$
    – NieDzejkob
    May 6, 2019 at 19:36
  • \$\begingroup\$ Huh, no commandline option (like C# and Haskell) huh \$\endgroup\$
    – ASCII-only
    May 7, 2019 at 1:09
0
\$\begingroup\$

TI-Basic (TI-84), 29 30 36 bytes

Ans->L₁
While 1<dim(L₁
If 0≤min(ΔList(L₁:Then
L₁
Return:End
iPart(.5dim(L₁->dim(L₁
End

Input and output are through Ans.

\$\endgroup\$
1
  • \$\begingroup\$ L1 is not legal input; you need to either use Ans or write Input L1. Same for output, either Ans or display. \$\endgroup\$
    – lirtosiast
    Jun 6, 2019 at 6:50
0
\$\begingroup\$

PHP, 86 bytes

function t($a){for(;$n=$a[+$i++];$l=$n)$f|=$n<$l;return$f?t(array_slice($a,$i/2)):$a;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 3, 60 bytes

a=list(input())
while a!=sorted(a):a=a[0:len(a)//2]
print(a)

Try it online!

If it has to be a list:

a=[1,34,2,42,3,4,5,23,4,12,34,53,65]
while a!=sorted(a):a=a[0:len(a)//2]
print(a)

this one even has a self scrambling thingy!

import random
a=list(input())
random.shuffle(a)
while a!=sorted(a):a=a[0:len(a)//2]
print(a)

Explanation:

a=list(input())       #ask for a string(that will be converted to a list)
while a!=sorted(a):   #while the actual sorted list *isn't* sorted,
    a=a[0:len(a)//2]  #it now equals the first half of it.
print(a)              #print it out!
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to the site and nice first answer! I've edited it slightly so that other users can run and test your code, and that the formatting's fixed. One thing to note: list(input()) doesn't give you an actual list, it just converts the input string into a list (hence why the TIO link outputs ['[']. Changing it to eval(input()) works for no extra bytes: Try it online! \$\endgroup\$ Jan 3, 2021 at 23:04
  • \$\begingroup\$ @cairdcoinheringaahing thanks! I doubt that this will win, but it was fun! \$\endgroup\$
    – pyton
    Jan 3, 2021 at 23:56
0
\$\begingroup\$

Factor, 50 bytes

[ [ dup [ <= ] monotonic? ] [ halves nip ] until ]

Try it online!

Removes the first half of the list, where the first half is shorter when there's an odd number of elements.

\$\endgroup\$
1
2

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.