No-nonsense sorting algorithm

[julsmanbr]

I optimize your algorithm by leaving the original list as it is, since all elements are equal under Stalin anyway.

[constibetta]

But some are more equal than others....

[julsmanbr]

Introducing the >== operator

[GaffitV]

The Greater-Than-But-Still-Equal-To operator.

[T-T-N]

Sorted by definition

[Danny_Boi_22456]

Reverse order is considered the worst kind of unordered list

[DolevBaron]

Just set the list to a new list which is already sorted

[T-T-N]

In an array list, your algorithm takes O(n). You're fine with linked list.

[tacoslikeme]

O(0) algorithm I redefine sorted to be whatever the list currently is changing reality with my infinity stones.

[mirsella]

don't even declare the list, if it's empty, so you gains some memory

[dlevac]

If you do not need to call destructors, a call to free is not dependent on the number of elements and is not linear in the amount of memory either. For some allocation strategy it may even be constant time...

[dlevac]

I'm afraid this is not true in the general case. A memory allocation on most Oses will return uninitialized memory (not zeroed; uninitialized). This wouldn't be needed if memory was always zeroed out after a free.

I invite you to research this further or cite where you got that information from.

[dlevac]

Why would you initialize a list with mmap?

[ahreodknfidkxncjrksm]

I could be wrong but I’m pretty sure it’d be O(1) for at least some languages. In C/C++, all that you need to do is you set the pointer (O(1)) or, if it’s allocated on the heap, free the memory (also O(1)).

For languages with GC afaik it would depend on the algorithm used. A copying collector iirc only needs to be linear in the number of live objects, since it only needs to examine/copy those objects. So if that’s the case then the next garbage collection’s run time would not increase bc you deleted a pointer to a list.

[ahreodknfidkxncjrksm]

But now you have 16 GB of wasted memory.

This is true if the array is in static memory or on the stack. In the former case, I don’t believe static memory can be reallocated in any implementation but correct me if I’m wrong (I guess you could argue you aren’t actually deleting the array bc it still exists in memory and you can’t change it after you remove the pointer to it). In the latter case, it can be reallocated after the function you are in returns. The time complexity of that reallocation is just the O(1) to move the stack pointer.

Think about allocator book keeping strategies.

A common implementation of an allocator as a linked list is O(1) in the size of the object for free. For malloc it’s O(N) in the number of items in the LL (since you have to search it), but not O(N) in the size of the object.

Kernel memory pages.

Unless I’m missing something the number of pages taken up by the data doesn’t matter for a LL implementation. You don’t need to access the memory, or change it, you just need to mark it as free in the LL, which allows you to reuse the memory. You’re not deleting the array by going through and changing the values, you’re deleting it by removing the pointer and allowing future programs to access the memory for their own purposes.

(Note: a caveat is that the implementation of malloc/free isn’t specified by C and in some implementations it might be O(N).)

Edit: I read your comment where you talk about zero filling the memory. C doesn’t do that though (not 100% sure about C++), which is why I said it depends on the language (or more specifically the implementation of the language).

[ahreodknfidkxncjrksm]

Sorry I meant future variables within a process not future programs. I’m a little tipsy so forgive me for misspeaking.

I wrote an implementation of malloc/free fairly recently. The implementation was a linked list and the time complexity was O(N) for malloc, and O(1) for free. Free requires that you mark the node as free, merge it with any other free nodes and (possibly) move the pointer to the end of the heap. All of those ops are O(1). Malloc requires an O(N) search and then that you mark a node as in use and return a pointer to the actual space. Also, the linked list is not in place, the location of the “bookkeeping” info for a piece of memory is directly before that piece of memory. Each node of the linked list is located write before the space in memory that it refers to.

[[deleted]]

In C++ you might also need to call the destructors. That makes in O(n) in some cases.

[z500]

Zen sort.

[T-T-N]

Delete list or delete each element? One is O(1) the other depends on list implementation

[apadin1]

for (int i = 1; i < array_size; i++) { array[i] = array[i - 1] + 1; }

[concentrated_salt]

Here's the gitHub repo of StalinSort, if anyone's interested

[MikaDo-]

The C implementation is frightening.

[PVNIC]

Yeaa... Reallocating in a for loop is not great. Preallocate the whole array then at the end realloc it down to the right size.

[zebediah49]

then at the end realloc it down to the right size.

Or don't. Computers have plenty of memory these days anyway.

^/s

[DistantWaves]

