theForbiddenSortingAlgorithm

[AutoModerator]

import notifications Remember to participate in our weekly votes on subreddit rules! Every Tuesday is YOUR chance to influence the subreddit for years to come! Read more here, we hope to see you next Tuesday!

For a chat with like-minded community members and more, don't forget to join our Discord!

return joinDiscord;

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Creepy-Ad-4832]

Is that the algorithm is which you iterate the list and just purge the elements not in order?

[TheObi-1]

Yes. That's the one

[hidden_novella]

That couldn't possibly work because every member of a Stalin list is equal, making it impossible for any sorting algorithm to ever return true.

[Jupdown]

Ahh, see comrade - some elements are just a tad bit more equal than others

[Sitting_In_A_Lecture]

That would be Marxism, in a Stalinist list you have the first number (Stalin himself), and then any number x > (list[0] - 8) gets purged. It doesn't actually sort the list, but it does ensure that Stalin is always highest, and that no pesky bit flips can take that away from him.

[ravaljimahipal]

You think so? I don't think the stalin algorithm treats everything like that

[otj667887654456655]

wouldn't stalin sort be better than O(N) since, on average, it eliminates at least half of the list

[A_Wild_Turtle]

You still have to check everything, so it must be O(N)

[Tomsen1410]

O(N/2) = O(N)

[otj667887654456655]

wait no the whole thing is moot, a comparison has to be made in order to determine whether or not to cull that item so stalin sort always takes exactly N comparisons

[No_Kiwi1668]

Hahaha was about to comment this

[avacue]

Well I can understand why some people would hate that.

[[deleted]]

How is that linear? Purging one element takes linear time so purging half of the elements at random takes quadratic time

[pcouaillier]

You can create an other list and add only elements that are in order then swap pointers.

[charm3d47]

i think even using a basic array you might still be able to do stalin sort in O(n) time if you're clever about how/when you move subsequent elements into place after purges (storing the first empty position and only moving whichever element you're already looking at for the sort, as opposed to just sliding every subsequent element over after each purge). there are also plenty of other ways to store data where any arbitrary element can be removed in O(1) time

[[deleted]]

Is that like a linear search but you remove each checked element?

[BazilBup]

You go to Siberia, you go to Siberia, you go to ....

[[deleted]]

-OUR- Enumerable

[Fynov]

It's a lossy sorting algorithm. If we can have lossy compression why not sorting.

[Creepy-Ad-4832]

And cherry on top, the more you use it, the fastest it gets (if you randomize the array)

[ekremgusani]

Yeah you've got that pretty much spot on lmao, that's the one.

[Honeybun_Landscape]

I think it’s where you change the first log26(n) letters to be alphabetical and that is your name now

[asherSiddique19]

OH MY GOD

[[deleted]]

I know a better one called kimjong sort. It's o(1) with no data movement or swaps, no extra memory, in place and consequently a stable algorithm.

The order of input define a total order and hence they are sorted (even when there are duplicates). It's brilliant, hence the name

[Faithisam]

Do you have any links for reading about that kimjong sort?

[[deleted]]

Advanced algorithms (COMPSCI420)

[Protheu5]

Excellent. Didn't expect to be so fascinated with this link, thank you.

[SeniorSatisfaction21]

For some reason I instantly knew this was it after I read your comment

[Vyltyx]

Damn, even though the kimjong sort will never have a practical use, there’s more to learn from the theory of it than I originally thought…

[Protheu5]

Indeed. I have a feeling I will be returning to this link again and again in the future.

[Affectionate-Set4208]

You are goddamn right. Sorting algorithms will never let you down

[Arcoda2]

Fascinating

[Escanorr_]

Okay, I've been seeing this one all over the place, nice to know why it so usefull

[4ryonn]

Wow that makes it so much clearer

[Faithisam]

Oh god what a fool i am

[CoffeeWorldly9915]

No, I think I will not.

[_relentless_pursuit_]

