12:05 PM
oh i get it

for example, I should be the least faded person right now

CMC: Favorite sorting algorithm? Mine's sleepSort

mine is mergesort

12 messages moved from The Edge of Propinquity

slaps face I actually clicked that, nice.

12:14 PM
@lyxal ha i clicked that and because of my crappy internet i got saved

Ye I closed the tab beforeit loaded

TIL propinquity means "Proximity; nearness."

I was like "huh? Where are the messages? I'llj ust click the link."

GPT-3 really does have a better vocabulary than I thought

Show me?

12:15 PM
48 secs ago, by lyxal
TIL propinquity means "Proximity; nearness."
"The Edge of Propinquity" was generated from all the room names here

Oh yeah

Hey if y'all need username ideas:
```casper
Hawk
Firefighter0701
tacoslayer
jackassonwheels
Thomas
Some Guy
muhahaha
Stuart Jansen
Jebediah

HouseOfCantor
Ethereal
CoffeeCat
Sci-fi
michael.ottawa

Dylan
Sudoku
Keshawn Meeks
Mariel
Hawk
buzzdave
Ivan Chew
Moggie
tldr
Mike
Hawk
Hawk```

@lyxal thank you
muhahaha

GPT-2

12:21 PM
GPT-3
with dark mode too

I mean, at least GPT-2 generates english

@Ausername that's nothing. the empty set denotes, even though it doesn't denote anything

@Neil Ok...
2

does anyone know R well enough to tell if codegolf.stackexchange.com/a/230419/7310 is really linear time?

e.g. all members of the empty set are odd, even, square, cube, prime and composite

12:23 PM
Oh true...
More GPT-2
'night

@flawr Feel like convolving stuff?

CMQ: Name an O(n) sort algorithm.

@Adám count sort, radix sort, just leaving the input as it is :)
depends on what the input looks like
@Adám count sort is linear time if the input is integers in a small range
@Adám radix sort is linear time if the input is integers in the range 0..n^c for a constant c if the input is of length n integers.
curiously you can convert from C doubles to 64 bit integers and back without any loss

12:43 PM
@felipa What is count sort?

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of...

@felipa Of course, they are all just 64 bits. Doesn't matter what the bits represent.

en.wikipedia.org/wiki/…. is also linear time under the right circumstances
specifically if the input is uniformly distributed
@Adám yes but the key point is that the order is preserved

@felipa That sounds suspicious. Some 64-bit patterns do not represent orderable floats.

which I think essentially always happens

12:49 PM
@felipa I still don't get it. E.g. is `qNaN<sNaN`?

@Adám is that a floating point nan?

Yes.

if it's nan that I guess there is no defined order so you can do what you like with it

5 mins ago, by felipa
@Adám yes but the key point is that the order is preserved

how is nan represented in bits in IEEE754?
@Adám that's right. The order of things that had order in the first place
like 7 and 13

12:52 PM
@felipa `s111 1111 1xxx xxxx xxxx xxxx xxxx xxxx`
@felipa But surely, any IEEE754 NaN must correspond to a 64 bit int.

@Adám sure. Maybe the range is 63 bits in that case?
We need an expert :)

@felipa Well, there are 16777214 IEEE754 NaNs, all the ints they correspond to are problematic.

so it could still be 63 bits?
If feel writing some code and trying it out could help here

I guess. Since all floats that begin with `s0` are normal floats.

that sounds good

12:58 PM
Not very curiously, you can convert from C doubles to 63 bit integers and back without any loss.

and preserve the order!!

If that even holds. I'm not so sure this is even true.

that's the clever bit

It it was true.
However, some floats have multiple valid bit representations. Clearly, these values should be considered equal (even if only one is the normal form), and thus they don't have the same ordering as the integers they correspond to.

1:27 PM
can you give examples?

@felipa 1×2⁴ and 0.5×2⁵

can the mantissa even be 1?

@Adám what order do you want those sorted in?

@felipa They are both 16.

