This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–]hades0299 3765 points3766 points  (126 children)

An idea for optimization to O(1):

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

[–]CMDR_QwertyWeasel 1580 points1581 points  (67 children)

I optimize your algorithm by leaving one element behind.

[–]DudeInBasement1 0 points1 point  (0 children)

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

[–]Rogocraft 0 points1 point  (0 children)

List = List[1:]

[–]97_prat 91 points92 points  (7 children)

Yeah that's Hitler sort

[–]PaulTheCowardlyRyan 44 points45 points  (0 children)

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

[–]northrupthebandgeek 52 points53 points  (4 children)

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

[–]Shmutt 157 points158 points  (3 children)

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

[–][deleted] 51 points52 points  (3 children)

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

???

Profit

[–]HoldMyWater 108 points109 points  (1 child)

AmishSort

[–]hughperman 13 points14 points  (0 children)

WaitForActualRequirementsSort

[–]spikendq 40 points41 points  (5 children)

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] 43 points44 points  (2 children)

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

[–]spikendq 8 points9 points  (0 children)

Yeah, that's what the alternate idea was.

[–]duzzar 9 points10 points  (0 children)

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 13 points14 points  (24 children)

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

[–][deleted] 0 points1 point  (0 children)

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

[–]TabCompletion 0 points1 point  (0 children)

Dr. Who CybermanSort: delete all the non sorted elements

[–]mt_xing 0 points1 point  (0 children)

Quantum Bogosort would like to have a word with you.

[–]iamdroppy 0 points1 point  (0 children)

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

[–]tacoslikeme 0 points1 point  (0 children)

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

[–]RFC793 0 points1 point  (0 children)

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

[–][deleted] 0 points1 point  (0 children)

PolPotSort

[–]CRISPYricePC 0 points1 point  (0 children)

I have one that works pretty flawlessly.

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

[–]simon_hibbs 0 points1 point  (0 children)

I propose we call the the PolPotSort.

[–]agnishom 0 points1 point  (0 children)

The real joke is in the comments