1185: "Ineffective Sorts"
Moderators: Moderators General, Prelates, Magistrates
Re: 1185: "Ineffective Sorts"
The important bound on the runtime of sleepsort will be a function of the operating system's task scheduler. This looks to be O(log (N)).
Re: 1185: "Ineffective Sorts"
Elvish Pillager wrote:If n = O(k log k) then log n = O(log(k log k)) = O(log k + log log k) = O(log k)
Hence there is no asymptotic difference between log n and log k.
You're right; thanks!
Re: 1185: "Ineffective Sorts"
So yeah, I implemented StackSort in C# (in one go so it's really ugly ). It sorts my list of 4 elements in about 4 minutes on my machine, it's close to O(1). I'm a first time poster (long time lurker) so I can't place the code or an actual link, but you can find it here : pastebin dot com/pzP19zJa
Re: 1185: "Ineffective Sorts"
Randall, you created a monster. If people start coding programs that search StackOverflow, download and compile the code, the next step is coding programs that will search the internet for programs that will search StackOverflow for the solution to any given problem. And the day is close when all computer programmers will actually be replaced by computer programs.
Or maybe it's just part of the plan that will lead to the singularity.
Or maybe it's just part of the plan that will lead to the singularity.
Re: 1185: "Ineffective Sorts"
pitareio wrote:Randall, you created a monster. If people start coding programs that search StackOverflow, download and compile the code, the next step is coding programs that will search the internet for programs that will search StackOverflow for the solution to any given problem. And the day is close when all computer programmers will actually be replaced by computer programs.
...except those who put stuff on StackOverflow.

 Posts: 6
 Joined: Wed Mar 20, 2013 11:16 am UTC
Re: 1185: "Ineffective Sorts"
Mr_Happy wrote:So yeah, I implemented StackSort in C# (in one go so it's really ugly ). It sorts my list of 4 elements in about 4 minutes on my machine, it's close to O(1). I'm a first time poster (long time lurker) so I can't place the code or an actual link, but you can find it here : pastebin dot com/pzP19zJa
Dude, that's freaking awesome! But still, 4 minutes? What's keeping it so long? Is it only finding a good algorithm after a few tries? Perhaps you should try ordering the search results under different criteria, such as number of votes vs. relevance vs. oldest, and if you do, please tell us your results .
Re: 1185: "Ineffective Sorts"
HarpyRotter wrote:Mr_Happy wrote:So yeah, I implemented StackSort in C# (in one go so it's really ugly ). It sorts my list of 4 elements in about 4 minutes on my machine, it's close to O(1). I'm a first time poster (long time lurker) so I can't place the code or an actual link, but you can find it here : pastebin dot com/pzP19zJa
Dude, that's freaking awesome! But still, 4 minutes? What's keeping it so long? Is it only finding a good algorithm after a few tries? Perhaps you should try ordering the search results under different criteria, such as number of votes vs. relevance vs. oldest, and if you do, please tell us your results .
The problem is that he'll need a sort algorithm for that.

 Posts: 38
 Joined: Fri Apr 27, 2007 2:59 am UTC
