Implement the Thanos sorting algorithm
$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]
code-golf sorting
asked 18 hours ago
vrwimvrwim
96511016
$endgroup$
|
show 10 more comments
$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]
code-golf sorting
asked 18 hours ago
vrwimvrwim
96511016
$endgroup$
2
$begingroup$
What direction does the list need to be sorted in for termination? Ascending, descending, either or at the choice of the algorithm?
$endgroup$
– Expired Data
18 hours ago
4
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
14 hours ago
4
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
14 hours ago
4
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
14 hours ago
3
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
10 hours ago
|
show 10 more comments
$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]
code-golf sorting
asked 18 hours ago
vrwimvrwim
96511016
$endgroup$
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]
code-golf sorting
code-golf sorting
asked 18 hours ago
vrwimvrwim
96511016
asked 18 hours ago
vrwimvrwim
96511016
edited 17 hours ago
vrwim
asked 18 hours ago
vrwimvrwim
96511016
asked 18 hours ago
vrwimvrwim
96511016
asked 18 hours ago
vrwimvrwim
96511016
96511016
2
$begingroup$
What direction does the list need to be sorted in for termination? Ascending, descending, either or at the choice of the algorithm?
$endgroup$
– Expired Data
18 hours ago
4
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
14 hours ago
4
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
14 hours ago
4
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
14 hours ago
3
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
10 hours ago
|
show 10 more comments
2
$begingroup$
What direction does the list need to be sorted in for termination? Ascending, descending, either or at the choice of the algorithm?
$endgroup$
– Expired Data
18 hours ago
4
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
14 hours ago
4
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
14 hours ago
4
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
14 hours ago
3
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
10 hours ago
2
2
$begingroup$
What direction does the list need to be sorted in for termination? Ascending, descending, either or at the choice of the algorithm?
$endgroup$
– Expired Data
18 hours ago
$begingroup$
What direction does the list need to be sorted in for termination? Ascending, descending, either or at the choice of the algorithm?
$endgroup$
– Expired Data
18 hours ago
4
4
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
14 hours ago
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
14 hours ago
4
4
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
14 hours ago
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
14 hours ago
4
4
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
14 hours ago
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
14 hours ago
3
3
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
10 hours ago
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
10 hours ago
|
show 10 more comments
19 Answers
19
active
oldest
votes
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
$endgroup$
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered 15 hours ago
TFeldTFeld
16.1k21449
$endgroup$
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered 18 hours ago
Sara JSara J
36519
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
13 hours ago
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
answered 14 hours ago
ArnauldArnauld
79.8k797330
$endgroup$
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered 8 hours ago
G BG B
8,1161429
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
add a comment |
$begingroup$
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
answered 16 hours ago
Jo KingJo King
25.6k362129
$endgroup$
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if it's equal.
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
16 hours ago
add a comment |
$begingroup$
Java 10, 106 bytes
L->{for(int M=1<<31,p=M,f;;L=L.subList(0,L.size()/2),p=M){f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
Try it online.
Or alternatively:
L->{for(int M=1<<31,p=M;;L=L.subList(0,L.size()/2),p=M){var f=1>0;for(int i:L)f&=p<=(p=i);if(f)return L;}}
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(int M=1<<31, // Minimum integer, set to -2147483648
p=M, // Previous integer, starting at this minimum
f // Flag-integer, starting uninitialized
; // Loop indefinitely:
; // After every iteration:
L=L.subList(0,L.size()/2),
// Only leave halve the numbers in the list
p=M){ // And reset the previous-integer to the minimum
f=1; // Set the flag-integer to 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
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
7 hours ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 42 bytes
#//.x_/;Sort@x!=x:>x[[;;⌊Tr[1^x]/2⌋]]&
Try it online!
answered 14 hours ago
J42161217J42161217
13.5k21252
$endgroup$
add a comment |
$begingroup$
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!
answered 17 hours ago
Expired DataExpired Data
3186
$endgroup$
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
$endgroup$
add a comment |
$begingroup$
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?
$endgroup$
1
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered 12 hours ago
TauTau
656211
$endgroup$
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered 16 hours ago
Expired DataExpired Data
3186
$endgroup$
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered 9 hours ago
GiuseppeGiuseppe
17.1k31152
$endgroup$
add a comment |
$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.
answered 14 hours ago
NeilNeil
82.1k745178
$endgroup$
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered 14 hours ago
ShaggyShaggy
19k21667
$endgroup$
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f182221%2fimplement-the-thanos-sorting-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
19 Answers
19
active
oldest
votes
19 Answers
19
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
$endgroup$
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
add a comment |
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
$endgroup$
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
add a comment |
$begingroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
$endgroup$
R, 41 bytes
x=scan();while(any(x-sort(x)))x=x[!0:1];x
Try it online!
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
answered 17 hours ago
Kirill L.Kirill L.
5,8431526
5,8431526
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
add a comment |
2
$begingroup$
is.unsortedrather thanany(...)would also be 41 bytes.
$endgroup$
– Giuseppe
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
2
2
$begingroup$
is.unsorted rather than any(...) would also be 41 bytes.$endgroup$
– Giuseppe
15 hours ago
$begingroup$
is.unsorted rather than any(...) would also be 41 bytes.$endgroup$
– Giuseppe
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
$begingroup$
This base method is 44 bytes as a recursive function, might be golfable: Try it online!
$endgroup$
– CriminallyVulgar
15 hours ago
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered 15 hours ago
TFeldTFeld
16.1k21449
$endgroup$
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered 15 hours ago
TFeldTFeld
16.1k21449
$endgroup$
add a comment |
$begingroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered 15 hours ago
TFeldTFeld
16.1k21449
$endgroup$
Python 2, 39 bytes
f=lambda l:l>sorted(l)and f(l[::2])or l
Try it online!
answered 15 hours ago
TFeldTFeld
16.1k21449
answered 15 hours ago
TFeldTFeld
16.1k21449
answered 15 hours ago
TFeldTFeld
16.1k21449
answered 15 hours ago
TFeldTFeld
16.1k21449
16.1k21449
add a comment |
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered 18 hours ago
Sara JSara J
36519
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
13 hours ago
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered 18 hours ago
Sara JSara J
36519
$endgroup$
2
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
13 hours ago
add a comment |
$begingroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered 18 hours ago
Sara JSara J
36519
$endgroup$
Python 3, 38 42 39 bytes
q=lambda t:t>sorted(t)and q(t[::2])or t
Try it online!
-3 bytes thanks to @JoKing and @Quuxplusone
answered 18 hours ago
Sara JSara J
36519
edited 10 hours ago
answered 18 hours ago
Sara JSara J
36519
answered 18 hours ago
Sara JSara J
36519
answered 18 hours ago
Sara JSara J
36519
36519
2
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
13 hours ago
add a comment |
2
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation!= sorted(t)must be> sorted(t).
$endgroup$
– Quuxplusone
13 hours ago
2
2
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
40 bytes
$endgroup$
– Jo King
16 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation
!= sorted(t) must be > sorted(t).$endgroup$
– Quuxplusone
13 hours ago
$begingroup$
39 bytes thanks to TFeld's observation that any permutation
!= sorted(t) must be > sorted(t).$endgroup$
– Quuxplusone
13 hours ago
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
answered 14 hours ago
ArnauldArnauld
79.8k797330
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
answered 14 hours ago
ArnauldArnauld
79.8k797330
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
answered 14 hours ago
ArnauldArnauld
79.8k797330
$endgroup$
JavaScript (ES6), 49 bytes
Removes every 2nd element, starting with either the first or the second one depending on the parity of the first unsorted element.
f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>p++&1)):a
Try it online!
answered 14 hours ago
ArnauldArnauld
79.8k797330
edited 14 hours ago
answered 14 hours ago
ArnauldArnauld
79.8k797330
answered 14 hours ago
ArnauldArnauld
79.8k797330
answered 14 hours ago
ArnauldArnauld
79.8k797330
79.8k797330
add a comment |
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered 8 hours ago
G BG B
8,1161429
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered 8 hours ago
G BG B
8,1161429
$endgroup$
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
add a comment |
$begingroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered 8 hours ago
G BG B
8,1161429
$endgroup$
Ruby, 37 bytes
->r{r=r[0,r.size/2]while r.sort!=r;r}
Try it online!
answered 8 hours ago
G BG B
8,1161429
answered 8 hours ago
G BG B
8,1161429
answered 8 hours ago
G BG B
8,1161429
answered 8 hours ago
G BG B
8,1161429
8,1161429
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
add a comment |
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
$begingroup$
36 bytes recursively
$endgroup$
– Kirill L.
8 hours ago
add a comment |
$begingroup$
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
answered 16 hours ago
Jo KingJo King
25.6k362129
$endgroup$
add a comment |
$begingroup$
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
answered 16 hours ago
Jo KingJo King
25.6k362129
$endgroup$
add a comment |
$begingroup$
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
answered 16 hours ago
Jo KingJo King
25.6k362129
$endgroup$
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
answered 16 hours ago
Jo KingJo King
25.6k362129
answered 16 hours ago
Jo KingJo King
25.6k362129
answered 16 hours ago
Jo KingJo King
25.6k362129
answered 16 hours ago
Jo KingJo King
25.6k362129
25.6k362129
add a comment |
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if it's equal.
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
16 hours ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if it's equal.
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
16 hours ago
add a comment |
$begingroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if it's equal.
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
05AB1E, 8 7 bytes
[Ð{Q#ιн
-1 byte thanks to @Emigna.
Try it online or verify some more test cases (or verify those test cases with step-by-step for each iteration).
Removes all odd 0-indexed items every iteration, so removes $frac{n-1}{2}$ items if the list-size is odd.
Explanation:
[ # Start an infinite loop:
Ð # Triplicate the list (which is the implicit input-list in the first iteration)
{Q # Sort a copy, and check if it's equal.
# # If it is: Stop the infinite loop (and output the result implicitly)
ι # Uninterweave: halve the list into two parts; first containing all even-indexed
# items, second containing all odd-indexed items (0-indexed)
# i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
н # And only leave the first part
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
edited 16 hours ago
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
answered 17 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
41.6k567215
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
16 hours ago
add a comment |
3
$begingroup$
You can useιinstead of2äif you switch to a keep every other element strategy.
$endgroup$
– Emigna
16 hours ago
3
3
$begingroup$
You can use
ι instead of 2ä if you switch to a keep every other element strategy.$endgroup$
– Emigna
16 hours ago
$begingroup$
You can use
ι instead of 2ä if you switch to a keep every other element strategy.$endgroup$
– Emigna
16 hours ago
add a comment |
$begingroup$
Java 10, 106 bytes
L->{for(int M=1<<31,p=M,f;;L=L.subList(0,L.size()/2),p=M){f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
Try it online.
Or alternatively:
L->{for(int M=1<<31,p=M;;L=L.subList(0,L.size()/2),p=M){var f=1>0;for(int i:L)f&=p<=(p=i);if(f)return L;}}
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(int M=1<<31, // Minimum integer, set to -2147483648
p=M, // Previous integer, starting at this minimum
f // Flag-integer, starting uninitialized
; // Loop indefinitely:
; // After every iteration:
L=L.subList(0,L.size()/2),
// Only leave halve the numbers in the list
p=M){ // And reset the previous-integer to the minimum
f=1; // Set the flag-integer to 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
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
7 hours ago
add a comment |
$begingroup$
Java 10, 106 bytes
L->{for(int M=1<<31,p=M,f;;L=L.subList(0,L.size()/2),p=M){f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
Try it online.
Or alternatively:
L->{for(int M=1<<31,p=M;;L=L.subList(0,L.size()/2),p=M){var f=1>0;for(int i:L)f&=p<=(p=i);if(f)return L;}}
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(int M=1<<31, // Minimum integer, set to -2147483648
p=M, // Previous integer, starting at this minimum
f // Flag-integer, starting uninitialized
; // Loop indefinitely:
; // After every iteration:
L=L.subList(0,L.size()/2),
// Only leave halve the numbers in the list
p=M){ // And reset the previous-integer to the minimum
f=1; // Set the flag-integer to 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
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
7 hours ago
add a comment |
$begingroup$
Java 10, 106 bytes
L->{for(int M=1<<31,p=M,f;;L=L.subList(0,L.size()/2),p=M){f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
Try it online.
Or alternatively:
L->{for(int M=1<<31,p=M;;L=L.subList(0,L.size()/2),p=M){var f=1>0;for(int i:L)f&=p<=(p=i);if(f)return L;}}
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(int M=1<<31, // Minimum integer, set to -2147483648
p=M, // Previous integer, starting at this minimum
f // Flag-integer, starting uninitialized
; // Loop indefinitely:
; // After every iteration:
L=L.subList(0,L.size()/2),
// Only leave halve the numbers in the list
p=M){ // And reset the previous-integer to the minimum
f=1; // Set the flag-integer to 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
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
$endgroup$
Java 10, 106 bytes
L->{for(int M=1<<31,p=M,f;;L=L.subList(0,L.size()/2),p=M){f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}
Try it online.
Or alternatively:
L->{for(int M=1<<31,p=M;;L=L.subList(0,L.size()/2),p=M){var f=1>0;for(int i:L)f&=p<=(p=i);if(f)return L;}}
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(int M=1<<31, // Minimum integer, set to -2147483648
p=M, // Previous integer, starting at this minimum
f // Flag-integer, starting uninitialized
; // Loop indefinitely:
; // After every iteration:
L=L.subList(0,L.size()/2),
// Only leave halve the numbers in the list
p=M){ // And reset the previous-integer to the minimum
f=1; // Set the flag-integer to 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
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
edited 13 hours ago
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
answered 14 hours ago
Kevin CruijssenKevin Cruijssen
41.6k567215
41.6k567215
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
7 hours ago
add a comment |
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}is shorter using streams, but I haven't been able to figure out how to avoid thejava.lang.IllegalStateException: stream has already been operated upon or closederror after returning the stream
$endgroup$
– Embodiment of Ignorance
7 hours ago
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} is shorter using streams, but I haven't been able to figure out how to avoid the java.lang.IllegalStateException: stream has already been operated upon or closed error after returning the stream$endgroup$
– Embodiment of Ignorance
7 hours ago
$begingroup$
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} is shorter using streams, but I haven't been able to figure out how to avoid the java.lang.IllegalStateException: stream has already been operated upon or closed error after returning the stream$endgroup$
– Embodiment of Ignorance
7 hours ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 42 bytes
#//.x_/;Sort@x!=x:>x[[;;⌊Tr[1^x]/2⌋]]&
Try it online!
answered 14 hours ago
J42161217J42161217
13.5k21252
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 42 bytes
#//.x_/;Sort@x!=x:>x[[;;⌊Tr[1^x]/2⌋]]&
Try it online!
answered 14 hours ago
J42161217J42161217
13.5k21252
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 42 bytes
#//.x_/;Sort@x!=x:>x[[;;⌊Tr[1^x]/2⌋]]&
Try it online!
answered 14 hours ago
J42161217J42161217
13.5k21252
$endgroup$
Wolfram Language (Mathematica), 42 bytes
#//.x_/;Sort@x!=x:>x[[;;⌊Tr[1^x]/2⌋]]&
Try it online!
answered 14 hours ago
J42161217J42161217
13.5k21252
edited 10 hours ago
answered 14 hours ago
J42161217J42161217
13.5k21252
answered 14 hours ago
J42161217J42161217
13.5k21252
answered 14 hours ago
J42161217J42161217
13.5k21252
13.5k21252
add a comment |
add a comment |
$begingroup$
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!
answered 17 hours ago
Expired DataExpired Data
3186
$endgroup$
add a comment |
$begingroup$
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!
answered 17 hours ago
Expired DataExpired Data
3186
$endgroup$
add a comment |
$begingroup$
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!
answered 17 hours ago
Expired DataExpired Data
3186
$endgroup$
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!
answered 17 hours ago
Expired DataExpired Data
3186
answered 17 hours ago
Expired DataExpired Data
3186
answered 17 hours ago
Expired DataExpired Data
3186
answered 17 hours ago
Expired DataExpired Data
3186
3186
add a comment |
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
$endgroup$
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
add a comment |
$begingroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
$endgroup$
MATL, 11 bytes
tv`1L)ttS-a
Try it online!
This works by removing every second item.
Explanation
t % Take a row vector as input (implicit). Duplicate
v % Vertically concatenate the two copies of the row vector. When read with
% linear indexing (down, then across), this effectively repeats each entry
` % Do...while
1L) % Keep only odd-indexed entries (1-based, linear indexing)
t % Duplicate. This will leave a copy for the next iteration
tS % Duplicate, sort
-a % True if the two arrays differ in any entry
% End (implicit). A new iteration starts if the top of the stack is true
% Display (implicit). Prints the array that is left on the stack
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
edited 14 hours ago
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
answered 17 hours ago
Luis MendoLuis Mendo
75k888291
75k888291
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
add a comment |
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
2
2
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
Broken for initially sorted list: [1, 2, 3, 4, 5] should remain [1, 2, 3, 4, 5]
$endgroup$
– Falco
15 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
$begingroup$
@Falco Thanks! Corrected now
$endgroup$
– Luis Mendo
14 hours ago
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
$endgroup$
Jelly, 7 bytes
m2$⁻Ṣ$¿
Try it online!
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
answered 12 hours ago
Erik the OutgolferErik the Outgolfer
32.8k429105
32.8k429105
add a comment |
add a comment |
$begingroup$
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?
$endgroup$
1
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
add a comment |
$begingroup$
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?
$endgroup$
1
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
add a comment |
$begingroup$
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?
$endgroup$
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?
edited 9 hours ago
community wiki
2 revs
ais523
1
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
add a comment |
1
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
1
1
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
$begingroup$
One byte per infinity stone.
$endgroup$
– djechlin
8 hours ago
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered 12 hours ago
TauTau
656211
$endgroup$
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered 12 hours ago
TauTau
656211
$endgroup$
add a comment |
$begingroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered 12 hours ago
TauTau
656211
$endgroup$
TI-BASIC (TI-84), 47 42 45 bytes
Ans→L1:Ans→L2:SortA(L1:While not(min(L1=Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans
Input list is in Ans.
Output is in Ans and is implicitly printed out.
Explanation:
Ans→L1 ;store the input into two lists
Ans→L2
SortA(L1 ;sort the first list
; two lists are needed because "SortA(" edits the list it sorts
While not(min(L1=Ans ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2 ;remove the latter half of the second list
; removes (n+1)/2 elements if list has an odd length
L2→L1 ;store the new list into the first list (updates "Ans")
SortA(L1 ;sort the first list
End
Ans ;implicitly output the list when the loop ends
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
answered 12 hours ago
TauTau
656211
edited 1 hour ago
answered 12 hours ago
TauTau
656211
answered 12 hours ago
TauTau
656211
answered 12 hours ago
TauTau
656211
656211
add a comment |
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered 16 hours ago
Expired DataExpired Data
3186
$endgroup$
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered 16 hours ago
Expired DataExpired Data
3186
$endgroup$
add a comment |
$begingroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered 16 hours ago
Expired DataExpired Data
3186
$endgroup$
VDM-SL, 99 bytes
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
Never submitted in vdm before, so not certain on language specific rules. So I've submitted as a function definition which takes a seq of int and returns a seq of int
A full program to run might look like this:
functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0])
answered 16 hours ago
Expired DataExpired Data
3186
answered 16 hours ago
Expired DataExpired Data
3186
answered 16 hours ago
Expired DataExpired Data
3186
answered 16 hours ago
Expired DataExpired Data
3186
3186
add a comment |
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered 9 hours ago
GiuseppeGiuseppe
17.1k31152
$endgroup$
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered 9 hours ago
GiuseppeGiuseppe
17.1k31152
$endgroup$
add a comment |
$begingroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered 9 hours ago
GiuseppeGiuseppe
17.1k31152
$endgroup$
Gaia, 9 bytes
eo₌⟪e2%⟫↻
Try it online!
There's a bit of a bug in the Gaia parser, probably because it hasn't been updated in 2 years.
I expected ₌ to add the same value to the stack, but alas, it adds a string rather than an array, which caused me no end of confusion.
Explanation:
e | eval input as a list
↻ | until
o | the list is sorted
₌ | push additional copy (as a string):
⟪e | eval as a list
2%⟫ | and take every 2nd elementanswered 9 hours ago
GiuseppeGiuseppe
17.1k31152
answered 9 hours ago
GiuseppeGiuseppe
17.1k31152
answered 9 hours ago
GiuseppeGiuseppe
17.1k31152
answered 9 hours ago
GiuseppeGiuseppe
17.1k31152
17.1k31152
add a comment |
add a comment |
$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.
answered 14 hours ago
NeilNeil
82.1k745178
$endgroup$
add a comment |
$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.
answered 14 hours ago
NeilNeil
82.1k745178
$endgroup$
add a comment |
$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.
answered 14 hours ago
NeilNeil
82.1k745178
$endgroup$
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.
answered 14 hours ago
NeilNeil
82.1k745178
answered 14 hours ago
NeilNeil
82.1k745178
answered 14 hours ago
NeilNeil
82.1k745178
answered 14 hours ago
NeilNeil
82.1k745178
82.1k745178
add a comment |
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered 14 hours ago
ShaggyShaggy
19k21667
$endgroup$
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered 14 hours ago
ShaggyShaggy
19k21667
$endgroup$
add a comment |
$begingroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered 14 hours ago
ShaggyShaggy
19k21667
$endgroup$
Japt, 10 bytes
eUñ)?U:ßUë
Try it
eUñ)?U:ßUë :Implicit input of array U
e :Compare equality with
Uñ : U sorted
) :End compare
?U: :If true then return U else
ß :Run the programme again with input
Uë : Every second element of U
answered 14 hours ago
ShaggyShaggy
19k21667
edited 13 hours ago
answered 14 hours ago
ShaggyShaggy
19k21667
answered 14 hours ago
ShaggyShaggy
19k21667
answered 14 hours ago
ShaggyShaggy
19k21667
19k21667
add a comment |
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
$endgroup$
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
$endgroup$
add a comment |
$begingroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
$endgroup$
Java (JDK), 102 bytes
n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}
There's already a C# answer, so I decided to try my hand on a Java answer.
Try it online!
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
answered 3 hours ago
Embodiment of IgnoranceEmbodiment of Ignorance
2,208125
2,208125
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f182221%2fimplement-the-thanos-sorting-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
What direction does the list need to be sorted in for termination? Ascending, descending, either or at the choice of the algorithm?
$endgroup$
– Expired Data
18 hours ago
4
$begingroup$
Don't we need to sort and eliminate half of the answers...
$endgroup$
– Sumner18
14 hours ago
4
$begingroup$
What is to stop an answer from simply returning any one element of the input?
$endgroup$
– Captain Man
14 hours ago
4
$begingroup$
@CaptainMan "While the list is not sorted [...]" If the list is already sorted, it should be returned as is
$endgroup$
– FireCubez
14 hours ago
3
$begingroup$
@DJMcMayhem, I originally thought the same, but that's actually not correct. Consider input [1,3,2,4].
$endgroup$
– usul
10 hours ago