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
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
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.
@@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
@@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.)
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 Edit edit: I mean the number being subtracted would be rounded to the nearest odd. So if the number of elements was 45 you would round 22.5 to the nearest odd (23) and remove 23 elements to be left with 22.
@@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.
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.
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.
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".
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:
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.
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.
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.
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).
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
@@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
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.
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)
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
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.
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
7:09 people love explaining both of the main concepts here incorrectly. 1. Shrodinger's cat is a *criticism* of the thing it describes. The cat is not, in fact, both alive and dead. It's a critique on the idea of observation causing the collapse of superpositions. 2. This is the double slit experiment. The particles don't simply change when being observed. The short of it is that while when not being observed, the particle behaves and creates a result in one way, but when we try to observe it, the methods used to observe something like that alter the particle's behaviors. It's not something like sentient particles knowing when they're being observed. Sorry if any of this was poorly explained or missing details.
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.
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.
@@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
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
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).
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 }
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."
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.
@@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
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.
@@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
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.
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.
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 :)
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
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.
I've got a funny sort. May I present to you, halting sort! Before we start, we need two things: 1) A universal Turing machine T 2) An algorithm A(x) such that A(x) halts for all finite positive integers x and A(0) is the input to T that corresponds to the Turing machine that halts immediately. Then, we can sort the list list as follows: 1) Create a new list alpha with n-1 elements. 2) For each index i between 0 and n-2, set element alpha[i] to 0 if list[i]
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)
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.
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
Lake sort: Throw the device with the array in memory into a lake while it is on, causing a short circuit and the memory of the array to be destroyed, thus removing the need to sort it
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.
"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".
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.
*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
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
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.
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.
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)
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.
@@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)
Bizzaro sort: Takes an already sorted array and takes the closest average of the numbers and switches it with the highest number on the list. It stops when all the numbers have been moved.
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.
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.
Duck Sort: 1. Gather a group of ducks. 2. Assign each duck a number corresponding to an element in the array to be sorted. 3. Place the ducks in a line. 4. Release the ducks and let them wander freely. 5. Every few minutes, ask each duck for its assigned number. 6. Arrange the ducks in numerical order according to the numbers they respond with. 7. Repeat steps 4-6 until all ducks are in the correct order. 8. Translate the order of the ducks back into the sorted array.
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..
except as people have pointed out the actual best way is to skip the shuffle steps and the checking steps and just jump strait to the saying it is correct step. if you want to you can have some one else clean up any universes that this did not work for.
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
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).
also don't forget to buy the best clock on the market because if you get the array 999999, 2, 1 you want to make shure the clock is precise enough to pick up the difference between 1/999999 and 2/999999
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
@@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
Infinity sort: You don’t choose the sorting algorithm. The computer randomly initializes a list of sorting algorithms to choose from to sort the initial list. We need to sort those sorting algorithms to find the one with the smallest O. So the computer randomly initializes another set of sorting algorithms to sort the sorting algorithms but it needs to know which algorithm to sort the sorting algorithms to sort the sorting algorithms to sort the list. This repeats infinitely (or until your computer melts).
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.
@@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.
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.
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
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")
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
@@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.
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.
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.
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.
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.
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!
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.
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
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.
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...
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
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.
Light speed sort: for each number, make a space ship, put a synchronized countdown timer inside and send them out into space. The ship representing the highest value goes at 99% the speed of light, and the rest go at a percentage of that based on their value (a value that is half of the highest value goes at 49.5% the speed of light, for example). The faster the ship goes, the slower time passes for the timer inside it. The first timer to finish is the first element of the list, the second one is the second, and so on.
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.)
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?
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.
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...
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.
Plane sort: the entire script runs over and over until, by pure chance, radiation flips all of the correct bits to sort the array. To maximize RNG, the programmer will bring their laptop on a plane to expose themself to greater amounts of radiation.
I propose the EAsort: At the start, we are given 3 entries of the list, but forst we must pay increasing amounts of money to unlock the next entries and then finally, we must pay increasing amounts of money to have the list bogobogo sorted, praying for a sorted list to emerge.
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.
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.)
Revival Sort: Going left to right through the list, check if the current number is in order, if it isn't add it to a list of deleted items and remove it from the original list, when you're done, add in a random item from the deleted list into a random position in the new shrunken list, and repeat.
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
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!
maybe you can do an OutsourceSort where you send it to a click-farm in a country with lower income than yours for them to sort the list at a low price not the most humane, but it does involve humans
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).
@@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.
Savestate sort: take a savestate of before the list was shuffled and warp back to it. Quantum savestate sort: same thing but brings everything with it.
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
@@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.
If you eliminate all the sets that don't start with the smallest element, and then eliminate those that don't have the second smallest element in the second position, etc. it reduces to a selection sort -- except it uses a lot more memory temporarily.
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 😬😅
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
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).
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
Edit edit: I mean the number being subtracted would be rounded to the nearest odd. So if the number of elements was 45 you would round 22.5 to the nearest odd (23) and remove 23 elements to be left with 22.
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.
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.
@@sakesaurusI 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?
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.
but qhat about a table like {0,0,0,0,0,0,1,2,4,7,3,47,42,69,420,7435773574,57436,456,435645,6543,654,64,3,64536}
but qhat about a table like {0,0,0,0,0,0,1,2,4,7,3,47,42,69,420,7435773574,57436,456,435645,6543,654,64,3,64536}
That's me doing classwork and calling it done
imagine sorting 2,1,2
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.
@@saddexed Or if you're a comic superhero.
To be fair cosmic rays and myriad electromagnetic interference actually gives the algorithm some remote chance of actually "working"😅
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
@@kooskoos1234 yes that's exactly what I'm saying
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
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".
This also has the side effect of two people reverting each other's edits.
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[]
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.
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 UA-camr 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
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.
This sounds like a genetic algorithm
The way "miracle sort" made me burst into laughter at 5am after an all nighter...
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?)
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
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
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.
Wait how is this gonna work for repeating numbers that's not next to each other?
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
Super Mario 64 speedrunners' favorite algorithm! (Allegadly)
7:09 people love explaining both of the main concepts here incorrectly.
1. Shrodinger's cat is a *criticism* of the thing it describes. The cat is not, in fact, both alive and dead. It's a critique on the idea of observation causing the collapse of superpositions.
2. This is the double slit experiment. The particles don't simply change when being observed. The short of it is that while when not being observed, the particle behaves and creates a result in one way, but when we try to observe it, the methods used to observe something like that alter the particle's behaviors. It's not something like sentient particles knowing when they're being observed.
Sorry if any of this was poorly explained or missing details.
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
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
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).
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.
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."
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
@@Wabbelpaddelthats miracle sort, basically.
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
@@batziii8745wrong, bogosort can have the same wrong order infinite amount of time
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.
Over the years, I've become a master of miracle sorting my problems in my life.
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!_
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
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.
I've got a funny sort. May I present to you, halting sort!
Before we start, we need two things:
1) A universal Turing machine T
2) An algorithm A(x) such that A(x) halts for all finite positive integers x and A(0) is the input to T that corresponds to the Turing machine that halts immediately.
Then, we can sort the list list as follows:
1) Create a new list alpha with n-1 elements.
2) For each index i between 0 and n-2, set element alpha[i] to 0 if list[i]
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)
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?
@@AlLiberali 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
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
Kamikaze Sort:
Take an unsorted array. Delete it.
Lake sort: Throw the device with the array in memory into a lake while it is on, causing a short circuit and the memory of the array to be destroyed, thus removing the need to sort it
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".
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.
*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 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.
Norman Sort: Have my cat meow at the data set until it's sorted
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
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.
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)
Bizzaro sort: Takes an already sorted array and takes the closest average of the numbers and switches it with the highest number on the list.
It stops when all the numbers have been moved.
Rowhammer-sort: don't read the array, but the DRAM rows next to it to induce bitflips in the array until it's sorted.
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.
i call this MaoSort
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!
Futurism sort: Waits until a perfect sorting algorithm gets invented.
Duck Sort:
1. Gather a group of ducks.
2. Assign each duck a number corresponding to an element in the array to be sorted.
3. Place the ducks in a line.
4. Release the ducks and let them wander freely.
5. Every few minutes, ask each duck for its assigned number.
6. Arrange the ducks in numerical order according to the numbers they respond with.
7. Repeat steps 4-6 until all ducks are in the correct order.
8. Translate the order of the ducks back into the sorted array.
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..
except as people have pointed out the actual best way is to skip the shuffle steps and the checking steps and just jump strait to the saying it is correct step. if you want to you can have some one else clean up any universes that this did not work for.
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
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.
also don't forget to buy the best clock on the market because if you get the array 999999, 2, 1 you want to make shure the clock is precise enough to pick up the difference between 1/999999 and 2/999999
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
This is just the premise of the three body problem
Infinity sort:
You don’t choose the sorting algorithm. The computer randomly initializes a list of sorting algorithms to choose from to sort the initial list. We need to sort those sorting algorithms to find the one with the smallest O. So the computer randomly initializes another set of sorting algorithms to sort the sorting algorithms but it needs to know which algorithm to sort the sorting algorithms to sort the sorting algorithms to sort the list. This repeats infinitely (or until your computer melts).
Deletion Sort: delete all elements in the list, leaving an empty, yet sorted, list.
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
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
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
Make it a Marvel race but its secretly rigged
so any sorting algorithm without code is just miracle sort
Ripple Sort: It switches elements randomly in a ripply fashion until the list is 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.
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?
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.
Loki's miracle sort: if the list is unobserved for any period of time, it becomes one random alteration away from perfectly sorted.
Exploitation sort: the array is sent to a child in Vietnam to be sorted manually.
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!
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.
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.
Number 9 is my absolute favorite, I always use it in computer science classes.
Destroy Sort : Destroy all number in the array except for the smallest one
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...
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!
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??
Light speed sort: for each number, make a space ship, put a synchronized countdown timer inside and send them out into space. The ship representing the highest value goes at 99% the speed of light, and the rest go at a percentage of that based on their value (a value that is half of the highest value goes at 49.5% the speed of light, for example). The faster the ship goes, the slower time passes for the timer inside it. The first timer to finish is the first element of the list, the second one is the second, and so on.
a sweet variation of Gravity sort with even more ridicilousness
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.)
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?
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.
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
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.
Plane sort: the entire script runs over and over until, by pure chance, radiation flips all of the correct bits to sort the array. To maximize RNG, the programmer will bring their laptop on a plane to expose themself to greater amounts of radiation.
I propose the EAsort:
At the start, we are given 3 entries of the list, but forst we must pay increasing amounts of money to unlock the next entries and then finally, we must pay increasing amounts of money to have the list bogobogo sorted, praying for a sorted list to emerge.
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.
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.)
Revival Sort:
Going left to right through the list, check if the current number is in order, if it isn't add it to a list of deleted items and remove it from the original list, when you're done, add in a random item from the deleted list into a random position in the new shrunken list, and repeat.
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
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!
HumanSort - shows a dialog presenting the unsorted list qnd asking the user to enter the sorted list. And halting the execution until this is done
maybe you can do an OutsourceSort where you send it to a click-farm in a country with lower income than yours for them to sort the list at a low price
not the most humane, but it does involve humans
@@aiocafea thats just the ImNotARobotSort i mentioned earlier but with less steps
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.
Savestate sort: take a savestate of before the list was shuffled and warp back to it.
Quantum savestate sort: same thing but brings everything with it.
Miracle sort is so good. Image just sitting in front of a bunch of numbers and yelling "PLEASE"
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.......
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.
A good one is Permutation sort - Generate all combinations (deterministic) and iterate over them to find which one is the sorted one. Similar to bogo
This opens up a way to crash any server with a single SQL call
@@charliekahn4205 ???
If you eliminate all the sets that don't start with the smallest element, and then eliminate those that don't have the second smallest element in the second position, etc. it reduces to a selection sort -- except it uses a lot more memory temporarily.
Permutation sort will always halt and that is not the case for Bogosort. So this is strictly better than Bogosort for that reason.
@@MattDog_222 this sorting algorithm essentially causes smaller servers to DDoS themselves
i like to immagine theres an alternate universe where Bogosort has worked every single time by pure chance
Thala sort:
Sort the array until the seventh position of gets sorted and then sort all the other places 7 times until we get 7 at 7th place.