Re: 1185: "Ineffective Sorts"
Okay, so this comic got me thinking about sort algorithms again, as I sometimes do (thanks to whoever posted sleepsort, BTW, that's brilliant. Stupid, but brilliant), and especially the "halfhearted" sort got me thinking. I can think of some applications where a halfhearted sort might actually be pretty useful  search result rankings, for instance. You want them in "relevance" order, but relevance is a nebulous thing, and you really don't care about the relative positions of items that are within about 5% of each other in relevance. If you can do better than O(n log n) complexity by not caring if the result is fully sorted, that might be worthwhile. Maybe even bonus points if the order of "close" values is nondeterministic.
So, thinking that someone had probably already thought about it (since there are so many articles even on purposely bad search algorithms), I looked around, but couldn't find anything. Does anyone know anything about halfhearted sorting algorithms? Or am I basically just talking about a specialized hash table?
(edit: my wordbrain isn't working well this evening)
So, thinking that someone had probably already thought about it (since there are so many articles even on purposely bad search algorithms), I looked around, but couldn't find anything. Does anyone know anything about halfhearted sorting algorithms? Or am I basically just talking about a specialized hash table?
(edit: my wordbrain isn't working well this evening)
Re: 1185: "Ineffective Sorts"
EugeneStyles wrote:Okay, so this comic got me thinking about sort algorithms again, as I sometimes do (thanks to whoever posted sleepsort, BTW, that's brilliant. Stupid, but brilliant), and especially the "halfhearted" sort got me thinking. I can think of some applications where a halfhearted sort might actually be pretty useful  search result rankings, for instance. You want them in "relevance" order, but relevance is a nebulous thing, and you really don't care about the relative positions of items that are within about 5% of each other in relevance. If you can do better than O(n log n) complexity by not caring if the result is fully sorted, that might be worthwhile. Maybe even bonus points if the order of "close" values is nondeterministic.
So, thinking that someone had probably already thought about it (since there are so many articles even on purposely bad search algorithms), I looked around, but couldn't find anything. Does anyone know anything about halfhearted sorting algorithms? Or am I basically just talking about a specialized hash table?
The halfhearted merge sort, as shown in the comic, don't even start to sort anything. It is completely useless. What can be more useful is a "halfhearted quicksort", where when reaching small enough partition size, it stops sorting instead of handing the small array to a insertion sort. But you only gain on the constant factor, it is still O(n lg n).
If you have many items with a convenient binary representation, like integers, MSB radix sort is probably the best choice, runs in O(n), and it can too be kinda stopped in the middle for a partially ordered array. But as you will be probably using radix sizes of 256, opportunities for stopping in the middle while keeping reasonable closeness will be narrow.
Re: 1185: "Ineffective Sorts"
I'm not real sure why, but I optimized sleepsort:
(Translated from Delphi as I post this, there may be bugs but hopefully you get the idea.)
It… looks like it's O(N).
Unrelated, I've coded three sorts in the past month or so — all based on bubble sort. Bubble sort is actually not that bad when N is very small… like the number of attributes in an RPG. The other two were garage games where it helps to run a partial bubble sort(one pass each direction, O(N)) each frame, as a halfhearted sort.
Code: Select all
PBYTE OrdSort(PBYTE pBytesToSort, int Length)
{
BOOL bMember[256];
int iSrc, iDst = 0, iMember;
//This part represents the spawning of the threads.
PBYTE Result = (PBYTE)malloc(Length); //Not an inplace sort.
for ( iMember = 0; iMember < 256; ++iMember ) bMember[iMember] = false;
for ( iSrc = 0; iSrc < Length; ++iSrc ) bMember[pBytesToSort[iSrc]] = true;
//This part represents the task scheduler dequeuing threads.
for ( iMember = 0; iMember < 256; ++iMember ) if ( bMember[iMember] )
for ( iSrc = 0; iSrc < Length; ++iSrc ) if ( pBytesToSort[iSrc] == iMember )
{
//This part represents the threads delivering their payloads.
Result[iDst] = iMember;
++iDst;
}
return Result;
}
(Translated from Delphi as I post this, there may be bugs but hopefully you get the idea.)
It… looks like it's O(N).
Spoiler:
Unrelated, I've coded three sorts in the past month or so — all based on bubble sort. Bubble sort is actually not that bad when N is very small… like the number of attributes in an RPG. The other two were garage games where it helps to run a partial bubble sort(one pass each direction, O(N)) each frame, as a halfhearted sort.
Re: 1185: "Ineffective Sorts"
Darekun wrote:I'm not real sure why, but I optimized sleepsort:Code: Select all
PBYTE OrdSort(PBYTE pBytesToSort, int Length)
{
BOOL bMember[256];
int iSrc, iDst = 0, iMember;
//This part represents the spawning of the threads.
PBYTE Result = (PBYTE)malloc(Length); //Not an inplace sort.
for ( iMember = 0; iMember < 256; ++iMember ) bMember[iMember] = false;
for ( iSrc = 0; iSrc < Length; ++iSrc ) bMember[pBytesToSort[iSrc]] = true;
//This part represents the task scheduler dequeuing threads.
for ( iMember = 0; iMember < 256; ++iMember ) if ( bMember[iMember] )
for ( iSrc = 0; iSrc < Length; ++iSrc ) if ( pBytesToSort[iSrc] == iMember )
{
//This part represents the threads delivering their payloads.
Result[iDst] = iMember;
++iDst;
}
return Result;
}
(Translated from Delphi as I post this, there may be bugs but hopefully you get the idea.)
It… looks like it's O(N).Spoiler:
Unrelated, I've coded three sorts in the past month or so — all based on bubble sort. Bubble sort is actually not that bad when N is very small… like the number of attributes in an RPG. The other two were garage games where it helps to run a partial bubble sort(one pass each direction, O(N)) each frame, as a halfhearted sort.
The enigma that is sleepsort just keeps getting more interesting to me, and I'm not exactly sure why. The audacity, for this sorting algorithm to join together such different concepts. I get the same unexplainable joy when I see physics take extreme liberties with mathematics to arrive at a good solution.
Thanks for sharing, Darekun!!
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: 1185: "Ineffective Sorts"
Darekun: With a few tweaks, to make it able to handle having input values that are equal, and the like... this essentially reduces to radix sort, which is O(n), but has a bunch of restrictions that apply to the input (eg the values you're sorting must be integers, and must have a compiletimefixed minimum and maximum range).
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: 1185: "Ineffective Sorts"
Appity wrote:The enigma that is sleepsort just keeps getting more interesting to me, and I'm not exactly sure why. The audacity, for this sorting algorithm to join together such different concepts.
There's also a deliberate conceptual brutality to it — it's not just deoptimizing a sort, it's using the deoptimization to do work "efficiently".
Appity wrote:Thanks for sharing, Darekun!!
Certainly!
phlip wrote:Darekun: With a few tweaks, to make it able to handle having input values that are equal, and the like... this essentially reduces to radix sort, which is O(n), but has a bunch of restrictions that apply to the input (eg the values you're sorting must be integers, and must have a compiletimefixed minimum and maximum range).
Mine does actually handle duplicates; otherwise you could get rid of the inner forif, leaving its contents running on the outer forif.
In a sense, the part that represents spawning threads detects the range — or did you mean in the sense that my implementation uses a range of 00hFFh? From the Wikipedia page, it looks like it'd be relatively easy to have item length as a parameter to a radix sort, and then run that many passes…
But, interesting, sleepsort is a deoptimized radix sort with only one pass. Since it's deoptimizing a fast sort, I guess the next question is what's the slowest sort we can apply this deoptimization to? :3
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: 1185: "Ineffective Sorts"
Darekun wrote:In a sense, the part that represents spawning threads detects the range — or did you mean in the sense that my implementation uses a range of 00hFFh?
Yeah, it's that the inputs are restricted to the range of a byte... so your code can loop from 0 to 255 and still call that O(1) since it's independent of the size of the input. If you make the range of the inputs unbounded then suddenly the length of that loop needs to vary with the input, or you need to do some kind of extra processing, and that affects the asymptotic runtime.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: 1185: "Ineffective Sorts"
Presenting:
SuperBogoSort!
Works in O(n!*j^n), where j = the number of possible elements.
SuperBogoSort!
Code: Select all
superBogoSort(input)
{
while (true)
{
// generate a list of random elements
candidate = generateRandomList(input.length);
// is our list sorted?
if (isSorted(candidate))
{
//does our list match the input?
check = shuffle(candidate);
if (input.equals(check))
return candidate;
}
}
}
Works in O(n!*j^n), where j = the number of possible elements.
Re: 1185: "Ineffective Sorts"
Why generate a random list of the same length? Feels like cheating!
Generate a random list of random length, then check if it's sorted, and then check if it matches a randomly shuffled version of the input.
Much better!
Generate a random list of random length, then check if it's sorted, and then check if it matches a randomly shuffled version of the input.
Much better!
Re: 1185: "Ineffective Sorts"
elasto wrote:Why generate a random list of the same length? Feels like cheating!
Generate a random list of random length, then check if it's sorted, and then check if it matches a randomly shuffled version of the input.
Much better!
And it's still only O(n^{2}) time for a nondeterministic computer (unless you also parallelise the check whether the two lists are permutations, in which case it's O(n) to check that the candidate is sorted, or O(1) if you also parallelise that)
Re: 1185: "Ineffective Sorts"
Manabu wrote:If you have many items with a convenient binary representation, like integers, MSB radix sort is probably the best choice, runs in O(n), and it can too be kinda stopped in the middle for a partially ordered array. But as you will be probably using radix sizes of 256, opportunities for stopping in the middle while keeping reasonable closeness will be narrow.
phlip wrote:Darekun: With a few tweaks, to make it able to handle having input values that are equal, and the like... this essentially reduces to radix sort, which is O(n), but has a bunch of restrictions that apply to the input (eg the values you're sorting must be integers, and must have a compiletimefixed minimum and maximum range).
For some reason, it really bugs me when I see radix sort described as O(n). It's better to think of it this way:
Given n elements from a set of size k distinct choices, radix sort works in O(n * log(k)).
There are a lot of algorithms like this  you can often choose between O(n * log(n)) and O(n * log(k)).
Darekun wrote:In a sense, the part that represents spawning threads detects the range — or did you mean in the sense that my implementation uses a range of 00hFFh? From the Wikipedia page, it looks like it'd be relatively easy to have item length as a parameter to a radix sort, and then run that many passes…
There used to be mechanical card sorters that were built around radix sort. They had 3 hoppers, and would divide cards in the input hopper into the 2 working hoppers on each pass, then stack them back in the input hopper for the next pass. Very cool to watch. They did, in fact, have the length as a control on the front  the one I remember had two knobs, one for start column and one for end column.
"In no set of physics laws do you get two cats."  doogly

 Posts: 98
 Joined: Mon Oct 18, 2010 9:49 am UTC
Re: 1185: "Ineffective Sorts"
lgw wrote:For some reason, it really bugs me when I see radix sort described as O(n). It's better to think of it this way:
Given n elements from a set of size k distinct choices, radix sort works in O(n * log(k)).
O(n+k)  k for clearing and reading the array, and n for inserting the elements in the middle, where:
 k >= n
 if it's appropriate, k is close to n
so describing an appropriate radix sort as O(n) works for me.
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: 1185: "Ineffective Sorts"
lgw wrote:For some reason, it really bugs me when I see radix sort described as O(n). It's better to think of it this way:
Given n elements from a set of size k distinct choices, radix sort works in O(n * log(k)).
Sure, that's fair. "k" is often a constant for a given implementation of radix sort, but for the algorithm in general it's certainly a parameter.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: 1185: "Ineffective Sorts"
Hate to be a necromancer and all that, but I just came across this:
https://github.com/drathier/stackoverflowimport
Gotta ask: is this in fact most awfully open to exploitation? Or is getting upvotes for malicious code on StackOverflow difficult enough that it's not as bad as it looks?
https://github.com/drathier/stackoverflowimport
Do you ever feel like all you’re doing is copy/pasting from Stack Overflow?
Let’s take it one step further.will go through the search resultsCode: Select all
from stackoverflow import quick_sort
of [python] quick sort looking for the largest code block that doesn’t
syntax error in the highest voted answer from the highest voted question
and return it as a module.
Gotta ask: is this in fact most awfully open to exploitation? Or is getting upvotes for malicious code on StackOverflow difficult enough that it's not as bad as it looks?
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: acunning40, BytEfLUSh and 117 guests