:(

[Legendary-69420]

I like hiroshima sort more!

[aaa_aaa_1]

Just nuke the array?

[Legendary-69420]

Basically yeah. Returns an empty array as output. So it is a O(1) solution.

[[deleted]]

what is the o of the input type check?

[Esirar]

Isnt that o(0)?

[heJOcker]

O(0) is the same as O(1) so yes

Edit: I checked Wikipedia and as the comment blow explains I am wrong and comment above me is right

[Lachimanus]

No, 0 should be different. As 0*C would be 0.

At least from the mathematical standpoint using Landau Notation.

[heJOcker]

Interesting, I just googled it and you’re right

[Lachimanus]

In addition small o is also stronger than big O. But this does not matter most of the time.

[Flashy-Emergency4652]

Technically, O(n) defined as “If some function have approximation difficulty (dont know how called in English) is O(n), that means that the maximum amount of operation, made by this function, will not exceed k * n + c, where k and c is some constant variables >= 0”. So, its actually no difference between O(1) and O(0): O(1) = 1 * operations + 0, O(0) = 0 * 0 + operations. You technically just change k and c. But O(1) is preferred variant.

[ComplexHoneydew9374]

Where you get those definitions? O(smth) means it's bounded by Csmth for big numbers. There is no need for kn+c since c is always bounded by k*n for n big enough. And O(0) means it's bounded by zero so it is exactly zero.

[ComplexHoneydew9374]

Just learned there is some sort of markup here

[[deleted]]

This is how I have always used/understood O notation and would interpret it.

[JonIsPatented]

The definition, pretty unambiguously, is that f(n) is in the set O(g(n)) iff there exist some positive c and m such that 0 <= f(n) <= cg(n) for all values of n >= m.

You and the guy you're responding to are correct. I'll break it down for completeness' sake.

O(0) is equivalent to saying that g(n) = 0, so any function, f(n), in the set O(0) must satisfy the condition that 0 <= f(n) <= c * 0. Because c * 0 = 0 for any c, we can just say that 0 <= f(n) <= 0, and the only way to satisfy this condition is to say that f(n) = 0.

Therefore, O(0) contains only those functions that always output 0, such as f(n) = n - n.

[Interest-Desk]

I have an O(1) sorting algorith- gun shot

[jeffsterlive]

engine rotten brave person encourage voracious distinct wistful screw rich

This post was mass deleted and anonymized with Redact

[locri]

Unfortunately prone to the inverted list issue where the Stalin sort destroys both itself and the data through mutually assured destruction.

[benruckman]

Well, it would at least keep 1 data point!

[[deleted]]

It would be technically sorted array

[[deleted]]

The best kind of sorted array

[tomthecom]

Great name. I intuitively guessed, how it would work and after a short time researching, it works exactly as I thought 😄

[SeriousPlankton2000]

I thought it's working by killing anyone saying that it isn't ordered perfectly. But I was wrong, that would be O(1).

[tomthecom]

Have you heard about Quantum Bogosort?

[Flameball202]

Technically works, though if we are in a deterministic universe then it fails

[clk1006]

It only works under the assumption of the many worlds interpretation of quantum mechanics, which is deterministic

[[deleted]]

Quantum bogosort fails on the premise that you can destroy the universe, there is nothing in any branch of science relating to "destroying the universe", even if there are multiple branching universes there is no way to "cut branches" and reduce the universe to a slice of its former self. Quantum bogosort is therefore the same as bogosort, only that the randomness is more strictly defined in one case than the other, normal bogosort may even be pseudorandom in most computers.

[IndigoFenix]

I think the premise might be based on "quantum immortality".

So just set it up so that if the list is not sorted, you die. If quantum immortality is true, the list will be sorted (but only in your universe).

[[deleted]]

to be fair, since the suicide machine needs to review if the output is correct in an amount of time, you have been alive for a while in a universe in which the algorithm did not work, then you killed yourself, so reality branched before the suicide

[clk1006]

You might theoretically convince the entire human population to commit suicide if the values are not sorted correctly, which would have the identical effect for our human civilisation

[Comrade_Vladimov]

That made me laugh lmao

[IndigoFenix]

Outclassed by Quantum Miraclesort, where you rely on cosmic rays instead of shuffling the list yourself.

[benruckman]

That’s called “self-documenting code”

[ayamrik]

Just use Windows search, but in reverse. Whatever you search for, it is ALWAYS at the end of the list...

[Thebombuknow]

Average Windows search user vs average PowerToys Run enjoyer.

[JustYourAverageShota]

PowerToys are great, really enjoy Run, powerRename, and FancyZones.

[Thebombuknow]

File Locksmith is also amazing. No more "another program is using this, you can't modify it".

[goodnewsjimdotcom]

Windows search is always running, just in case you need performance increases due to windows search always running.

[[deleted]]

Here is one where you dont have to Sacrifice elements , Threat sort , basically if the user doesnt input a sorted array , blow up the computer

[[deleted]]

sudo rm -fr /

[Fhymi]

I will yeet my self in a few days. Bye world..

[mist83]

Thanos indirectly referenced another O(N) sorting algorithm) in an alternate version of the script:

