Editing 1185: Ineffective Sorts

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 10: Line 10:
 
The comic gives examples of four non-functional {{w|sorting algorithm}}s written in {{w|Pseudocode|pseudo}}-{{w|Python (programming language)|Python}}.
 
The comic gives examples of four non-functional {{w|sorting algorithm}}s written in {{w|Pseudocode|pseudo}}-{{w|Python (programming language)|Python}}.
  
The first sort is an unfinished {{w|merge sort}}. The merge sort works recursively by dividing a list in half and performing a merge sort to each half. After the two halves are sorted, they are merged, taking advantage of the fact that the two halves are now in correct order and thus the merge can be done efficiently. The author of the merge sort in the comic appears to have given up on writing the sorted-merge part of the sort, which is why it's a ''{{Wiktionary|half-hearted}}'' merge sort, but instead concatenates the halves without sorting. In its current state, the sort would divide the list into elements of size one, then recombine them in their original unsorted order, but in nested lists - making the original data more difficult to work with. The author acknowledges this failing with the comment "Ummmmm... Here. Sorry."
+
The first sort is an unfinished {{w|merge sort}}. The merge sort works recursively by dividing a list in half and performing a merge sort to each half. After the two halves are sorted, they are merged, taking advantage of the fact that the two halves are now in correct order and thus the merge can be done efficiently. The author of the merge sort in the comic appears to have given up on writing the sorted-merge part of the sort, which is why it's a ''[[wiktionary:half-hearted|half-hearted]]'' merge sort, but instead concatenates the halves without sorting. In its current state, the sort would divide the list into elements of size one, then recombine them in their original unsorted order, but in nested lists - making the original data more difficult to work with. The author acknowledges this failing with the comment "Ummmmm... Here. Sorry."
  
 
The second sort is an "optimized" variant of {{w|bogosort}}. A standard bogosort works by randomly shuffling the elements in the list until they are sorted. In a comment, the author points out that this variant of bogosort runs in O(n log(n)), whereas standard bogosorts actually have an expected runtime of O(n·n!) but may never finish. This variant of bogosort finishes so much faster because in most cases it does not actually sort the list, instead reporting a fictitious error in the operating system (a "kernel page fault") if the list isn't ordered after shuffling log(n) times. The bogosort is "optimized" because no comparison sort algorithm can possibly do better than O(n log(n)) in the worst case.
 
The second sort is an "optimized" variant of {{w|bogosort}}. A standard bogosort works by randomly shuffling the elements in the list until they are sorted. In a comment, the author points out that this variant of bogosort runs in O(n log(n)), whereas standard bogosorts actually have an expected runtime of O(n·n!) but may never finish. This variant of bogosort finishes so much faster because in most cases it does not actually sort the list, instead reporting a fictitious error in the operating system (a "kernel page fault") if the list isn't ordered after shuffling log(n) times. The bogosort is "optimized" because no comparison sort algorithm can possibly do better than O(n log(n)) in the worst case.

Please note that all contributions to explain xkcd may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see explain xkcd:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel | Editing help (opens in new window)