Difference between revisions of "Talk:1185: Ineffective Sorts"

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
(14 intermediate revisions by 9 users not shown)
Line 3: Line 3:
 
I lost it on //portability. It's a sad state where I've actually more or less come across 3 of these. [[Special:Contributions/203.126.136.142|203.126.136.142]] 00:56, 14 March 2013 (UTC)
 
I lost it on //portability. It's a sad state where I've actually more or less come across 3 of these. [[Special:Contributions/203.126.136.142|203.126.136.142]] 00:56, 14 March 2013 (UTC)
  
Audiovisual aid circa 1980, eh: '''http://youtube.com/watch?v=gv0JUEqaAXo#t=236s''' [[Special:Contributions/98.111.152.198|98.111.152.198]] 01:35, 14 March 2013 (UTC)
+
Audiovisual aid circa 1981, eh: '''http://youtube.com/watch?v=gv0JUEqaAXo#t=236s''' [[Special:Contributions/98.111.152.198|98.111.152.198]] 01:35, 14 March 2013 (UTC)
 +
 
 +
One of xkcd's best in a quite a while, imo. [[User:Alpha|Alpha]] ([[User talk:Alpha|talk]]) 03:39, 14 March 2013 (UTC)
 +
 
 +
Saying "bogosorts actually run in O(n*n!) time and may never finish" is a contradiction. Not the runtime is in O(n*n!), but the ''expected'' runtime.  [[User:BKA|BKA]] ([[User talk:BKA|talk]]) 08:19, 14 March 2013 (UTC)
 +
:Not necessarily. O(n*n!) is the expected runtime, but unlike other sorts, there is no max runtime which is what it is trying to say.[[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC)
 +
Didn't the author of the halfhearted merge sort give up on the sort part of the merge sort? 'cause merging is done in the return[a,b] part as far is see it...[[Special:Contributions/193.175.223.10|193.175.223.10]] 18:00, 14 March 2013 (UTC)
 +
[[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC)Well return[a,b] merges them in exactly the original order. So I think you are right. It recursively cuts the list into tiny bits and returns the uncut back to the previous call. [[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC)
 +
:The list is sorted when the already sorted sublists are merged. This is an efficient way to sort because only the lowest values in each sublist need to be compared so fewer comparisons are required. The author of the halfhearted merge sort did not write a proper merge (or any merge) and instead returns the sublists in the original order. Sublists of length one are known to be in the correct order which is why the list is recursively cut into units of length one.[[Special:Contributions/24.60.69.41|24.60.69.41]] 22:44, 17 March 2013 (
 +
 
 +
Did nobody notice that the POSIX/UNIX commands are uppercase, when they are supposed to be case-sensitive lowercase?  If you actually call system() with those arguments (in Linux), you don't delete anything and just get the "command not found" error. --[[Special:Contributions/138.67.185.73|138.67.185.73]] 01:41, 21 March 2013 (UTC)
 +
: It's possible they ''are'' meant to be lowercase, as parts of this comic appear to be written in <span style="font-variant:small-caps">Mixed-case Small Caps</span>. Look at the top lines of each program, for example. --[[User:Aaron of Mpls|Aaron of Mpls]] ([[User talk:Aaron of Mpls|talk]]) 06:59, 5 April 2013 (UTC)
 +
 
 +
Did anyone see this hint on the about page (http://xkcd.com/about/):
 +
 
 +
"Which sorting algorithms should I use? They taught me so many.
 +
 
 +
This is tricky. Most of what they teach you in school is just as an example of how to think about algorithms; 99% of the time you shouldn't worry about optimizing your sorts. Just learn to implement Quicksort (which is very good) and use that without fretting about it too much. People overfocus on efficiency over clarity and simplicity. And most of the time the environment you're coding in will have an efficient sort function built-in anyway.
 +
 
 +
Note: If you're interviewing for a company for a position with a focus on algorithms, the above is not an excuse not to know your stuff."
 +
 
 +
--[[User:RagnarDa|RagnarDa]] ([[User talk:RagnarDa|talk]]) 20:07, 7 April 2013 (UTC)
 +
 
 +
For the PanicSort, is the second "Return list:" intentionally having a : at the end? If yes, what does it do? [[User:Logo|Logo]] ([[User talk:Logo|talk]]) 10:47, 9 May 2014 (UTC)

Revision as of 10:47, 9 May 2014

I loved the "runs in O(n log n)" part. 76.106.251.87 00:16, 14 March 2013 (UTC)

I lost it on //portability. It's a sad state where I've actually more or less come across 3 of these. 203.126.136.142 00:56, 14 March 2013 (UTC)

Audiovisual aid circa 1981, eh: http://youtube.com/watch?v=gv0JUEqaAXo#t=236s 98.111.152.198 01:35, 14 March 2013 (UTC)

One of xkcd's best in a quite a while, imo. Alpha (talk) 03:39, 14 March 2013 (UTC)

Saying "bogosorts actually run in O(n*n!) time and may never finish" is a contradiction. Not the runtime is in O(n*n!), but the expected runtime. BKA (talk) 08:19, 14 March 2013 (UTC)

Not necessarily. O(n*n!) is the expected runtime, but unlike other sorts, there is no max runtime which is what it is trying to say.206.181.86.98 03:09, 15 March 2013 (UTC)

Didn't the author of the halfhearted merge sort give up on the sort part of the merge sort? 'cause merging is done in the return[a,b] part as far is see it...193.175.223.10 18:00, 14 March 2013 (UTC) 206.181.86.98 03:09, 15 March 2013 (UTC)Well return[a,b] merges them in exactly the original order. So I think you are right. It recursively cuts the list into tiny bits and returns the uncut back to the previous call. 206.181.86.98 03:09, 15 March 2013 (UTC)

The list is sorted when the already sorted sublists are merged. This is an efficient way to sort because only the lowest values in each sublist need to be compared so fewer comparisons are required. The author of the halfhearted merge sort did not write a proper merge (or any merge) and instead returns the sublists in the original order. Sublists of length one are known to be in the correct order which is why the list is recursively cut into units of length one.24.60.69.41 22:44, 17 March 2013 (

Did nobody notice that the POSIX/UNIX commands are uppercase, when they are supposed to be case-sensitive lowercase? If you actually call system() with those arguments (in Linux), you don't delete anything and just get the "command not found" error. --138.67.185.73 01:41, 21 March 2013 (UTC)

It's possible they are meant to be lowercase, as parts of this comic appear to be written in Mixed-case Small Caps. Look at the top lines of each program, for example. --Aaron of Mpls (talk) 06:59, 5 April 2013 (UTC)

Did anyone see this hint on the about page (http://xkcd.com/about/):

"Which sorting algorithms should I use? They taught me so many.

This is tricky. Most of what they teach you in school is just as an example of how to think about algorithms; 99% of the time you shouldn't worry about optimizing your sorts. Just learn to implement Quicksort (which is very good) and use that without fretting about it too much. People overfocus on efficiency over clarity and simplicity. And most of the time the environment you're coding in will have an efficient sort function built-in anyway.

Note: If you're interviewing for a company for a position with a focus on algorithms, the above is not an excuse not to know your stuff."

--RagnarDa (talk) 20:07, 7 April 2013 (UTC)

For the PanicSort, is the second "Return list:" intentionally having a : at the end? If yes, what does it do? Logo (talk) 10:47, 9 May 2014 (UTC)