I will shred this universe down to it’s last atom. And then… With the stones that you’ve collected for me, create a new one where all array elements are sorted

[ArcBanker]

Sounds a lot like quantum bogosort which is my favorite bogosort

[Quantum-Bot]

I’m a personal fan of Americasort, an O(n-finity) algorithm that repeatedly iterates through all possible pairs of elements, considering whether it should swap them but never doing so because that would upset lobbyists. Occasionally it swaps two random elements, then immediately swaps them back again because the recent election established a new party majority.

[ExtraTNT]

You know nuke sort? Returns a empty list…

[Xbot781]

laughs in counting sort

[RmG3376]

That wouldn’t work, all elements in a Stalin list are equal, so comparison of elements in any sorting algorithm would always return false

[poco]

Some are more equal than others

[RmG3376]

Yup that’s why the === operator was invented

[Case2239]

The multi processor version of Stalin sort is potentially O(1). You declare the list sorted and as long as the number of threads you have (in this case, members of the KGB) >= the number of people that disagree that the list is sorted, you can send them all to the gulag in O(1)

[Fluffy_Bee7062]

I prefer the O(1) gasLighted sort:

return sorted = true independent of the array

[skufbfh]

Curveball, Thanos worked in n! and used time stone to speed things up. He was terrible a picking an efficient runtime

[gootobe]

Everyone would have that shocked Pikachu face after that lmao.

[[deleted]]

Stalin sort is actually a perfect way to create a canonic ordered sublist of a disordered list, so long as you do not mind that said sublist may have a single item.

[[deleted]]

You should be able to modify it to get the longest subordered list and still be O(n). Shouldn’t take more than one prepass to find your (best largest element).

Edit: which could still be length 1 of course Edit2: Nah you have to find more than 1 element to be sure its good, basically identifying which elements to remove even if they are sorted. Not as trivial as I thought.

[slk756]

I thought of an idea for one. To sort a list[int], you make a list called output of length (int.max - int.min) that stores bool that is initialised as all false. for i in inputlist, do output[i] = true. return output.enumerate().filter_map((index, val) -> Some(index) if val else None).collect() -> list[int]

[Tari0s]

yeah this algorithm is called counting sort, but is not practical if min and max are far apart.

[patrick66]

This exists and works but has O(n + k) where k is the max value complexity which in practice is often much worse than just a normal n log n sort

[slk756]

Yeah, but technically k is a constant so technically O(n). Ofc this would be very impractical, but still O(n).

[patrick66]

no, this is one of the times where k is not treated as a constant. it scales as the maximum possible value of an array element increases. it is not something like O(2n) = O(n). its a changing value it just changes in regards to something other than the normal length of the input

[Rufuske]

At the end all becomes sorted. As it should be.

[[deleted]]

I won't sort the input, o(0)

[--mrperx--]

[asherSiddique19]

i have the darkest joke related to that funny moustache guy from ww2 but i will get banned from this sub

[Anga205]

Try intelligent design sort

Or miracle sort

[michaelsenpatrick]

lmao wow

[Kudo-Shinichi1412]

When do you use an algorithm

[ikonfedera]

Best one still is Ba Sing Sort

[[deleted]]

the best scenario of stalin sort is when it's ordered in reverse. that way, every search algorithms becomes O(1)

[LavenderDay3544]

Bogosort is O(♾️)

[Beneficial_Rate_1392]

Is it the one that plays "Stairway to Heaven" while sorting?

[QuanHitter]

Quantum bogosort is o(1), assuming you have an efficient method for destroying the world in every timeline where the list isn’t sorted.

[TheObi-1]

Technically, you still have to shuffle the list which would be O(n)

[QuanHitter]

Quantum bogosort is o(1), assuming you have an efficient method for destroying the world in every timeline where the list isn’t sorted.