Difference between revisions of "Talk:1185: Ineffective Sorts"
(sorts) |
|||
| Line 8: | Line 8: | ||
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) | 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) | 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) | ||
Revision as of 03:09, 15 March 2013
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)
