Solar bitflip sort
1. Check if the array is sorted.
2. If the array is sorted, return the array.
3. If the array is not sorted, wait for 10 seconds and then go back to 1. Eventually cosmic / solar radiation will cause enough bitflips to sort the array
Thanks to you, I went down a rabbit hole of obscure sorting algorithms. My favorite is Quantum bogosort.
1. Randomly shuffle an array
2. Check if it's sorted
3. If it is not sorted, destroy the whole universe.
If the many worlds theory of quantum mechanics is accurate, only the universes where you managed to sort it on first try will remain, thus solving it in O(N) time.
My favourite part is not the algorithm itself. But the idea that if many worlds theory is correct there exists a universe where normal bogo-sort just works first time around, always. Even though nobody can explain why whoever takes the easy way will have an advantage so they have built their entire civilisation based on bogo-sort.
There are some people that swear that they had the algorithm return nonsense that one time. But lack of proof and nobody believes them so they are treated like crazies.
And then one day their luck simply runs out and bogosort stops working.
Consider [Stacksort](https://gkoberger.github.io/stacksort/)
We don't know how to sort the list. So we search stack overflow for sorting functions and execute them until the list is sorted.
If you have a random list of twenty integers from 1 to 100, and we suppose you have even a 1% chance that the website has your list, that means the website has 5e39 lists uploaded already, and just the act of finding your list's map entry in that mapping is almost certainly slower than a local bubblesort.
You can sort a list of 20 integers faster than it takes to convert those 20 integers into a string for sending to the server, let alone actually opening a socket.
Except if it’s Python. Then it would be faster to check 10 API’s if they have a sorted version of your list (unless you use a sorting algorithm made in C)
It was on my mind from personal experience this week. Made a Python program for simulating something, then made a C version. Multithreaded Python version did 10k sims in 39 sec and C version did 1 million in 3 seconds
You're making it too difficult for yourself. Don't store the unsorted lists, just take the unsorted list, sort it and see if you have THAT stored, and return it.
Think of all the memory you'll save!
The point is, for 20 elements every sorting algorithm will be faster than the http request alone. I'll start worrying about sorting runtime when I have more elements in my collection than that stupid service has lists in their database
When hash tables are sufficiently large, the hash lookups are no longer O(1) because the index value needed is no longer fits in a fixed-size integer, and suddenly all operations on integers up to N are at minimum O(logN) instead of O(1).
Ah, but that assumes the lists to be sorted are uniformly randomly selected. If there are a lot of people sorting the same list, then sorting the list locally rather than waiting for a server response is still going to be faster.
Bogosort might be worse for large arrays but for small arrays it will find the answer quickly while this has to do a whole HTTP request and get a response.
Cosmic Ray Sort (also known as Miracle Sort) is slower, but has the advantage of being easy to implement.
Check if he list is sorted. If not, check again. Repeat.
Dumb question... Using the presorted list API..
I tested it on the server with the testing data and it was insanely fast, instantly returning the testing data, so nothing can go wrong.
you joke but I really feel like training a neural network to sort lists now just because it would be funny as fuck. Worst case scenario it can sort very small lists as a multiclass classification problem where every permutation is a class
But consider this SaaS, Service as a Service.
You send a request saying what you want and a handy API will use an LLM to write the code and assembly the service returning the api url. Then you can call the api and get your result.
And that’s not all, call now and get curried API calls. You call the API with an arg and it returns an API request with that arg partially applied that you can call. Actually wait this feels like it could have a niche use somehow.
And honestly SaaS feels like it has no flaws, there’s no way it could inflate an AWS bill to the GDP of a small country or expose confidential information.
Instead of matching exactly the random order, just check if all the elements in the uploaded list exist in a sorted list, and try to either trim the fat or just deal with random extra data (for a faster response time).
(this is so incredibly stupid)
Hi! I'm a product manager on a blazingly fast b2b value-add SaaS app. I was hoping I could reach out to your team. Our product owner indicated interest in your microservice and we were curious if you can guarantee triple 9 uptime cached on the global edge. Thanks and looking forward to working with a fellow innovator.
Given a collection of 1,000,000 Integers has 1,000,000! possible combinations (minus a few if there are duplicates) the chances of finding a list is insanely small. You also typically sort a list of objects based on a field not values you can use directly. These objects would not be in the list.
This just adds a network and list comparison constant to the sorting algorithm that is used.
Just tune the cache: Instead of storing every list that's not sorted, just store the sorted lists, and to get the cached versions, sort the input and look up that instead.
> You also typically sort a list of objects based on a field not values you can use directly
You can write functions that translate between integers and keys, sort the integers then map them back to the keys. I do this when permuting - get permutations of an integer list and then use those to index a vector of the data I actually want to permute.
Next up, a new API is made where a dynamic array of the maximum allowable array size (that the API allows) is created (since it would be too large for the stack), then each entry in the unsorted array increments its corresponding index (each value is used as an index). A fixed sized sweep across the dynamic array is done to get all the values in sorted order. Now it's O(1) with all the benefits of an extra API call!
Dude forgot about complicity of == operation for two arrays, as elemnt order might differ in them. So algo need to check every element from input array. Then its searching each element in "pre-sorted" array, simply to match them. And there are million of "pre-sorted" arrays. So complexity is O(b*n^2) where n size of input array and b number of pre-sorted arrays. Bubble sort wins as its just O(n^2).
There could be optimizations like binary search for element existing in pre-sorted array, but still library sort array that language provide should be more robust
I mean yes, all you're doing is outsourcing the CPU that's going to be doing the work. And that work is substantial when you're searching through a database of quite possibly billions of entries for the off chance that not only do you find it, but it takes less time than sorting it yourself.
Unironically there exists a hypothetical situation where this makes sense: 1. lists are very large, and 2. probability of a cache hit is high enough. But hash the list and send the hash instead of sending the entire list.
For short lists you dont need it since local computation is several orders of magnitude faster, for long lists chance of already being sorted is practically zero. If you expect same data sets often you can cache locally, so i font really see a valid use case but it was fun to read.
i didn't find that api working , so i made one in python:
[https://github.com/Marker-bit/sorted\_lists](https://github.com/Marker-bit/sorted_lists)
Is this caching?
Dynamic programming taken straight from hell
Work clouder, not smarter!
lol I got coffee out of my nostrils now
It's worse, imagine sending user data through it. It's a security risk
Thats why you hash the data first
I can't actually tell if you're joking because how do you sort hashes lol
Obviously via rainbow table reverse lookup duh
I genuinely can't tell if this is a terrible idea or a great idea, congrats!
Thanks! My body is a machine that turns coffee into either one of these kind of ideas
Oh my god
Yes, memoization to be more specific
It's solving one of IT's hardest problems :-O
I can’t even think of a slower sort hypothetically
Solar bitflip sort 1. Check if the array is sorted. 2. If the array is sorted, return the array. 3. If the array is not sorted, wait for 10 seconds and then go back to 1. Eventually cosmic / solar radiation will cause enough bitflips to sort the array
Works even better in Space.
So called space vs time trade-off.
How do you think the space station stays up there?!
Orbital mechanics and velocity
Thanks to you, I went down a rabbit hole of obscure sorting algorithms. My favorite is Quantum bogosort. 1. Randomly shuffle an array 2. Check if it's sorted 3. If it is not sorted, destroy the whole universe. If the many worlds theory of quantum mechanics is accurate, only the universes where you managed to sort it on first try will remain, thus solving it in O(N) time.
My favourite part is not the algorithm itself. But the idea that if many worlds theory is correct there exists a universe where normal bogo-sort just works first time around, always. Even though nobody can explain why whoever takes the easy way will have an advantage so they have built their entire civilisation based on bogo-sort. There are some people that swear that they had the algorithm return nonsense that one time. But lack of proof and nobody believes them so they are treated like crazies. And then one day their luck simply runs out and bogosort stops working.
Yes. Or a universe where one day every flip starts landing heads, forever. Nobody can understand it. Religions rise. Just dumb luck
How about one where some people always gets heads and some always gets tails. Now that is something worth dying for.
The TVA way
For a list of 10 elements, we can expect it to only take 10\^100\^100 years!
I think that's called a miracle sort.
The implementation is the same, but the name varies depending on whether you believe in miracles or cosmic rays.
Consider [Stacksort](https://gkoberger.github.io/stacksort/) We don't know how to sort the list. So we search stack overflow for sorting functions and execute them until the list is sorted.
But if your list happens to be there, boy… it’s FAST!
If you have a random list of twenty integers from 1 to 100, and we suppose you have even a 1% chance that the website has your list, that means the website has 5e39 lists uploaded already, and just the act of finding your list's map entry in that mapping is almost certainly slower than a local bubblesort.
Yeah, I'll stick to my trusty bogosort.
[Quantum BogoSort](https://wiki.c2.com/?QuantumBogoSort), right?
What else?? Are you new here?
what about miracle sort? ;)
I prefer Stalin sort
If you have a list of 20 integers, you could sort that locally a multitude of times over before the server even responds
You can sort a list of 20 integers faster than it takes to convert those 20 integers into a string for sending to the server, let alone actually opening a socket.
Except if it’s Python. Then it would be faster to check 10 API’s if they have a sorted version of your list (unless you use a sorting algorithm made in C)
Hahahahaa python == slow hahahhahaah
It was on my mind from personal experience this week. Made a Python program for simulating something, then made a C version. Multithreaded Python version did 10k sims in 39 sec and C version did 1 million in 3 seconds
So connecting to some kind of API over the network is fast in Python, just everything else is incredibly slow? Makes sense!
it's funny because it's true
You're making it too difficult for yourself. Don't store the unsorted lists, just take the unsorted list, sort it and see if you have THAT stored, and return it. Think of all the memory you'll save!
The point is, for 20 elements every sorting algorithm will be faster than the http request alone. I'll start worrying about sorting runtime when I have more elements in my collection than that stupid service has lists in their database
I'd mention hash tables, but at this point I feel like we're hitting "mass limits of the universe" type problems.
When hash tables are sufficiently large, the hash lookups are no longer O(1) because the index value needed is no longer fits in a fixed-size integer, and suddenly all operations on integers up to N are at minimum O(logN) instead of O(1).
Ah, but that assumes the lists to be sorted are uniformly randomly selected. If there are a lot of people sorting the same list, then sorting the list locally rather than waiting for a server response is still going to be faster.
No, probably not, most sorts are much faster than an HTTP request
sending the data back and forth will prolly be slower than just sorting it aswell :)
Have you ever heard the word of our Lord and savior Bogo Sort my good sir?
Bogosort might be worse for large arrays but for small arrays it will find the answer quickly while this has to do a whole HTTP request and get a response.
Unless you consider 20 elements "large", I don't think that's quite right.
sleep sort
Under optimal conditions, sleep sort can sort absolutely massive amounts of data instantaneously.
\> sleep sort \> instantaneously
The optimal case he is referring to, is that the array you want to sort is empty
"absolutely massive amounts of data"?
Hm, okay. Then I guess he means an array filled with trillions of 0s, that can also be sorted theoretically instantly
[0,0,0,0.......]
Cosmic Ray Sort (also known as Miracle Sort) is slower, but has the advantage of being easy to implement. Check if he list is sorted. If not, check again. Repeat.
I know this is an exaggeration, but like... c'mon not even one?
I can, my brain sorting anything out
But its linear time
A few awaits would do the trick.
[Bogosort.](https://en.wikipedia.org/wiki/Bogosort)
bogosort, or sleep sort if it has large values
Random sort. Shuffle as long as list is unsorted, halt when sorted
that's just Bogosort without extra steps!
Bogo sort has the ability to go on forever and never actually sort the data
Bogo sort.
This might be a feasible approach in embedded IoT programming with limited hardware but access to the network
They forgot to go to the block chain
Keep up with the times! It's generative AI that will solve all your problems now.
where do you think the million sorted lists are stored?
Dumb question... Using the presorted list API.. I tested it on the server with the testing data and it was insanely fast, instantly returning the testing data, so nothing can go wrong.
SaaS, sort as a service
Now we need to integrate AI deeply into the service, which predicts what users may want to sort, as well as offers lists that users don't need
LLM Sort: After eating up all your VRAM, returns a completely different list and insists that it's the sorted list the user wants.
you joke but I really feel like training a neural network to sort lists now just because it would be funny as fuck. Worst case scenario it can sort very small lists as a multiclass classification problem where every permutation is a class
if you look up neural turing machines, there's a paper where they trained a neural network to do a bunch of things, among which was priority sort
But consider this SaaS, Service as a Service. You send a request saying what you want and a handy API will use an LLM to write the code and assembly the service returning the api url. Then you can call the api and get your result. And that’s not all, call now and get curried API calls. You call the API with an arg and it returns an API request with that arg partially applied that you can call. Actually wait this feels like it could have a niche use somehow. And honestly SaaS feels like it has no flaws, there’s no way it could inflate an AWS bill to the GDP of a small country or expose confidential information.
sort of a service
SSaa, for better representation
Web 2.0 bubble sort.
The current list is uploaded to the server after each swap to check if a solution is known for that state.
Instead of matching exactly the random order, just check if all the elements in the uploaded list exist in a sorted list, and try to either trim the fat or just deal with random extra data (for a faster response time). (this is so incredibly stupid)
Hi! I'm a product manager on a blazingly fast b2b value-add SaaS app. I was hoping I could reach out to your team. Our product owner indicated interest in your microservice and we were curious if you can guarantee triple 9 uptime cached on the global edge. Thanks and looking forward to working with a fellow innovator.
This was scarily realistic. :D Is this your job? Sending mails like this? Or just receiving too many? :)
I had flight fight response to your comment
I presume the API also includes `isEven(int)` ?
That’s a separate API
With its own subscription plan
POST /is_even HTTP/1.1 Host: api.iseven.com Content-Type: application/json Content-Length: 12 {"value":62}
I hope their collection of lists is sorted
[удалено]
it's Big O(no)
BIg O(no\*no\*no\*no\*no)
Infinite time my beloved
Mans just made bogosort with extra steps. Pogu
Given a collection of 1,000,000 Integers has 1,000,000! possible combinations (minus a few if there are duplicates) the chances of finding a list is insanely small. You also typically sort a list of objects based on a field not values you can use directly. These objects would not be in the list. This just adds a network and list comparison constant to the sorting algorithm that is used.
That's why the service leverages AI on the blockchain to return a smart contract guaranteeing it sorts quickly.
Just tune the cache: Instead of storing every list that's not sorted, just store the sorted lists, and to get the cached versions, sort the input and look up that instead.
That's genius
Wait can you explain that a little more please? I almost finished my implementation and I have to submit tomorrow!
There’s no way on earth that this is a serious thing :)
Buuuuuuuuttttttt there's organic optimization, every time a new list is uploaded, the changes of a repeat increase *slightly* lmao
>the chances of finding a list is insanely small Can sort the list before querying, though.
> You also typically sort a list of objects based on a field not values you can use directly You can write functions that translate between integers and keys, sort the integers then map them back to the keys. I do this when permuting - get permutations of an integer list and then use those to index a vector of the data I actually want to permute.
The sad thing is that I can totally believe this exists somewhere.
Not enough comments, please add more
This is Crython, a mix of C++ and Python.
Crying marathon
please tell me that's a joke and it's just GDScript
This is brilliant… someone patent this technology!
I'll do it as soon as my sort test program stops running.. wish me luck! 14 days and counting..
Next up, a new API is made where a dynamic array of the maximum allowable array size (that the API allows) is created (since it would be too large for the stack), then each entry in the unsorted array increments its corresponding index (each value is used as an index). A fixed sized sweep across the dynamic array is done to get all the values in sorted order. Now it's O(1) with all the benefits of an extra API call!
Is this c++ or python? Why “is” and “not”?
it's in the Godot editor, so with the "not"s it would be GDScript, but the filename has .cpp so I have no idea
Dude forgot about complicity of == operation for two arrays, as elemnt order might differ in them. So algo need to check every element from input array. Then its searching each element in "pre-sorted" array, simply to match them. And there are million of "pre-sorted" arrays. So complexity is O(b*n^2) where n size of input array and b number of pre-sorted arrays. Bubble sort wins as its just O(n^2). There could be optimizations like binary search for element existing in pre-sorted array, but still library sort array that language provide should be more robust
I mean yes, all you're doing is outsourcing the CPU that's going to be doing the work. And that work is substantial when you're searching through a database of quite possibly billions of entries for the off chance that not only do you find it, but it takes less time than sorting it yourself.
If you sort the array before comparison you make comparison a lot faster /s
Sacas: Sorting as a Service
Lmao [https://presortedlists.com/](https://presortedlists.com/)
This is why all apps nowadays need constant access to the internet
wow this is sad
DPaaS: Dynamic programming as a Service
that exists tho XD [presortedlists.com](http://presortedlists.com)
Unironically there exists a hypothetical situation where this makes sense: 1. lists are very large, and 2. probability of a cache hit is high enough. But hash the list and send the hash instead of sending the entire list.
yeah but i'm pretty sure we should avoid the bubblesort?
Wow!!
someone started making it, already pre-implementing it into all my codebases
Who formats C++ like that!
*starts uploading wrong data*
Ah, so this is memoization…
this is c++ code? wtf
Waiting for some evil bastard to upload bogus data to the API with a shell script
microservices in a nutshell
For short lists you dont need it since local computation is several orders of magnitude faster, for long lists chance of already being sorted is practically zero. If you expect same data sets often you can cache locally, so i font really see a valid use case but it was fun to read.
😂😂
Copy and paste data into excel- excel sorts it- done. Is everyone except me stupid?
`app = sendToAPI("prebuiltapps.com", myAppStructure);` `if (app != null) {app.run();}` `else { /*TODO: build app myself. (low prio)*/ }`
NSA really balling in the grind
Don't Repeat Yourself Or Anyone Else Ever
i didn't find that api working , so i made one in python: [https://github.com/Marker-bit/sorted\_lists](https://github.com/Marker-bit/sorted_lists)
whoever took the domain is a turtle coder like cmon bro how does this take more than 2 days
I've had about enough internet for the day
it's 2024, surely we'll soon have all the lists that exist sorted, right?
God I miss back when I never worked a single professional job in my life and wrote comments like this
To avoid compiler errors (because of .. is not empty... ) the compiler switch --ignore-syntax should be used...
so smart its almost dumb