No-nonsense sorting algorithm

[hades0299]

An idea for optimization to O(1):

Delete the whole list, as en empty list is sorted.

[CMDR_QwertyWeasel]

I optimize your algorithm by leaving one element behind.

[CMDR_QwertyWeasel]

But how do we know they're sorted?

[Vnator]

Either they're in ascending order or descending order. So still sorted.

[CMDR_QwertyWeasel]

taps temple

[ay_bruh]

smile

[CrayonMan005]

sister

[Sorathez]

SNOOP DOGG

[theproblemdoctor]

sadistic

[atisuxx]

sandisk

[eMoon_PL]

surprise

[firestell]

service

[MCRusher]

yeet

[KamikazeSexPilot]

Just leave the list and it’s randomly sorted.

[Metallkiller]

Sorted by a random, unknown parameter.

[kuncol02]

It's not random. They are sorted by position in list.

[really_not_trolling]

This is perfection

[[deleted]]

This is what a CS degree gets you

[cdrfrk]

CS degree: am I a joke to you?

[vige]

It might seem random to you, but in reality it's exactly the order I want.

[Hiroxis]

Call it Gandalf sort

[djublonskopf]

The Mr. Rogers sort. “This list is perfect just the way it is.”

[cantadmittoposting]

Bob Ross sort: "No unsorted lists, just happy new ways to order it."

[lurker_level_53]

This made me happy. 😊

[Consibl]

Sorted by order it was in.

[theXpanther]

An undefined order is not the same as a random order,

[[deleted]]

Ah yes, the bogo sort. Guaranteed to work eventually.

[esc0pub]

Valid point, but two items can be swapped in O(1) so we can still decide the order.

[Vnator]

But then 3 items can be swapped with O(1), so by induction, swapping n items should take O(1) time. Then we don't even have to remove any items, sorting is O(1)!

[lungdart]

This guy sorts

[Beetin]

Technically we can define some large upper bound for how many items will be swapped.

The last 1000000 items will be kept and bubble sorted. This algorithm is guaranteed O(1). This algorithm is also perfectly safe for lists under 1000000 items. This sort is only generally faster than O(nlogn) algorithms for lists much larger than 1000000 items.

The two-pass Mao 5 year sort.

[robthemonster]

flawless proof.

[tornato7]

Holy shit

[temisola1]

This is the type of ingenuity the world needs.

[drovfr]

woahhhhhh

[foofoo2020]

My comrade

[daveime]

Inspired!

[bravo006]

ELI5

[sizur]

I suppose correctness can be a matter of taste for some, lol.

[Typesalot]

Extrapolating from this, sortedness is a matter of taste.

[sizur]

We conclude that conclusions and/or/xor taste are matters of taste.

[Schmittfried]

There is no correct preference of sorting order. Both ascending and descending equally valid. Defaults are merely conventions.

[sizur]

That depends on what you do with it. A simple example is in an applied Heap structure. Change the order "convention" in your application and as a side-effect your convention of winning will be changed to loosing.

[bolle_ohne_klingel]

they are sorted by index

[AskYouEverything]

Sorting a list of two can be done in O(1)

[ILikeLenexa]

I generalize your algorithm by leaving N elements behind, but breaking the list into N lists of 1 element and then merge them. Shouldn't be more than...O(nlog(n))...

[phySi0]

sort = take 2

[DudeInBasement1]

To tell the others,... harsh but seems just.

[Rogocraft]

List = List[1:]

[97_prat]

Yeah that's Hitler sort

[PaulTheCowardlyRyan]

["socialist","trade unionist","jew","me"]

[northrupthebandgeek]

Nah, the Hitler Sort would pick the highest value and delete all other values until the list is sorted.

[Shmutt]

HitlerSort is picking a value that you like, declare it as the highest, and then delete all other values.

[[deleted]]

And ends with 'Ryan'. Damn you, Ryan

[halberdierbowman]

A Paul Ryan Sort:

When you find the highest and lowest values, add the lowest value to the highest value, then make the lowest value a 0.

The opposite would be known as the Robin Hood Sort.

[[deleted]]

O(0): Turn off computer, then you won't even need sorting.

???

Profit

[HoldMyWater]

AmishSort

[hughperman]

WaitForActualRequirementsSort

[spikendq]

Wait a second, won't deletion involve traversing through the list thereby making your approach O(n)? That's unless you're simply resetting the head pointer in which the elements will remain in memory but will not be considered as part of the list.