@Adám so what is the concern?
they will be sorted correctly when converted to ints won't they?

1:36 PM
oh, wait, sorry, ofc. but i don't think 0.5 can be the mantissa? don't quite remember but i think it requires 1 <= m < 2

@felipa No, they will be unequal when converted to ints, and therefore they might switch places.

as long as nothing comes in between them!

Lots of things come between them, because they are not consecutive ints.

@Adám lots of doubles when converted to ints?
can you show a double that would come in between?

Sure.
0.75×2⁵

1:39 PM
@Adám can 0.5 be a mantissa?
or 0.75

@Adám i'm not sure you understand how floats work
mantissas almost always have an implicit leading digit of 1

@ngn I'm pretty sure I don't.

the exceptions are the two 0s, denormals (if supported), nans and infinities

Right, my examples were only for illustration.

so, 16 has a unique representation

1:42 PM
Right.

currently spending a day looking at the polyglot
it just has everything, including ESCAPE

However, very small numbers can have non-unique representation.

i thought only 0 and nan have non-unique representations

best is O(n log log n), from here

@ngn Ah, looks like I mixed up things. Decimal floats have this issue.
@StackMeter Stalin sort is O(n)

1:47 PM
lol

@Adám yes but that doesn't return all n items
whatever's left in the gulag may or may not be unsorted

So?

here's another O(N) sorting algo (O(1) even!)
`x=>[]`

if it's not sorted, you have to sort it again

@StackMeter One doesn't go to Gulag to stay; one goes to die.

1:49 PM
many escaped

@hyper-neutrino Hitler sort!

`x=>x[0]` \o/

@hyper-neutrino what about the ENTIREITY OF THE REST OF THE LIST

Gone, reduced to atoms.

sorry for shouting, but a sort is not a sort unless it works with 100% accuracy on 100% of the list 100% of the time

1:51 PM
@hyper-neutrino Primogeniture sort?
@StackMeter It does, though.

monkey-patch the cmp() function to always return -1 to fool any potential tests. what would this algorithm be called? :)

"digging yourself a deeper and deeper hole" sort?

@Adám that works on (100/len(x))% of the list, and as we all know, 1/x tends to 0, so 100/x tends to 0

yes i have been very busy lately
i would come back, but recently I am busy at school and stuffs

Mean sort, O(n): Replace all values with the average of the list.
CMC: Implement mean sort.

1:54 PM
@Adám Assuming we're given `n` as an input, I think Jelly and it outputs `n+1`

@Adám `Æmṁ` in Jelly

lazy sort - return instantly, and later sort the first i+1 elements when result[i] is accessed

Nice sort, O(1): Tell the list that it's beautiful just the way it is and doesn't need to be in any other order.

@ngn don't think that would work very well :P

@Adám take a look at this

1:56 PM
@hyper-neutrino this sorting algorithm believes that all array elements are born equal :)

In, there are two things that you must have to be a sorting algorithm.

1) The output must be in NONDECREASING ORDER - no element x > y if index(x) < index(y)

2) The output must be a PERMUTATION of the input, i.e. NO ELEMENT MUST BE SKIPPED, DUPLICATED OR REPLACED.

therefore your "sorts" are not sorts, but imposter sorts.

I hope you do realize we're (at least I'm) joking...

ik
just felt the need to say

@Adám APL, 8 bytes: `(≢⍴+/÷≢)`
(are the brackets needed?)

@StackMeter well, at least the small-domain algorithms (counting sort, dutch flag, radix..) are serious

2:01 PM
@ngn yes, but those fit the criteria

wait radix sort is linear? wat

@hyper-neutrino if all the numbers fit into a single base-c digit

realistically, it's n log n

radix is definitely logarithmic from what i remember for avg case
something (n+m)*log b or whatever

2:03 PM
however, there are improvements to radix sort that allow you to get n log log n for all numbers b where the word length is > log n

@hyper-neutrino it's linear in n (the length of the array) on the assumption that its elements are below a certain limit

