| Latest revision |
Your text |
| Line 6: |
Line 6: |
| | | titletext = StackSort connects to StackOverflow, searches for 'sort a list', and downloads and runs code snippets until the list is sorted. | | | titletext = StackSort connects to StackOverflow, searches for 'sort a list', and downloads and runs code snippets until the list is sorted. |
| | }} | | }} |
| | + | |
| | | | |
| | ==Explanation== | | ==Explanation== |
| − | 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 sorting algorithms written in pseudo 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 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 first sort is an unfinished merge sort. The merge sort works recursively, dividing itself in half and doing 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 merge part of the 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 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 they can use the standard libraries to call a quicksort. The joke being, the standard library contains a quicksort, and the programmer would rather rely on that (possibly even pass it off as his own work) than his own example of quicksort. While it's commonly a good idea in real projects, this would surely count as a failure on interview. | + | The second sort is a bogosort, a sort that works by randomly shuffling the elements in the list. It claims to run in O(nlog(n)) time although bogosorts typically run in O(n*n!) time and may never finish. It achieves this by returning an error if the list isn't ordered after shuffling log(n) times. |
| | | | |
| − | The final sort is just a mess. First it checks to see if the list is sorted, and exits if it is. Then it rotates the list by a random amount 10,000 times (as if cutting a deck of cards) and exits if the list is ever sorted. Next, in desperation, it checks if the list is sorted three times. Finally, realizing that they have no chance of success, the author performs the computer equivalent of a {{tvtropes|RageQuit|Rage Quit}} and attempts to destroy the computer rather than admit defeat. First, the program attempts to schedule a shutdown of the computer in five minutes, then attempts to delete the current directory, then attempts to delete the user's home directory (presumably the grader's files), and finally all the files on the computer. {{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. Under the guise of "{{w|Software portability|portability}}", the program runs the equivalent Windows {{w|rmdir|rd}} command with switches to delete all files from the "C:" drive without prompting. Finally, the program returns a list containing the numbers one through five in order. | + | The third sort parodies a programmer explaining a quicksort during a job interview. The quicksort works by choosing a 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 they know how it works. |
| | | | |
| − | In the title text, {{w|StackOverflow}} ([https://stackoverflow.com/ link]) is a question-and-answer site where programmers can ask and answer questions on programming. The author of this code takes advantage of the hopes that someone on StackOverflow knows what they are doing and has posted code to sort a list... ''and somebody [https://github.com/gkoberger/stacksort/ implemented stacksort]; well, sort of.''
| + | 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 gnu 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 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. |
| | | | |
| | ==Transcript== | | ==Transcript== |
| − | :'''Ineffective sorts'''
| + | <!-- The transcript can be found in a hidden <div> element on the xkcd comic's html source, with id "transcript". |
| − | define HalfheartedMergeSort(list):
| + | -- Tip: Use colons (:) in the beginning of lines to preserve the original line breaks. |
| − | if length(list)<2:
| + | -- Any actions or descriptive lines in [[double brackets]] should be reduced to [single brackets] to avoid wikilinking |
| − | return list
| + | -- Do not include the title text again here --> |
| − | 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]
| |
| − | | |
| − | == Trivia ==
| |
| − | | |
| − | * [https://xkcd.com/about/ xkcd's ''about'' section] has an FAQ about sorting algorithms. It mentions both quicksort and job interviews.
| |
| | | | |
| | {{comic discussion}} | | {{comic discussion}} |
| − | [[Category:Programming]]
| + | <!-- Include any categories below this line--> |