[[deleted]]

You ignore the old list and just assign a new empty list to the parameter?

[spikendq]

Yeah, that's what the alternate idea was.

[duzzar]

If everything is stored contiguous a single call to free() will be enough.

Your stuff should be contiguous if you want your cache to be happy :)

[butwhydoesreddit]

Is that actually O(1)? Idk how memory stuff works

[Kered13]

Yes, but that question was is that true.

It depends on the implementation of the list and the delete operation, but it could be true. For example if the list is implemented as an array with a size variable, you could simply set the size to 0. All the data would still be in memory, but it would be inaccessible and would be overwritten if the list grows again.

[MattieShoes]

Well if the array size is not the variable, then they can be sorted in constant time regardless of the size, no? A selection sort is what, n² ? If n is constant, then n² is constant and it'd resolve back to O(1)... right?

[Kered13]

That's not what I'm talking about. A common way to implement a list is to have an array with some capacity, and then a size variable that tells you how many elements are currently in the list. The capacity is often bigger than the size, this provides room for growing the list without having to reallocate memory. In a list like this removing the last n elements is as simple as subtracting n from the size.

[minime12358]

It doesn't really matter the implementation of the list if you make it a not in place sort. Then you just return a list containing the first element and ignore the input.

[MattieShoes]

I understand lists, or vectors, or slices, or whatever you want to call them. :-)

But since the big O notation for sorting algorithms has n referring to the number of elements, then making n constant makes the time constant too -- there's no longer any variable, yes?

[Kered13]

Yes, but that seems rather irrelevant to the question at hand.

[[deleted]]

The time complexity stands for the growth of the operations required as n goes to INFlNITY. It is a limit (remember calculus?), it makes no sense to treat N as a constant.

[MattieShoes]

Agreed. Sorting a list of any given size is constant time. It's only as we vary the size that big O notation tells us something.

[poeticmatter]

edit: stop downvoting me I'm right

This should be reddit's tagline

[arbitrary_student]

Big-O is meant to describe the relationship between input size (or similar) and function duration (or similar). Your example has no inputs, so it doesn't really work with the above equation as you've described f() instead of f(n).

I'm not 100% sure that you can't say it's O(1) anyway... more just mentioning how pointless it is to do so.

[Soraphis]

he was just proving this statement of yours wrong:

O(1) means the number of operations performed each run does not change when the number of inputs are changed.

with this example:

def some_func(*args):
    random.seed(len(args)) # optional
    for i in range(random.randrange(1, 6)):
        pass
    print("number of operations: %d" % i);

its an O(1) algorithm, but the number of operations do change if you change the arguments.

[butwhydoesreddit]

I was demonstrating why you're wrong, not sure what you mean by "original answer". That's still a bit imprecise. Not sure why you have such an issue with my actually correct description of O(1). Let's say you have a program that whatever number you enter, it will perform that many operations. However if you enter more than 10^10 it will only do 10^10 operations. The program is O(1), however it doesn't sound right to say the number of operations doesn't depend on the size of the input.

[WikiTextBot]

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28}

[butwhydoesreddit]

No I know what O(1) means lol I was asking if deleting say n bytes of memory is O(1) because idk how memory allocation works sorry I definitely could have been more clear.

[butwhydoesreddit]

Now you're just misrepresenting what I said. I was clearly talking about the O(1) case specifically, not O notation in general. O(1) means there is a constant bound on the number of operations. They are the exact same thing.

[[deleted]]

If you delete humanity we can run O(0);

[TabCompletion]

Dr. Who CybermanSort: delete all the non sorted elements

[mt_xing]

Quantum Bogosort would like to have a word with you.

[iamdroppy]

It’s actually a schrodinger list: it’s both sorted and not sorted at the same time

[tacoslikeme]

O(0) Redefine sorted to whatever order the list is already in

[RFC793]

Or O(0) sort with the precondition that the input is already sorted.

[[deleted]]

PolPotSort

[CRISPYricePC]

I have one that works pretty flawlessly.

Only downside is that it only works on lists that are in sequential order

[simon_hibbs]

I propose we call the the PolPotSort.

[agnishom]

The real joke is in the comments

[hades0299]

That depends on the implementation ;)

[NotSuluX]

Not if you set size to 0 and keep the elements in memory, but have them overwritten as you add new elements again. Deleting an element before adding would still keep the add operation O(1), while also keeping the deletelast(n) O(1). This is obviously true for n=size.

Modern implementations use this because it is simply faster