1185: Ineffective Sorts

2013-03-13T18:57:40Z

77.179.85.233: /* Transcript */

{{comic
| number = 1185
| date = March 13, 2013
| title = Ineffective Sorts
| image = ineffective_sorts.png
| titletext = 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 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 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(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 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 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 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==
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]

{{comic discussion}}

explain xkcd - User contributions [en]

1185: Ineffective Sorts