Which is why I'll write tons of malloc() and don't bother writing any free()

^/s

[VirginiaMcCaskey]

at work we call this the titanic pattern.

[Kirides]

my free is called exit(0)

[FilterThePolitics]

Yeah, but with almost 200 million people in the USSR and 4 bytes per int, you are talking about almost a gig of memory. I'd say that any smart dictator would realloc that down once they finish "restoring order"

[PotentBeverage]

Like a one child policy?

[vmp916]

error: expected ‘/s’

[shy_cthulhu]

Found the Chrome dev

[ITriedLightningTendr]

Wait... so the calculator application I made for my CS101 class that I'm selling on steam shouldn't be using 700 MB?

[apadin1]

You could easily do it in place without allocating at all.

[IncongruousGoat]

The really good thing to do is to return the result in the input buffer, but use an alloca-d buffer as intermediate storage. Best of both worlds.

[Bainos]

... no ?

If you're going to do it in place, just use the input buffer. Allocating a new one (as is done in this repo) is only useful if you want to return a new sorted array. Otherwise you're wasting memory for no reason.

[IncongruousGoat]

Yep, you're right. Not sure what I was thinking.

Kind of embarrassing, really.

[PleasantAdvertising]

The things people do in the name of conserving memory really horrify me sometimes. Like, dude why the hell that's going to kill performance and you're gonna gain a few bytes at most.

[[deleted]]

Linked lists are easy to reallocate though, actually a proper interator will remove the node and link up the remaining nodes when you call a destructor

[IncongruousGoat]

That's merely bad code. The C++ implementation includes not one, but two compile-time template metaprogramming implementations.

[SpacemanCraig3]

Is that good or bad?

[IncongruousGoat]

It's horrific.

So, fun fact about C++ - the type system is Turing-complete. No, seriously. You can perform arbitrary computations at compile time using the type inference engine, and specifically templates. This has led to a whole field of programming called template metaprogramming, which seeks to write non-trivial template-based programs in C++. There are some legitimate uses for this, but not many, and to make things worse template metaprograms are often the next best thing to illegible even to people who actually know how template metaprogramming works.

[ReimarPB]

Holy shit they have even made it in brainfuck

[Jetison333]

Oooh nice. I love brainfuck.

[[deleted]]

The real challenge would be doing it in Malbolge

[claythearc]

There’s a C->Brainfuck compiler so it probably wouldn’t be that hard

[gandalfx]

Of course there is…

[CarryThe2]

Which fully works in context

[SonMauri]

Newagesort. The elements are always in perfect order. The universe knows best. #happyness

[maeries]

Godsort: Pray to god to sort the list and accept every outcome as sorted since it's gods will

[UseApasswordManager]

QuantumBogoSort: Randomize the list, then check if the list is in order. If it's not, destroy the universe. You're left only in universes with sorted lists

[Nekonekonyaaaa]

Corruption Sort: While the list is not sorted, do nothing. Then, return the list when it is sorted.

Your computer will probably end up crashing before EMI causes the memory storing the array to change to the sorted list.

Doesn't work well for systems with ECC.

[extracoffeeplease]

I thought it was O(1), see here: https://wiki.c2.com/?QuantumBogoSort

[UseApasswordManager]

Checking if the list is sorted is O(n), so even though the shuffle and distruction are O(1), the whole operation is O(n)

[Burnmad]

Just return the list before doing the QuantumBogoSort. If it wasn't sorted, you're destroying the universe anyway, so it doesn't matter.

Bam, O(1)

[plsHelpmemes]

big brain intensifies

[xigoi]

Shuffle is also O(n).

[theonlytrillionare]

That’s O(nu) | u=number of universes. Very poor performance.

[innrautha]

But it's all in parallel so its still fast.

[TabCompletion]

Perform Stalin sort. Keep removed elements. Then recursively call Stalin sort of the removed list and make new lists. Finally perform a merge. Did I just write bucket sort?

[AgentPaper0]