hmm okay, I see

@hyper-neutrino nope

okay. It wasn't working when I just tried `⎕← ≢⍴+/÷≢ 1 2 3 5` probably because then the whole thing becomes a chain of monads but idk what's the requirement when actually submitting as a solution

the actual algorithm is a mix of radix sort and merge sort, which, in conjunction, push it down to n log^2 n
at least that's what I think log^2 n is

2:06 PM
CMQ: I optimised an algorithm from O(n²) to O(n) and then my colleague argued the commit message was wrong because the array size was constant so both were O(1). Who was right?

@pxeger what was the algortihm
because I think it's still O(n)

@hyper-neutrino when submitting as a solution you can assign the train to a variable without brackets

@pxeger your boss when he said stop arguing about nonsense and get back to work :)

it was a string internment/caching initiialisation routine

so you can omit them

2:07 PM
@ngn lol

ah, okay thanks

@pxeger I'm saying O(n)

n was like 600

so O(600)?

even if N is small and fixed the TC of an algorithm is still just based on the size in theory is it not?

2:09 PM
yup, O(360000) -> O(600)

like, if you nested loop thrice through a list even if it has like 4 elements it's still a cubic-time algorithm

Well theoretically any algorithm with limited input size can be O(1)

you can say the runtime in practice doesn't make a difference because the array is constant and small, but the compexity doesn't care

@hyper-neutrino true
@hyper-neutrino complexity cares not for your mortal, limited size input
I am dropping gems here

broke: program doesn't work at all
woke: O(infinity) time complexity

2:13 PM
lol
@Razetime infinity is a constant so that's still O(1)
4

genius

infinity is strictly not a constant

you mean O(n^infinity

infinity + 1 = infinity
this makes it not a constant

2:17 PM
So O(n) then
I see
still better than O(n!)

infinity != any n
you can only approach infinity
infinity is an expression that will always be higher than any weight you compare to it

well if adding any constant to it returns it
it must be O(n)
you probably meant O(n^n^n^n^n... infinity times)

are you reading anything i am saying

I am
what is infinity in terms of n then
since n is what we measure time complexity

> what is infinity in terms of n
it isn't
that's the point

2:23 PM
so if it's not any nc, n^c, or n+c (c is a constant or an expression of one of those types), it's a constant

Infinity isn't a proper number that can be manipulated like other numbers

and?

that makes it not fit in any of your formats

JS: `const x = Infinity;` ergo infinity is a constant

@pxeger e x a c t l y

2:26 PM
noo mr patrick pls

If you have an infinite list, then O(n)=O(infinity)
@Razetime ???

@user I presume Razetime was referring to me (my name is Patrick)

I would like to make bpa.st/A37Q in-place. Can anyone see how to do it?

no his name is the krusty krab
@felipa what does "in-place" mean

@felipa what do you mean by in-place? Do you mean non-recursive?

2:29 PM
@Razetime Oh, spongebob

@felipa copy the list

@Razetime I mean that it only uses the list that it is given and doesn't make any new ones
@pxeger ^^^
@StackMeter in-place means no new lists

oh partitioning without extra lists

why would you want to do that?

it needs to reorder profits_weights

2:30 PM
maybe use index values instead of lists?

I'm pretty sure it would be slower

@Razetime yes exactly

he wants a quicksort like paritioning thing
which will be faster

@pxeger why would it be slower? quicksort is famously done in-place
@Razetime exactly yes

why would in-place be faster

2:31 PM
@cairdcoinheringaahing I think you meant: "can get away without subjects in English if don't give a shit"

@felipa what is stopping you from making it in-place?

creating extra arrays and populating them with values is definitely less efficient than modification

unless you're working with log (n) to begin with
which, if you're sorting you can't
@Razetime copying surely is a constant time thing

Unless I'm misunderstanding what the algorithm is supposed to do, you would have to insert items in the middle of the list which is probably slower than allocating some new ones

or at worst linear

2:33 PM
@ngn I think I can do the partitoning with something like bpa.st/MDTQ

@StackMeter How?

@ngn but I am not sure how to plug it all together

It's O(n) because you go through the entire list

just add a new pointer to the list

That's not copying

2:33 PM
@user oh

do you know how memory works?

evidently lmao

You don't need to know how memory works

and add extra time because you are adding to a list based on a condition

2:33 PM
ok
but conditions are constant

ok how do you copy N elements without going through all N of them lol - it has to be linear

you check one item

maybe I should have asked an in-place challenge

@felipa that looks remarkably similar to the code @Anush posted a couple of days ago

If you just make a new pointer, modifying the new list would modify the old one and vice versa

2:34 PM
@ngn it's the same code

it's like copying your house and giving it to a friend by just cutting a new key
(no it isn't, but i wanted to give a garbage analogy)

but I can't see quite how to make it all work

oh
ok

@hyper-neutrino It's not a bad analogy. I once tried copying my friend's house and burning it down but accidentally just burned his house down instead :/
4

ah, yeah, I hate it when that happens

2:36 PM
@felipa first step - simplify :) you don't need 5 cases in that while loop - i think only 2 will do

it's not constant, but it's linear, and any sorting algorithm is linear at best

@hyper-neutrino When you get 3 stars after posting obvious starbait? Yeah
:P

@ngn if you can see how to do it, I would love help
don't make me ask SO :)

@user imo, the star comes at the moment you least expect it to

not really in this case

2:37 PM
@user meh who cares if it's star bait when it's also just funny

@ngn at least I have completely working code to start with :)

