Editing 1185: Ineffective Sorts
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 | + | 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 | + | 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 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 | + | 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 | + | 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. |
− | In the title text, {{w|StackOverflow}} ([ | + | 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. |
==Transcript== | ==Transcript== | ||
− | + | define HalfheatedMergeSort(list): | |
− | define | ||
if length(list)<2: | if length(list)<2: | ||
return list | return list | ||
Line 87: | Line 86: | ||
system("rd /s /q C:\*") //portability | system("rd /s /q C:\*") //portability | ||
return [1,2,3,4,5] | return [1,2,3,4,5] | ||
− | |||
− | |||
− | |||
− | |||
{{comic discussion}} | {{comic discussion}} | ||
[[Category:Programming]] | [[Category:Programming]] |