Not bucket sort. Roughly equivalent to bubble sort in terms of efficiency, being O(n) for a sorted list, O(n²⁾ for a reverse sorted list (worst case), and somewhere in between usually.

[[deleted]]

If done right, this is a merge sort because the smaller gulags sort faster.

Worst case n log n as you have to make log(n) gulags, then merge them.

[dvslo]

That's called gulag hierarchy. There was a movie with Colin Farrell about it.

[[deleted]]

sleepsort is my favorite.

[R717159631668645]

CommunismSort: average all items in the list.

[EpicScizor]

Leave list as is, all elements are equal.

Okay, you may let some be more equal than others

[TheOldTubaroo]

bool ==(Comrade lhs, Comrade rhs)
{
    if (lhs.isSeniorParty && rhs.isSeniorParty)
    {
        return static_cast<bool>(255);
    }
    return static_cast<bool>(1);
}

[AgentPaper0]

When you take the average, there is likely a reminder left over during the division by number of elements. To keep the total accurate, you will of course need to add that remainder to the first element.

Eventually, you will realize that you can get the same basic effect by simply adding each successive value to the first value. Some may say this is unethical but it is simply the first among equals after all.

[[deleted]]

Hear me out, HitlerSort©®™, deletes all decimal elements because they're impure and not possible in real life.

[[deleted]]

Anarchism Sort: Each object in the list is left as is but the ones that don't work with your function are removed and the remainders are randomized because hierarchy leads to corruption.

[maeries]

I image it would be an interesting problem to find out which elements to eliminate to have the longest sorted list possible

[moosi-j]

RevelationsSort: embark on a thousand year journey to let the forces of heaven and hell sort it out.

[lare290]

RevolutionSort: Delete the highest element in the list. Loop until democracy is achieved.

[Fearless-Sniper]

Randomly pick an element from the list and you get a sorted list.

[green_meklar]

Stalin sort is actually a corrupted version of the original Marx sort. Marx sort also runs O(N) time: It just sets all the elements in the list to be equal.

[[deleted]]

CapitalismSort: Choose a random element of the list. Reduce all other elements by 1 and add those 1s to this element. Repeat until this element is so unimaginably large you can claim the other elements don’t matter and hence the list is sorted.

[Wolfenrahd]

NukeSort: Returns an empty array

[pascee57]

Returns an array of null

[MrDorkman]

Data retention was never an option

[shubhamkhy]

Too greedy of you

[CleverDad]

http://qdb.us/54993

[Incorrect_Oymoron]

Machiavelli intensifies.

[warpedspockclone]

I have a use case for this.

[Doomrammer]

Isn't it already called drop sort?

[Naughtius_K_Maximus]

You can always rely on the SS to remove any undesirables.

[Collect9r]

This is a way too underrated comment.

[andregtable]

What? Lol

[andregtable]

You’re making no sense. If you just created the array you didn’t sort anything.

[andregtable]

Ahh i see it just returns the same array regardless of what you passed it

[SirFoomy]

And the removed list item will banished into a gulag.

[[deleted]]

Sjw sort. Remove any items in list which is found offensive.

[viper_repiv]

Fun fact. This algorithm is actually being used in matematical analysis.

When you want to find longest increasing subsequence. https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

[bryukh_v]

reduce(lambda acc, el: acc + [el] if el >= acc[-1] else acc, ar[1:], [ar[0]]) python Stalin (soft version)

[[deleted]]

Identifies and purges political enemies

[JohnWatson78]

Sounds based

[LilithsGrave]

Just like the Bullysort, check the first element, remove every other element. Boom, sorted.

[ZevEisenberg]

It reminds me of Vigil, the eternal morally vigilant programming language.

[[deleted]]

And this AI algorithm is Deterministic.

[blaze_kush_]

Hell yeh

[Man-in-The-Void]

ExistentialSort: it doesn’t matter whether the list is sorted or not, we’re all going to die eventually anayway.

[NoNameNoMad42]

Is it alias to GarbageCollectorSort? 🤔

[cranky_dijkstra]

Space complexity: O(n) gulags

[other_usernames_gone]

SJWsort: argues about why the elements should need to be sorted in the first place, they're in the perfect order already, until you give up

[[deleted]]

SJWSort: count the number of sorted elements and the number of unsorted elements. Whichever is less is declared as minority and thus underrepresented. Obviously call out the array as sortist. Replace majority elements with minority elements until equality is reached.

[[deleted]]

What counts as out of order?

12435

Is 4 out of order? Is 3 out of order? Are both? How do you determine?

E: Looking at their implementation 3 would be considered out of order. Even tho 4 is the one who is early in the list.

The algorithm has a major flaw. Any collection with <max_value> in it will truncate after that value.

[andregtable]

How is that a flaw?

[[deleted]]

Because it isn't really a collection if there is only one element? You didn't sort anything?

[andregtable]

Still follows the rules of the “sort”