^^^
@Razetime Fair enough :P

@felipa then if your code works you'd ask CR not SO i think :P

@hyper-neutrino :)

idk CR's scope too well though ¯\_(ツ)_/¯

2:38 PM
@hyper-neutrino Don't ever suggest using CR, they'll hunt you down and format all your golfed code if you do :P

@felipa you mean the working code is the one that makes new arrays?

@felipa creating a new list isn't going to increase the time complexity except by a linear factor, and any sorting algorithm is linear at absolute best, so it's effectively constant

@ngn yes
@StackMeter right but I care about constant factors today :)

2:41 PM
it's not every day that I care about constant factors but I do care today

@Razetime wdym?
@Razetime I've read several different articles trying to find the best sort today

@StackMeter it really does depend on the input
data that is almost sorted can be sorted more quickly by timsort for example

@felipa how?

@StackMeter see above
ints can be sorted very quickly by radix sort but string sorting may be faster by another method
etc.
@user :)
I like running automatic formatters on codegolf answers

@felipa really fun on perl

2:45 PM
You...what?!?1!

@Razetime I didn't even know there were perl formatters!

more often than not they do nothing
or they absolutely break the program

@Razetime for which language?

most languages

@felipa do you really need `middlepart`? would it ruin the algorithm if it's considered part of `largepart` (or `smallpart`)?

2:46 PM
js, ruby, perl, so on
even C

Ruby too?

formatters aren't used to seeing an entire program written in a for loop

@ngn You might be able to merge them but it's part of the logic. "while cum_weight < capacity and middlepart:" is an important loop
the key point is that at some point we need to deal with a fractional part of an item
if it's fast and in-place I can be flexible :)
@ngn I can give more test cases if that is helpful

@felipa anush's version partitions only into >=pivot and <pivot

@ngn they may be cleverer than me :)

2:51 PM
but their code didn't work :)

@hyper-neutrino Is JoKing the new hive mind now?

@ngn so only cleverer in parts :)
I really like anush's partitioning. It feels they are on the right lines because it looks like quicksort's partitioning in spirit

@cairdcoinheringaahing We are all JoKing, just as we are all caird and lyxal and hyper and WW, because we are all one entity controlled by the Supreme Leader Redwolf Programs

> We are all joking

Except for Tim. Screw Tim.

2:54 PM
I think this describes 97% of all conversation here :P

lmao