1185: Ineffective Sorts

Explain xkcd: It's 'cause you're dumb.
(Difference between revisions)
Jump to: navigation, search
(the merge is there, it doesn't sort)
Line 12: Line 12:
 
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 with a minimum number of comparisons. The sort will divide the list until it contains elements of size one, then would begin merging. However, the author of the merge sort in the comic appears to have given up on writing the sorting part of the sort (which is why it's a [[wiktionary:half-hearted|''half-hearted'']] merge sort). In its current state, the sort would divide the list into elements of size one, do nothing to them, and return the two halves of the original list.
 
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 with a minimum number of comparisons. The sort will divide the list until it contains elements of size one, then would begin merging. However, the author of the merge sort in the comic appears to have given up on writing the sorting part of the sort (which is why it's a [[wiktionary:half-hearted|''half-hearted'']] merge sort). In its current state, the sort would divide the list into elements of size one, do nothing to them, and return the two halves of the original list.
  
The second sort is a {{w|bogosort}}, a sort that works by randomly shuffling the elements in the list. In a comment, the author claims the sort will run in O(nlog(n)) time, when bogosorts actually run in O(n*n!) time and may never finish. The author cheats this limitation by reporting a fictitious error in the operating system (a "kernel page fault") if the list isn't ordered after shuffling log(n) times.
+
The second sort is a {{w|bogosort}}, a sort that works by randomly shuffling the elements in the list. In a comment, the author claims the sort will run in O(n log(n)) time, when bogosorts actually run in O(n·n!) time and may never finish. The author cheats this limitation by reporting a fictitious error in the operating system (a "kernel page fault") if the list isn't ordered after shuffling log(n) times.
  
 
The third sort parodies a programmer explaining a {{w|quicksort}} during a job interview. The quicksort works by choosing an index as a pivot value and sorting all elements less than the pivot before the pivot and all the elements greater than the pivot after the pivot. It then does a quicksort to the section less than the pivot and the section greater than the pivot until the whole list is sorted. The interviewee flounders for a little while, then asks whether he can use the standard libraries to call a quicksort. Using the standard library's quicksort would allow the programmer to successfully execute a quicksort, but would not demonstrate that he knows how it works.
 
The third sort parodies a programmer explaining a {{w|quicksort}} during a job interview. The quicksort works by choosing an index as a pivot value and sorting all elements less than the pivot before the pivot and all the elements greater than the pivot after the pivot. It then does a quicksort to the section less than the pivot and the section greater than the pivot until the whole list is sorted. The interviewee flounders for a little while, then asks whether he can use the standard libraries to call a quicksort. Using the standard library's quicksort would allow the programmer to successfully execute a quicksort, but would not demonstrate that he knows how it works.
  
The final sort is just a mess. First it checks to see if the list is sorted, and exits if it is. Then it cuts the list 10,000 times (like a deck of cards) and exits if the list is sorted. Next, in desperation, it checks if the list is sorted three times. It then empties the list, tries to shutdown the computer and attempts to delete first the current directory, second the user's home directory, and finally the entire file system. {{w|rm (Unix)|rm}} is a POSIX command; the -r and -f flags mean that the remove command will remove all contents of the specified directories and will not prompt the user beforehand. The program next runs {{w|rmdir|rd}}, the windows equivalent of rm, in an attempt to delete the "C:" drive. The /s flag does the same thing as -r and the /q flag does the same thing as -f. Finally, the program returns a list containing the numbers one through five in order.
+
The final sort is just a mess. First it checks to see if the list is sorted, and exits if it is. Then it cuts the list 10,000 times (like a deck of cards) and exits if the list is sorted. Next, in desperation, it checks if the list is sorted three times. It then empties the list, tries to shutdown the computer and attempts to delete first the current directory, second the user's home directory, and finally the entire file system. {{w|rm (Unix)|rm}} is a POSIX command; the -r and -f flags mean that the remove command will remove all contents of the specified directories and will not prompt the user beforehand. The program next runs the Windows {{w|rmdir|rd}} command with switches to delete all files from the "C:" drive. Finally, the program returns a list containing the numbers one through five in order.
  
 
In the title text, {{w|StackOverflow}} ([http://stackoverflow.com/ link]) is a question-and-answer site where programmers can ask and answer questions on programming.
 
In the title text, {{w|StackOverflow}} ([http://stackoverflow.com/ link]) is a question-and-answer site where programmers can ask and answer questions on programming.

Revision as of 03:19, 16 March 2013

Ineffective Sorts
StackSort connects to StackOverflow, searches for 'sort a list', and downloads and runs code snippets until the list is sorted.
Title text: StackSort connects to StackOverflow, searches for 'sort a list', and downloads and runs code snippets until the list is sorted.

Explanation

The comic gives examples of four non-functional sorting algorithms written in pseudo-Python.

The first sort is an unfinished 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 with a minimum number of comparisons. The sort will divide the list until it contains elements of size one, then would begin merging. However, the author of the merge sort in the comic appears to have given up on writing the sorting part of the sort (which is why it's a half-hearted merge sort). In its current state, the sort would divide the list into elements of size one, do nothing to them, and return the two halves of the original list.

The second sort is a bogosort, a sort that works by randomly shuffling the elements in the list. In a comment, the author claims the sort will run in O(n log(n)) time, when bogosorts actually run in O(n·n!) time and may never finish. The author cheats this limitation by reporting a fictitious error in the operating system (a "kernel page fault") if the list isn't ordered after shuffling log(n) times.

The third sort parodies a programmer explaining a quicksort during a job interview. The quicksort works by choosing an index as a pivot value and sorting all elements less than the pivot before the pivot and all the elements greater than the pivot after the pivot. It then does a quicksort to the section less than the pivot and the section greater than the pivot until the whole list is sorted. The interviewee flounders for a little while, then asks whether he can use the standard libraries to call a quicksort. Using the standard library's quicksort would allow the programmer to successfully execute a quicksort, but would not demonstrate that he knows how it works.

The final sort is just a mess. First it checks to see if the list is sorted, and exits if it is. Then it cuts the list 10,000 times (like a deck of cards) and exits if the list is sorted. Next, in desperation, it checks if the list is sorted three times. It then empties the list, tries to shutdown the computer and attempts to delete first the current directory, second the user's home directory, and finally the entire file system. rm is a POSIX command; the -r and -f flags mean that the remove command will remove all contents of the specified directories and will not prompt the user beforehand. The program next runs the Windows rd command with switches to delete all files from the "C:" drive. Finally, the program returns a list containing the numbers one through five in order.

In the title text, StackOverflow (link) is a question-and-answer site where programmers can ask and answer questions on programming.

Transcript

define HalfheatedMergeSort(list):
    if length(list)<2:
        return list
    pivot=int(length(list)/2)
    a=HalfheartedMergeSort(list[:pivot])
    b=HalfheartedMergeSort(list[pivot:])
    // ummmmm
    return [a,b] // Here. Sorry.
define FastBogoSort(list):
    // An optimized BogoSort
    // Runs in O(n log n)
    for n from 1 to log(length(list)):
        shuffle(list):
        if isSorted(list):
            return list
    return "Kernel Page Fault (Error code: 2)"
define JobInterviewQuicksort(list):
    Ok so you choose a pivot
    Then divide the list in half
    for each half:
        check to see if it's sorted
            no, wait, it doesn't matter
        compare each element to the pivot
            the bigger ones go in a new list
            the equal ones go into, uh
            the second list from before
        hang on, let me name the lists
            this is list A
            the new one is list B
        put the big ones into list B
        now take the second list
            call it list, uh, A2
        which one was the pivot in?
        scratch all that
        it just recursively calls itself
        until both lists are empty
            right?
        not empty, but you know what I mean
    am I allowed to use the standard libraries?
define PanicSort(list):
    if isSorted(list):
        return list
    for n from 1 to 10000:
        pivot=random(0,length(list))
        list=list[pivot:]+list[:pivot]
        if isSorted(list):
            return list
    if isSorted(list):
        return list:
    if isSorted(list): //this can't be happening
        return list
    if isSorted(list): //come on come on
        return list
    // oh jeez
    // i'm gonna be in so much trouble
    list=[]
    system("shutdown -h +5")
    system("rm -rf ./")
    system("rm -rf ~/*")
    system("rm -rf /")
    system("rd /s /q C:\*") //portability
    return [1,2,3,4,5]
comment.png add a comment!

Discussion

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)
Personal tools
Namespaces

Variants
Actions
Navigation
Tools

It seems you are using noscript, which is stopping our project wonderful ads from working. Explain xkcd uses ads to pay for bandwidth, and we manually approve all our advertisers, and our ads are restricted to unobtrusive images and slow animated GIFs. If you found this site helpful, please consider whitelisting us.

Want to advertise with us, or donate to us with Paypal or Bitcoin?