10 FORBIDDEN Sorting Algorithms
Vložit
- čas přidán 18. 05. 2024
- If you to upgrade your workstation too, don't miss their sale now and use my code ''YTB50'' for $50 off on order over $500.
FlexiSpot E7 standing desk: bit.ly/44VUYtr - US
bit.ly/46Vvluo - Canada
In this video, I explored the realm of impractical sorting algorithms. Say goodbye to the usual and practical methods, and join me on a journey through a collection of algorithms that are downright wacky. We'll have a laugh while shedding light on the inefficiency and pure silliness of certain sorting approaches.
Chapters:
Introduction - 0:00
Sponsor - 1:08
Stalin Sort - 2:40
Sleep Sort - 3:17
Slow Sort - 3:59
Bogo Sort - 4:45
Bozo Sort - 5:20
Bogo Bogo Sort - 5:40
Quantum Bogo Sort - 6:28
Schrodinger's Sort - 7:09
Intelligent Design Sort - 7:41
Miracle Sort - 8:22
Outro - 8:53
💻 Instagram: / im.ardens
💻 Discord: / discord
💻 GitHub: github.com/myNameIsArdens - Zábava
If you to upgrade your workstation too, don't miss their sale now and use my code ''YTB50'' for $50 off on order over $500.
FlexiSpot E7 standing desk: bit.ly/44VUYtr - US
bit.ly/46Vvluo - Canada
YO WHAT!? Never heard of FlexiSpot in my life until 3 weeks ago when I bought my E8, and I must say that I regret absolutly nothing 🤣
There is also Silly sort... and yes I have built afew custom ones... my joke one is known as child sort.... as I remember... 430,250 comparisons to sort 20 elements
Flexispot is collecting youtubers like infinity stones.
Crushed like a submarine brother 😂 2:15
Make a video about algorythm in general. I have no plan, how to create one actually 😬😅
Gaslight Sort:
- Take unsorted list.
- Tell user, it is already sorted.
eerily similar to the intelligent design sort
Someone else came up with this 3 months before you. :(
Gatekeep Sort: Don't let the user see the list.
@@sakesaurus1706I love that these two statements have very concisely deconstructed the "God's plan" line of religious thought
So Gaslight sort basically equals intelligent design sort?
Thanos Sort: Randomly remove half of the elements until all the remaining are sorted.
Edit: since so many people asked, I think if there were an odd number of elements, round the number to be snapped to the nearest odd, making the next even again
Tezcatlipoca Sort: you copy the sorted list using a smoking mirror to see into the future where the list is already sorted.
So mergesort without the merge part 😂
Worst case:O(logn), where you delete everything but 1 element.
@@tapist3482 Sorry, but deleting elements takes also time not to speak of checking the remaining list if its sorted. Discarding the half randomly if it's not sorted. So for the worst case:
You have N elements, you check if the list is sorted, that's N-1 steps, then you discard half of it, that's N/2 elements to be deleted.
Now, you have N/2 elements, N/2-1 checks and you discard half of it again, that's N/4.
...
You have 2 elements, that's a single check, you remove an element.
You have 1 elements, that's a single check, you have finished the Thanos Sort.
That's a total of sum(2^m+2^m/2)+1, where m=dlog2(N)..0 = ~3N => O(N), (dlog2 stands for discrete 2 based logarithm), almost same as Stalin Sort, but with more expected casualties, and it seams to be 1.5 times slower in the worst case.
@@AlexM1983DHUN You're right. I really missed the part where the algorithm is still meant to sort stuff, so the checking step is necessary.
I'm a big fan of Intern Sort. Whenever something needs to be sorted, a ticket is created and sent to an intern to manually copy and paste the elements back in the correct order.
Except their Jira access has been revoked for some obscure reason and another support ticket has to be opened first to reinstate access.
@privacyvalued4134
and after that the ticket is closed with a "wontfix" because the unsorted list is already in the expected order.
Isn't that just how Miracle Sort actually works?
@@alaeriia01 no, miracle sort is more like if you never create a ticket but still expect the intern to somehow know your list needs sorting and regularly check if they ave done so
In my office, actually employees don't have access from day 1 for over a month, meanwhile interns gets their access immediately @@privacyvalued4134
Preplanning Sort:
Input your initial data in a sorted order in the first place, thus removing the need to sort it.
O(0)
That's kinda the argument of sort by intelligent design
This actually exists and is called an insertion sort
@@FoxSlyme what?? Insertion sort is an actual algorithm people use
@@kooskoos12345 yes that's exactly what I'm saying
Moving Goalpost Sort:
Take an unsorted array [8,1,6,0], re-define all numbers in mathematics so it is now sorted which means [8
O(n) runtime, how amazing! No elements removed as well!
@@californium-2526 O(0), in fact. The entire sorting algorithm is a no-op (just like intelligent design sort. Oh wait. Those are actually pretty much the same sort.)
Similar is Tao sort, which, given a list to be sorted, returns a new ordering method where they are already sorted.
@@neopalm2050 well, technically it is O(n) because you need to actually read the array to define the numbers
@@incription Not if the "redefining" is done at compile time (meaning the type changes rather than any actual data).
Miracle sort is basically me checking my empty fridge every hour or so to see if, miraculously, some food spawned in.
Miracle Sort, also known as the "Thoughts and Prayers" Sort.
My first action when get back home is always check the damn fridge. And sometime the food (also drink) spawns into :v
or a girl, if you are Delhite enough.
I recall learning about very fast sorting algorithm in my algorithms class which I surprisingly haven’t seen mentioned here.
Multiply the entire array by 0 and now it’s sorted. I think it should be called “Kachow” sort because of its speed:
Sort the list:
["cow", "dog", "pig", "you😂"]
@@Farzriyaz[“”, “”, “”, “”]
This reminds me of how when I was learning to balance equations in Chemistry, I would do so easily by writing 0 in front of all compounds
@@Farzriyaz [NaN, NaN, NaN, NaN] looks sorted to me 👍👍
@@Farzriyaz[]
overwrite sort:
set the value of the 1st element in the list to 1, the 2nd to 2, the 3rd to 3 and so on until you reach the end of the list.
Miracle sort can actually work:
With an extremely low probability, cosmic rays could flip enough bits in memory to eventually result in a sorted list, that, with an even lower probability, might contain the original elements.
The downside is that with a much higher probability, other bit flips occurring during that time will crash the program.
Another downside is that just like Bogo Sort, Miracle Sort is not guaranteed to halt.
Mario 64
In 2013, a Super Mario 64 speedrunner experienced what is thought to have been a single-event upset, where one bit that defined Mario’s position flipped, teleporting him up with no known side-effects.
bogo sort is garanteed to halt by the infinite monkey theorem, just not in a reasonable amount of time. for miracle sort, I guess if you assume a constant flow of cosmic rays and infinite time, it could be garanteed to halt too
@@pedropesserl neither is guaranteed to halt before the heat death of the universe. You need infinite time to be sure they halt, which’s fine for bogosort: it’s an abstract algorithm, it can run in the infinite universe of mathematics.
You can’t do the same with miracle sort, though. It only works if it’s a physical computer with transistors and stuff that lives in the Universe, so the algorithm itself can only run until the heat death of the universe.
@@felipevasconcelos6736 that's exactly what I meant
Why not combine thread sort and bogo sort? Shuffle the array, create a new thread for each element, and use that to check if they are in the right order.
The most complicated useless thing everrrr 😂😂
I guess if you had a few millions threads this could be very fast xd
This but with Quantum Compute 🤔
@@sword0948 forkbomb moment
That's like my idea, make it so any correct group like "OPQ" is made into one element then randomoze the sequence again. This is exponenionaly better, because the sequence slowly shrinks untill it is 1 element, making it end.
Bruteforce Sort:
1. Create an array of all possible n! permutations of the array to be sorted
2. Mark each array as "sorted = false".
3. For each array, make sure that each of its elements is not less than the previous one. If so, mark the array as "sorted = true".
4. Filter the array of arrays using "array.sorted === true"
5. The first element of the filtered array of arrays should be your sorted array.
Hooray, O(n!), my favorite!
Quantum sort: Bomb it with cosmic rays, eventually they'll bit shift into correct order.
@@glumbortango7182 most sort algos are O(n) for memory consumption, This one is uniquely bad because it's a factorial in both time and memory usage lol.
You can make this worse. How do you iterate through all possible permutations.
Well, pick each possible element as the first element. Then sort the rest with brute force sort. So in python that's
def bruteforce(x):
y=list(permute(x))
for i in y:
for j,k in zip(i,i[1:]):
if j>k:
break
else:
return i
def permute(x):
if len(x)==0:
yield []
return
for i in x:
for j in permute(bruteforce(list(filter(lambda j:j!=i,x)))):
yield [i]+j
@@fragileomniscience7647thats miracle sort, basically.
Futurism sort: Waits until a perfect sorting algorithm gets invented.
I'd like to propose "The Liar's Sort". This is where you have two machines with the same data. You let one machine do the actual sorting, and once it's done, you use the completed sort to sort the data on the second machine, making it look like it was sorted in one cycle.
Alternative title: Reaction CZcamsr sort
Amusingly, the "thread sort" mentioned in the video is technically a version of this algorithm. (The thread sort relies on the OS using its own (different) sorting algorithm to order the wake-up times of the threads, so it's technically not sorting anything itself at all, it's just taking the output of a different sorting algorithm (with a few extra steps) and presenting it as its own).
Isn’t that kind of just “intelligent design sort”? The other computer is the intelligent sorter.
No joke, that is basically what happened as the "draft" of the Human Genome. Celera used the public HGP data, digitslly chopped it up into "faux read" data, and then reassembled the data and declared success. But, they did not randomly sample from the pool of faux reads, thus the set contained all the necessary information to reconstruct the sequence.
John Sulston spent 10% of his 2002 memoire describing this big lie.
A variation on that is the Liar's Homwowrk Sort where the machine reports that the sort was successful. When pushed for the data it stalls for time while it sorts the data in Google at the last minute
Random construction sort:
1. Construct a random sorted list.
2. Check if the sorted and unsorted list contain the same elements.
3. Repeat until a match is found.
I'd like to propose the names monkeysort or typewritersort for this process, in reference to the infinite monkeys on infinite typewriters writing Shakespeare thought experiment
Or, a more absurd version. Generate a random list. Check if it is the sorted version of the original list. If yes, halt. If no, repeat.
@jasperbarnett6819 but to check, you would need a sorted version of the original list, eh? XD
@@jackik1410 no, you would just need a copy of the original list (unsorted). Then just run two checks: one, that the generated list is sorted, and two, that it contains each element of the original list, and nothing else
@@jasperbarnett6819 right, fair point, two checks
The Bethoven sorting:
It takes each element of the array and compares with a note of the Beethoven's 5th
If the note is ascending, it changes it with the next value, if it's descending it changes with the previous.
At the end of the array check if it's sorted, if not, continues the song on the beginning of the array, until it's sorted (the song goes in a loop)
Is that guaranteed to eventually work?
@@gaysarahk if the list length is divisible by the length of Beethoven's 5th, and does not sort on first pass, I'm pretty sure it now loops forever
Bum bum bum buuuuuum!
@@gaysarahkno. In fact, not only is it not guaranteed to halt; it’s highly likely to never halt.
Here are a bunch of O(1) sorting algorithms:
*Dictator Sort:* Select the first element of the array by position and remove the rest of the elements because they are inconsequential. The downside is that there is now only one element in the array but it is always sorted. Unfortunately, the dictator also becomes a peasant by position.
*Peasant Uprising Sort:* Select the last element of the array by position and remove the rest of the elements because they came before your element's position. The downside is that the peasant becomes the dictator by position.
*Jesus Sort:* Select either the first or the last element of the array. The least position shall become the greatest or the greatest position shall become the least in the kingdom of one element arrays.
*Nazi Sort:* Randomly select one element in the array to survive. This sort is terrible for many reasons that should not have to be explained.
Here's what I got from that:
class NaziSort {
// Nazi Sort implementation
}
class JesusSort extends NaziSort {
// Implementation
}
class DictatorSort extends JesusSort {
// Implementation
}
class PeasantUprisingSort extends JesusSort {
// Implementation
}
this guy is a genius
Laughed so much... 😂
Dictator Sort and Peasant Uprising Sort are O(n) due to removal of the remaining elements
*Batman Sort:* Print “Because I’m Batman.” The list is now sorted, and anyone who says otherwise must be insane and will be sent to Arkham Asylum.
Political sort - have an unsorted list, say [9, 7, 1, 3, 4, 0, 8, 5, 2, 6], proceed by actively lobbying governments in all countries in the world to change meaning of the written numbers so that the list would appear sorted. E.g change the meaning of '9', so it's actually 0, '7' is actually 1 and so on.
That's messed up...or maybe you could argue and continue to make sure the whole computer or pc would believe the same thing to be true
pay2sort
That would require a world governing new world order to effectively make those changes, so literally 2618
I commented the same idea, sorry
@@Nugcon countries could sign treaties it have a common meaning for those lists without one body being in charge of everybody.
Undefined Sort: Mark the space in the memory used by the list that is to be sorted as free and then check up on it after the computer has had time to reuse the memory space and hope that whatever happens to be in memory is the sorted version of the list.
It would probably be very hard to implement this, because the program would have to be able to get access to the same section in memory repeatedly. However, a similar method would work and is actually insanely easy: malloc with the desired amount of bytes, check if the allocated memory is in order, if not, malloc again. Do this until you run out of memory or an ordered list is found in memory.
Why am I giving this any serious thought? I have no frickin idea.
If Bogosort and Miracle Sort had a baby. A hideous, hideous baby.
I love a sorting algorithm that can corrupt data from entirely different processes
A more practical Miracle Sort... I like it!
@@catsnorkel well, you wouldn't corrupt it, because you're just reading it
Solution to Sleep Sort's issues - divide all numbers by the largest possible value able to be stored in the device's memory, reducing them to decimals between the value of -1 and 1. Then, add to each number 1, so the possible values are between 0 and 2, then use Sleep Sort. I'm fairly certain this will be O(n).
Well it's correct, but at this point you can just do bucket sort instead.
bro out here with big brain
Change the sleep timer to system ticks instead of seconds.
Mutation Sort: Works by "mutating" the items in the list until they all fit
The algorithm will loop through the items and check each item to see if it is less than the previous item. If it is, it will increment the item by 1 until it is bigger than the previous element.
How about a gravity sorting algorithm where you start an entire physics simulation and give each item a density based on its value where the list is then sorted based on each elements position in a liquid
Negative numbers:I believe I can fly
Does zero just stay in the air?
That's kinda like the counting sort, where the problem is with big numbers
there is a sorting algorithm called gravity sort
This is a real sorting algorithm that is actually useful for some sorting problems (where there is a huge amount of data, an answer is needed quickly, and the precision of the answer isn't that important - only most elements need to be in the correct position).
Yes Man sort, which is even faster than BOGO sort
Given an unsorted set, the algorithm randomizes the set and reports that the list is in order, regardless of whether or not the set is actually sorted.
This is potentially faster than BOGO sort, because in the instance that it does happen to be in order on the first try, it doesn't waste time checking if it is in order.
This does have the downside of occasionally ending before the set is sorted.
occasionally
Quantum bogo sort works just as fast and has no downside, as long as you follow the right quantum branch.
Hard sort:
Return an hardcoded sorted array.
Given any array, it will return a sorted array in O(1)
@@fenec250true...i always use quantum bogo sort despite the desperate wails of mercy from all the beings in the parallel universes we just destory.....its just too fast to not be used
Blind Man sort, even faster, just returns the array, doesn't do anything to it, theoretically has a notation of O
Over the years, I've become a master of miracle sorting my problems in my life.
Last one is quite similar to Cosmic Radiation Sort, where you wait for the cosmic rays to bitflip the values in the array such that in the end they appear sorted
Frick i just commented this
(Proposing cosmic ray sort)
I've genuinely never heard that it exists lol
2:40 Seek and destroy
3:17 zzzzzz
4:00 *Better* mergesort
4:46 Theoretically the fastest sorting algorithm that exists
5:21 Bogosort but slower
5:41 Bogosort but Bogoer
6:28 Bogosort but with *serious* concequences
7:09 If I don't see it, it's not there
7:41 If it ain't broke, don't fix it
8:24 yes
The last one is literally just checking the fridge in the middle of the night to see if more food spawned.
@@malkrie1444 I feel so hurt that miracle sorting my fridge at 2am doesn't work.
I find sleep-sort really interesting.
@@malkrie1444more like waiting for bit flips
6:28 bogosort but quantum Stalin sort
At university, me and a few others worked with a group from our physics lab. They wanted to design a robot for an hypothetical Experiment with radioactive sources.
During this we came up with the idea for radiation sort:
You take your array, dump it into a poorly shielded memory, push that next to a strong radiation source and wait until the radiation causes enough bits to flip so that you know have the data in Order
Now that i think about it, given that the data would be destroyed and recreated in the process, this could also be called Theseus sort (as in ship of theseus)
I like the name Theseus sort
TBH every sort is kinda Theseus sort if you think about it
This is literally miracle sort that utilizes cosmic radiation flipping a bits but at a much higher rate.
It seems to me more like a monkey's typewriter sort.
Or perhaps the Library of Babel sort.
They could use it for actual rng for better security, as the damage is probabilistic (right?)
Hey, Sleepsort CAN sort negative numbers. I implemented a solution to that in Bash a while ago.
Basically, first we go over the list and check if we have negative numbers, and if so, what the lowest negative number is. Keep that number in mind (say, -55). Then we add the positive (so 55) to all values in the list. Then we run sleepsort on the list. Then we subtract 55 from all values in the sorted list. Then we're done. :D
It wouldn't be simpler to check if there are negative numbers, add the absolute value from the lowest number and start from there?
@@jagerwolf5821That's... what the comment said to do. I don't understand the confusion.
@@jagerwolf5821 as it turns out that is precisely as simple as what the man above said.
couldn't you just sleep sort negative numbers into their own list based on their abs value. Then reverse the negatives list and append the non-negative part to it?
But then if your numbers are declared as a limited size type (like 64 bit integer), you have the risk of a really big number flipping negative due to that addition.
The way "miracle sort" made me burst into laughter at 5am after an all nighter...
You forgot worstsort. The idea is that if we have a list of every permutation of the array then in that list of permutations is the sorted array. So if we sort the list of permutations then at the start will be the sorted array, but how do we sort the list of permutations? How about we use worstsort.
So a fork bomb.
zip bomb of sorts
So O(nn!)
Forget the halting problem, this never even begins
@@charliekahn4205No it's, O(infinity)
Lookup Sort: Precompute sorted versions of all possible input lists and store them in a hash table. Then just look up the input in the table. Uses a lot of memory, but it's really fast.
Finally a O(1), working, (not) efficient sorting algorithm.
Mmm password rainbow tables.
@@ferdinand.keller no, hashing a list is O(n) I think
@@LB-qr7nv Ha, true, it’s O(n). You are right.
Important clarification: it's very fast _at run-time!_
Brutesort:
You put in an array, and the sorter makes EVERY possible combination.
It marks each one either as sorted = false or sorted = true depending on if they’re sorted or not.
The ones that come out as true get put into a new list while the ones marked as false are discarded.
After that, it randomly picks one of the sorted lists and outputs it.
isnt this bogosort with more useless atempts?
@@batziii8745 There is the same probability of getting a double randomized bogosort that there is to get the sorted list at any attempt, so sure you could get the result before (n!) but you could also have the worst luck in the universe (or god hates you) and get more attempts than (n!), so with brutesort you are assured that you would get the sort after (n!) so yeah 50/50
miracle sort sounds like me doing essays back in high school
The gaslight sort: the comparator finds the corresponding addresses for the values of elements a and b, sorts them, and then always returns true. It's like saying "No no the array was always sorted."
I had the same idea. In theory, if you just convince yourself that the data is already sorted and doesn't need to be resorted, it's technically the fastest possible sorting algorithm (but also, the least reliable).
Naw, the real gaslight sort is to overwrite the list with another list that is already sorted and return true. "No, no, this was always the input list, you didn't really see an unsorted list."
I would say stalin sort actually is used in practice.
If you have a stream of data where you only need the most up to date value, if packages come out of order, you throw away any older packages than the latest you accepted.
Its not quite sorting since you do not have the whole list up front, its rather a filter, but its using the same algorithm :)
Also could be used for begining an insertion sort.
It's also useful for situations like building a tree from a key-value list that is *supposed* to be sorted so you can do it efficiently. To ensure that your own output is valid you have to stalin sort to at least the first nonconforming element, at which point you can either send it to gulag or error out.
@@priyanshugoel3030now I want to make a sorting algorithm that repeatedly uses Stalin sorting with multiple “gulag” arrays so that no data is lost, and then using the gulag arrays to re constant the original array in a sorted manner
@@frozenheartedgiant8330 Resurrection Sort
The infinite tournament: you start by setting out a tournament, where you compare the contestants to each other, and the larger number moves to the next comparison (just like in a tournament). at the end, you get the largest number. Remove that number from the list, and repeat the tournament. Repeat until only one number is left. Remove that smallest number and add all of the old big numbers back in. Repeat this process, every time removing the smallest number, until only one number is left. It is the largest number. Remove that number, and add all of the small numbers back in. Repeat that process until only one number is left. It is the smallest number. Repeat that process until only one number is left...
This is sounding like a back-and-forth version of heap sort. You left out your exit condition (everything sorted).
@@danuttall i left the exit condition out on purpose, thats why its called the infinite tournament
Not sure if this has been proposed yet: shuffle sort.
1. Select two random, non-overlapping sequences of the array, of the same length.
2. Swap them.
3. Check if the array is sorted. If not, go to step 1.
Or: reverse sort.
1. Select a subsequence of the array.
2. Reverse its order (swap last and first numbers, second-last and second, and so on.)
3. Check if array is sorted, if not repeat from step 1.
Monkey sort.
1. Print the unsorted list.
2. Hand it to a monkey.
3. Have the monkey retype the list. (Into a computer to save time.)
4. Check that the list is sorted. If it is, give a banana to the monkey.
5. Optional bonus step: check that the list has the same number of the same elements as the original list. There are a few ways of doing this; for extra points sort the list using bogosort or similar for comparison (then throw the output from bogosort away; we can always regenerate it next time it is needed.)
Just one correction. Time complexity actually doesnt tell you how fast an algorithm is. It just tells you how much slower it gets with more data. If you had an infinite amount of data, then time complexity would be very accurate, but that is not real life. Algorithms that have a better big O notation might actually be a lot slower with less than a million data points.
Also yes it's a nitpick, but I do think it is very important to have correct information out there for everyone. A lot of people get this wrong and use hashmaps for arrays with 10 entries.
Bogosort has time complexity O(1)
@@paladynee O(infinity) because big O works off of worst case senario
@@doppledah its actually O(n!) It takes the average.
"If you had an infinite amount of data..." If you're unashamedly nitpicking, this should be something more like "As the amount of data increases without bound".
*brazilsort*
inspired by stalinsort, but instead of deleting nonsorted elements, it sends them to brazil.
all nonsorted elements get moved to an auxiliary array (aka brazil), with only sorted elements remaining in the main array. then, we do the same process with the leftovers, moving all nonsorted elements in the auxiliary array into yet another auxiliary array. we repeat this process until all of our arrays are sorted, after which we merge them back into the original
the way we do this is as follows:
take the smallest element of each array. if theres just one, then that ones the smallest, if theres two, compare them and pick the smallest, if theres more, recursively brazilsort them until you find the smallest one. the element you picked is the smallest overall and is placed first in the final sorted list. the whole process is repeated for every element
*example*
2 5 0 7 6 1 4 9 8 3
2 5 7 9 / 0 6 1 4 8 3
2 5 7 9 / 0 6 8 / 1 4 3
2 5 7 9 / 0 6 8 / 1 4 / 3
~
2 0 1 3
2 3 / 0 1
~
2 0
2 / 0
0
the first element is 0. not feeling like doing the rest of it but thats basically it
2 5 0 7 6 1 4 9 8 3
2 5 7 9 / 0 6 1 4 8 3
2 5 7 9 / 0 6 8 / 1 4 3
2 5 7 9 / 0 6 8 / 1 4 / 3
2 0 1 3
2 3 / 0 1
2 / 0
Result: 0 _ _ _ _ _ _ _ _ _
2 5 7 9 / 6 8 / 1 4 / 3
2 6 1 3
2 6 / 1 3
2 1
2 / 1
Result: 0 1 _ _ _ _ _ _ _ _
2 5 7 9 / 6 8 / 4 / 3
2 6 4 3
2 6 / 4 3
2 6 / 3 / 4
2 3 4
Result: 0 1 2 _ _ _ _ _ _ _
5 7 9 / 6 8 / 4
5 6 4 3
5 6 / 4 3
5 6 / 4 / 3
5 4 3
5 / 4 3
5 / 4
Result: 0 1 2 3 4 _ _ _ _ _
5 7 9 / 6 8
5 6
5
Result: 0 1 2 3 4 5 _ _ _ _
7 9 / 6 8
7 6
7 / 6
Result: 0 1 2 3 4 5 6 _ _ _
7 9 / 8
7 8
7 / 8
Result: 0 1 2 3 4 5 6 7 _ _
9 / 8
9 8
9 / 8
Result: 0 1 2 3 4 5 6 7 8 _
9
Result: 0 1 2 3 4 5 6 7 8 9
I wonder how would change performance if you just put Brazilians in front and repeat
It's kind of stupid, but in a smart way. It makes the unmatched elements a problem for later and sorts rapidly through each chunk by moving everything out of the way. It's like a "I'll worry about that later" sort.
@@pal181 im not sure it would affect performance that much, but itd certainly save a lot of space. kinda goes against the spirit of making an awfully bad sorting algorithm
but thinking about it, if you pair that with a more sensible way of merging it all together, it may actually make for a decent sorting algorithm
That sounds actually quite good algorithm, if you start with almost sorted list.
I like sleepsort with the sigmoid transformation. It's like sleepsort but works on negative input and always finishes in 1s, regardless of input size.
It could even finish in 1 millisecond if you wanted it to! Whether the precision of thread timing is up to the challenge remains to be seen.......
2:17 "So that your stuff won't get crushed like a submarine"
imo dark jokes are the funniest kind when they're performed well
Edit: wrong timestamp
Usersort: Ask the user to use the upstairs and sort the array for you. You can optionally make an intuative GUI for it
hear me out on this one: UserBogosort. It randomly shuffles the elements in the list, but instead of checking itself whether or not the list is sorted, it asks the user instead.
bonus points if the list is shown in the smallest font possible and the user has to manually type "true "or "false" every time.
my boss uses that algorithm, except instead of an intuitive UI it's 4 separate broken programs each with a different terrible UI.
@@KX36 Is your boss a Unix nerd?
@@SharpBritannia no, i work in the NHS so inefficiency is key. you don't even want to know how much we spent on those programs.
@@KX36 God save the King, And the NHS off Tory hands
There is always a recursive Genetic Sort.
Base case, if the input is already sorted return the list.
Next copy the array into a second array and randomly mutate the copy by swapping two elements at random. For both arrays, call a fitness function that returns a score based on how many elements are sorted relative to their neighbors.
If the new array has a better score, recursively call Genetic Sort passing the new array.
If the new array has a worse or equal score, recursively call Genetic Sort passing the original array.
You might try a variation of this in which the genome is a set of instructions related to sorting a list, e.g. "assign index 5 to X" or "swap elements X and Y", and whichever randomly-generated algorithms do the best become the parents of the next generation of sorting algorithms.
I actually had something similar as an assignment when I took a C++ course on my CS degree.
The viruses were vectors of the same numbers and they "evolved" as individuals and as a group toward a target virus by random inner swaps.
It was cool and pretty simple.
This is one of the least inefficient proposals.
Cute.
Sounds like slightly smarter bozo
* *List is already sorted* *
Create a copy. Mutate. Compare. Survival of fittest. Repeat.
Haltingsort: store the list in memory in any form, generate a random pattern of bits and treat it as an executable program, run the program, and check if after the program has halted the list is in order by comparing all neighboring elements. If not, generate another random program to execute and try again. If the program doesn't halt then this never sorts, so if it can be determined not to halt, then skip that program. Fortunately there is no general way to determine that for all random programs, so at least some will run, and at least some will lead to an ordered list.
Unfortunately, the program may generate a totally unrelated ordered list and stop, but hey, nobody remembers the original list then anyway.
(The procedure may still not halt btw, we just won't know that.)
5:56 Captions: "It's the biggest piece of dogsword" XD
Captcha sort: devide the array in smaller pieces, and present them as a captcha on online forms. Combine the results.
Similarly: Amazon Mechanical Turk Sort (this one is more expensive. Not necessarily in space or time, but in actual dollars)
You can extend the sleepsort to work with negative numbers. Just take the absolute of all the numbers for the sleep and then iterate over the array once backwards, putting each negative number in order in front of the array.
or you shift the sleepingtime of all elements by the size of the smallest negative number
@@Muretobut that wouldn't be efficient.
@@mathijsfrank9268 do you really think that's an issue?
@@Mureto what algorithm would you use to find the smallest one
@@autisticboi2992 you start doing a somewhat sensible thing and figure out what the highest and lowest numbers are, perhaps by remembering the highest and lowest number seen as you look through the list. (you could also perhaps scale the sleep times based on this, but lets not get ridiculous)
"Won't get crushed like a submarine" ... that went so smooth I almost didn't catch it.
Castle Doctrine Sort: Every entry is assigned a number based on its value, it them looks at that number in the list and deletes any entry that is in that spot and takes its place.
Duplication-Bogo-Sort: it'd use bogo-sort and if its wrong, it duplicates all elements and tries again. That way, there is a 33% chance to not even solve a 2 digit array in infinite time. And 3 digit would have a 60% chance to never get solved
bogostupiditysort: if its not sorted it randomizes it, and if its not sorted after the randomization all of your data gets set to 0, basically sorting it.
It’s not a bug, it’s a feature!
Multiverse Sort:
Imagine that multiple parallel universes exists with small differences, then you find the universe where the meaning of “sorted” is the array itself, delete all other universes and you have a sorted array.
3:06 I see no way this could cause any errors.
Assimilation sort:
Take the first element in the array and duplicate it to each position in the array. The array is now sorted with a (X-1)/X error rate. For example, if you Assimilation sort 3,5,4,2,1 then you get 3,3,3,3,3. Which is a 4/5 error rate.
Actually, 34563 would only have a 3/5 error rate, so the method is better than you thought
@kaijuge6934 That is true. The more duplication in the set, the more accurate it becomes.
Decay sort: (Inspired by vacuum decay)
(1): Create two copies of the array
(2): Wait for a element in the array to change (using the three copies to see what was the change, as this clearly is the best way to do so)
(3): The element that changes is clearly superior and at a lower state thus every element wants to become the lower state and will become identical to the element that changed
(4): Change all elements to copies of the one changed
you now have an array of n elements, which are identical, the array has been sorted.
This, but instead of waiting, it just generates a random number and changes every element to be that random number, thus sorting the list
AdverSort (Adversary Sort)
A game takes place between two adversarial programs: one that sorts by Bubblesort (ascending) and one that sorts by Bubblesort (descending). The programs take turns applying a single iterative sorting step to the giving data and the new order of the data is stored in the memory. If a move would cause the data to end up in an order that has already been perceived, the program in question has to make a different move. If a program has no valid moves left, it loses. The winner (its adversary) then gets to carry out its own direction of bubble sort, either ascending or descending. The ordered data is returned, but which program won the game is deliberately not returned.
Child laborer sort: Take a list of unsorted numbers and send it off to a child laborer to sort it for you.
Paradox sort: let the computer brute force the sort by doing a regular comparison with every element until it's sorted and then send the result back in time just before it started, meaning you end up with the sorted array a moment before you start the algorithm to sort your array, removing the need to ever use any energy or time to sort anything.
And a useful side effect is that the computer room becomes bigger on the inside than the outside.
Sort of Future Past: Knowing that you will need the sorted array in your past future, project the sorted array back to yourself before you even knew the array existed, eliminating your own timeline.
@@ThisMightBeRyan Hmm. Can you find a Java API for that?
I edited the comment so the replies make no sense
Nonbinary sort
that's basically just intelligent design sort in a different coat of paint lol
altenatively you could call it "Gaslight sort"
"homeopathy sort"
gaslight sort
I must say I didn't expect much of this video other than a good enough watch for a lonely lunch since it's an already very used format, but this is one of the best joke sorting algorithms compilation I've seen.
Plagiarism Sort : Thats how it goes.
1. Take an Array.
2. Sort it using any of the standard sorting algorithms.
3. Claim that you sorted it using your algorithm.
My sorting algorithm (also kind of Schrodinger's Sorting Algorithm): It randomly arranges the list, but never prints out the numbers, so you never know whether it sorted it correctly or not
Stalin sort has utility in situations where you need to sort a dataset that you suspect contains falsified entries due to inconsistent indices in the 'id' category, for instance. If users[n].id is supposed to always be n+1 and you as an investigator saw that wasn't the case on a couple entries (a behavioral scientist at Harvard was caught falsifying data in that exact way), deleting any items in the list that didn't conform to that convention gives you a picture of the dataset without the falsified entries. If I recall from the bit I saw about it, the investigators in that case employed a roughly similar method to demonstrate how the raw data differed without the falsified entries.
I knew the reference you were making
@@SkyboxMonster congratulations! You win the prize!
So a filter
@@kacperkonieczny7333 Sure, but i get the feeling Stalin sort might actually be more computationally efficient than some filtering algorithms? Don't have numbers on that, but it seems like close to the simplest approach to that problem.
@@andythedishwasher1117 I meant that Stalin sort in this example was simply a filter
Stalin Sort might actually be usefull in some cases. Not for sorting, obviously, but to deal with certain corrupt data packages
It's how streaming sorts packages too... anything older than the last package received is discarded. So, yes, Stalin sort kinda is used everyday.
Randomized Sort: Randomly pick a random amount of the dataset to randomize. After a random amount of sorting attempts, check if the dataset is now sorted.
Miracle sort could theoretically work on a (somewhat more) reasonable timescale if you blast the computer with radiation. I’ve heard a few stories where a (probably) cosmic particle hit a computer just right to change a bit or something. It caused a huge issue in some country a while back where a candidate got (I think) exactly 1024 more votes than possible. Apparently some kind of particle hit the computer just right to flip a bit
and a mario speedrunner got a world record
That is absolute bongus, I hope you dont really believe that mate.
@@LockenJohny101
It was Belgium in 2003, and was 4096 votes actually, and was a single bit flip via most likely a cosmic ray.
@@MycaeWitchofHyphae Dude, computers wouldnt work if radiation could change values like that. There are error correction mechanisms exactly for that purpose.
I am not a hardware engenier and not a error correction expert, but this is common sense.
And this change of votes is just a sloppy excuse for election fraud.
@@LockenJohny101 it did happen and is a real thing.
MUGEN sort: use a hash to assign each element a character in the MUGEN fighting game engine, and run a tournament. Rearrange the array according to the results of the tournament, and check if it's sorted. If it isn't, use a different hash, and repeat the process.
(i am aware that this is basically "bogo sort with extra steps")
If you give your characters stats based on the value of the element, it might actually work somewhat reasonably.
@@PauxloE You've just turned it from bogosort to sleep sort. Congratulations!
@@tokeivo sleep sort but it's entertaining to watch
Time-travel Sort (actually even "quicker" than O(0) ):
Take an array, use whatever mundane sort on it, then modify your system's clock so that it is back to one minute before what it was when you started.
Back in uni I overheard some people I didn't know talking about the worst sorting algorithm and one of them brought up Stevesort. I have no idea if that guy was named Steve or if it came from elsewhere, but it amounts to:
1) Generate all permutations of the array.
2) Return the permutation that is sorted.
Kind of in the same vein as Bogosort but using unmanageable amounts of storage space rather than randomization.
my favorite bit with quantum bogo sort is to consider the timeline where it's been working without issue for decades, how computer science would develop around that, and the pandemonium that would ensue from various points if it suddenly stopped, or if it started to just occasionally be wrong
But for every situations where quantum bogo sort could not work once, there is a universe where it did worked that one time.
It is hard not to draw parallels to our own universe, and wonder whether we’ve just been rolling lucky dice using all the wrong methods.
@@pageturner2958 which therefore means that there is a world where it absolutely never fails and the population hails it as a god and Bogoism is practised by all living and dead things
Here's an idea: Mimungsort
Inspired by the forging of the sword Mimung in Germanic mythology. Take the array, split it up into all of its elements, mix it into flour, and feed it to fowl, especially geese. After they have digested it and pooped it back out, reforge the array and check if it is sorted. If not, repeat the process.
Asiansort:
Buy a clever Chinese kid off the black market, and let it fiddle with the computer until the array is sorted.
Tarnkappesort; Inspired by germanic mythology in wich a cape makes you invisible and 20-folds the wearers strenght:
Outsource the sorting to a 20-fold faster server that you stole from a dwarf.
cycle sort:
1. check if any elements are in the correct postiton
2. for any that aren't, put the last one in the array into the [box]
then move the last element that isn't in its position to the one who got placed into the box etc.
there is a gap which isn't filled by any element, so we replace it with the element which recently got placed into the [box]
3. check if the list is sorted
if not, return to step 1
The wikipedia sort. The algorithm publishes the unsorted list on wikipedia, and waits until a user edits the list. After a user edits the list, a wikipedia admin checks if the list is sorted. If it isn't we wait for another user to edit the list. A variant of this algorithm could include admins reverting changes for various reasons, as well as adding templates at the top of the page telling that "this list needs to be sorted".
Rowhammer-sort: don't read the array, but the DRAM rows next to it to induce bitflips in the array until it's sorted.
Here are some of my ideas:
Zerosort: For any array A, return an empty array.
Onesort: For any array A, return array B containing any randomly chosen element from array A.
UBsort: For any array A, if A is sorted, then return A, else behaviour is undefined.
UBsort is the best
the simplest implementation for UBsort is Hopesort (Hope the array is already sorted, and return it)
You would be surprised how often UBsort is used in real life. Usually because an algorithm that assumes a sorted list is given a list that isn't sorted..
@@Carewolf Yeah, i accidentally wrote it last week actually. I gave qsort a comparison function that always returned 0 (meaning A == B), because i forgot to change one character, resulting in nothing being done. This was a problem because i used bsearch on that same array later in the program, assuming it was sorted.
Snowflake sort:
Identify as sorted array, and anyone that says otherwise is an offensive, triggering, racist, bigot, sexist, LGBTphobic toxic patriarch.
To implement Schrödingers sort, one just need to load the list in a separate memory, and fire protons at the device.
you can also just randomize the list and terminate the program, ensuring it can never be inspected to determine it's state
Ripple Sort: It switches elements randomly in a ripply fashion until the list is sorted.
This video does not feel like it was uploaded 9 days ago, it feels like i've been seeing this in my recommended for like 3 years
i came up with my own sorting method, i call it favorite sort
step one: go through all elements
step two: pick an element (this can be left to personal preference, chance, or any other method you like
step 3: delete all other elements
congrats! the set is sort!
MaoSort:
1) give the list to an underling
2) the underling reports that the list has been sorted as well as eleven other lists.
3) All Praise Chairman Mao!
The funny thing is - Quantum-bogo-sort is basically the combination of Bogo-sort with multiverse stalin-sort. And not only is it correct (and stable), it is proven to be optimal: You can not do better than O(n) - the complexity of checking if it is sorted..
Exploitation sort: the array is sent to a child in Vietnam to be sorted manually.
Error sort: have two computers send the list to each other using parallel transmission over a long distance (increases the likelihood of error) and make it so that there is no parity bit for error correction. have both computers check if the data is sorted as they send it to each other. The data will likely not be the same as the original
Optimized miracle sort!
Bloody brilliant!
The methodology of the “miracle sort” might just work if given long enough, not by means of a miracle, but by cosmic rays flipping the bits in RAM. That’s what I call “cosmic glitch sort.” And if you want to play in hard mode, use ECC RAM!
to speed it up and remove the chance of a bit flip in the wrong spot, store the data in one place, and sort the titles, and place the titles into a particle accelerator
Are you saying that random cosmic events are not miraculous? Those particles and waves have traveled parsec after parsec having not hit a single thing since the big bang, just to hit your insignificant silicon pebble and change a bit. You probably don't even listen to the latest and greatest angelic songs on your geiger counter, do you?
Seed search sort. Create a seed-based procedural randomizer where all arrangements of the list are possible. Starting at seed 1, step through all seeds until a sorted list is found.
My idea: Evosort.
Using the concept of genetic algorithms:
1/ we randomly generate a set of algorithms
2/ run each of them on a copy of the data to be sorted. To prevent cheating, the order of the copy is randomised each time.
3/ We score each of the algorithms according to a "sortedness" score, which I will define as follows: go along each element in turn and compare it with the previous one. If the pair are in the correct order, then increment the score by 1, otherwise the score stays the same.
4/ we then kill the 50% worst scoring ones and create children based on randomly selected pairs from the remaining 50%. The probability of any algorithm being selected as a parent is weighted according to it's rank, so the best has the highest chance of procreating and the worst remaining one has the lowest chance of procreating. Children are made by splicing part of one parent's algorithm with part of the other parents algorithm with a chance of mutation.
5/ repeat steps 2 to 4 until one of the algorithms achieves the maximum possible score (length of array - 1).
6/ output the sorted version of the array
7/ delete all sorting algorithms to re-initialise the sort for next use.
This sorting algorithm is extra useless, because it relies on having another sorting algorithm available so it can rank the performance of the algorithms.
I've heard once about the legendary No Sort: you don't do anything, just hope that your list is already sorted by chance. It has complexity O(0), which is the best possible out of all sorts, although there is a small precision tradeoff (similarly to Intelligent Design Sort and Miracle Sort).
"small precision tradeoff"
Miracle Sort doesn't have a precision tradeoff. It will not return the array unsorted. You just have to pray that the process will halt at some point.
@@xchronox0 Ohh, I get it now. It's not that Miracle Sort might not return a sorted list, it's just that it might take a very long time. In other words, the tradeoff is not loosing precision, but loosing determinism (if I understand it correctly). In that case, we can affirm that No Sort is clearly better, because doing nothing is 100% deterministic.
Generative Bogosort:
1. Create an array the same size as the list to be sorted, and fill it with randomly generated bits.
2. Check if that array is sorted. If not, repeat step 1 until it is.
3. Now that we have an array of sorted data, we need to make sure it's the correct data. Since our original list is probably not sorted, shuffle it randomly and compare it to our candidate. If they match, we're done! If not, go back to step 1.
algorithms are crazy and I think the images you used in the sleep sort display this perfectly LOL such a madman approach
schrödinger's black box sort:
1. generate an input file with a random sequence of numbers
2. in main file, use the input file as your list
3. assume list is either sorted or unsorted depending on specific need
I figured it out, Fortune Sort. Just come up with a scribble that looks like any numeral and make all the numerals in your sorting that! It works perfect for carnival fortune tellers and birthday guessers...
I can actually imagine the Stalin sort being ideal in some circumstances (not when handling people tho)
Maybe less as a sorter and more of a game mechanic, but there are probably more practical uses if you really try
also the second one, that could work sometimes (but there are probably better sorts for those)
Stalin sort should ONLY be used with people!!!
Worked for Stalin.
Also, for implementing Miracle sort, a lot of optimizing compilers transform the obvious way to do it into a while (true) infinite loop.
You-Can-Never-Be-Too-Sure-Sort:
Uses all the sorting algorithms in this video and verifies that they all yeilded the same list. If not... Restart!
what I do to sort my lists and arrays is replace every number in that array with the index. So the array [4, 5, 1, 7, 3] gets sorted to [0, 1, 2, 3, 4]. Very efficient, highly recommend.
Roll sort, it takes an array of n size, looks at the first value in the array, rolls a die with n sides and swaps the value with the value at the position rolled.
For example, consider the array [ 1, 3, 8, 6, 2, 5 ]. The algorithm roll a 6-sided die (because there are 6 numbers in the array), in this case let's say it lands on 5. The algorithm would then swap the value in the first position (1) and then seap it with the value in the 5th position (2) ending with [ 2, 3, 8, 6, 1, 5 ]. The algorithm would then check to see if the array is sorted. If not, it repeats the process grabbing the value in the first position (2) and rolling a d6, etc. until the array is sorted.
Edit, to make the algorithm less efficient I've changed the wording to say that the algorithm looks at the *first* value in the array, instead of the first *unsorted* value.
if you want to optimise, as the first out of order item is lower then the item before, you can role a dice with numbers only to this point
The time complexty is O(n²!) 😂😂
@@SASA_maxillo and with my addition?
isnt that bozosort
@@schwingedeshaehers why would I want to optimize??
There's also the sorting algorithm that assumes that the list is already sorted, and passes it along but if it turns out later down the line that the list isn't sorted, it destroys the universe
Russian Roulette sort: Each cycle, take two random elements and put them in a special array. Then, start randomly generating numbers ranging from the smallest element +1 to the biggest element +1. Whichever element encounters a random number bigger than it first gets sent to the output array. Keep playing until the output array just happens to have had all the elements get sent there in the correct order.
My favourite forbidden sorting algorithm is the Franceschini-Muthukrishnan-Pătrașcu algorithm.
It is a variant of radix sort which sorts integers in O(n) time. Unlike most variants of radix sort, however, it also sorts using only constant additional space! Given that you must visit each element at least once to sort, this is, and I mean this completely unironically, an optimal algorithm. Indeed, it "solved" the integer sorting problem from a theoretical perspective.
That sounds good so far, but it is a forbidden algorithm because it breaks one of the unspoken rules of sorting that you didn't realise existed: it messes with the keys.
Consider an array of n integers that are u bits in size. This array is n*u bits in size. However, there are 2^u choose n possible such sets, which means that you COULD, in theory, compress this array to only log (2^u choose n) = n log u - Θ(n log n) bits. It turns out that this extra space is exactly the additional space needed for radix sort!
The FMP algorithm works like this:
1. Sort the first n/log n elements in the array using your favourite O(n log n) in-place sorting algorithm.
2. Compress those elements, freeing Ω(n) bits of space.
3. Radix sort the rest of the array, using this space as working storage.
4. Decompress the elements you compressed earlier.
5. Merge the two sub-arrays in-place.
arxiv.org/abs/0706.4107
I'm not sure I understand the issue with it.
@@gaysarahkRather than just moving or swapping elements, it depends on modifying them.
But is the end result not the same?
@@gaysarahkIt feels, to many people, like a violation of a rule that you didn't realise existed until someone broke it. Intuitively, sort algorithms should work on "read only" elements.
Anxiety sort: works like insertion sort but the closer the program gets to finishing the higher the chance it will make a mistake. If it makes a mistake it’ll brick your device.
Psychedelic sort:
Overdose on ketamine until the list appears sorted. Since you are a special post-modern snowflake, no one can refute your view of reality, and it is indeed sorted.
HashSort:
Take the number of elements (N),
Take the sum of the lements (n);
For each element (x) in the list, store them in new position at offset = x * (n/N)
Downsides: It only works with positive integers and doesn't work if there are duplicates, but when it does work it completes in O(N) time!
Sounds like bucket sort. It is actually a pretty useful O(n) algorithm.
@@Carewolf Ah neat! I thought something like this might exist.