Talk:1185: Ineffective Sorts
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)
- Idk who is reading explain for interview advice but: know quicksort and mergesort cold, maybe timsort (modified merge, neat) or heapsort (you need to know heaps anyway) and I'm pretty sure you're good. I've never heard of anyone being hired or not based on knowing more obscure sorters. Singlelinelabyrinth (talk) 05:13, 26 July 2020 (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)
- For anyone still reading this in 2026 the answer is that it is a syntax error. The code will not compile (or abort at that point using a truly primitive interpreter). Perhaps Randall accidentally added it there? (I suspect he put it there on purpose, though, as part of the interviewee’s incompetence) Dúthomhas (talk) 07:00, 6 June 2026 (UTC)
I'd always thought that the author of the panicsort was trying to destroy the evidence that they failed. Ragequitting is an interesing interpretation. 162.158.74.109 03:20, 20 October 2020 (UTC)
the portability part killed me haha:
- also the job interview one was the best one An user who has no account yet (talk) 08:04, 7 September 2023 (UTC)
well now rm -rf / need the --no-preserve-root flag or the system will refuse deleting.--DaadfroGG (talk) 11:37, 24 August 2024 (UTC)
What about more optimized Bogosort:
Define ActuallyFastBogoSort(list):
Counter = 0
While Counter == 0:
Shuffle(list)
if issorted(list):
Counter += 1
Return list
Will this version properly work? Or can it be modified some more? --172.69.223.54 20:17, 24 December 2024 (UTC)
---
JobInterviewQuickSort in Python:
def job_interview_quick_sort(lst: list) -> list:
pivot = choice(lst) # OK so you choose a pivot
# Then divide the list in half
list1 = lst[:pivot]
list2 = lst[pivot:]
for half in [list1, list2]: # For each half
if half == sorted(half): # Check to see if it's sorted
pass # No, wait, it doesn't matter
new_list = []
# Compare each element to the pivot
for element in half:
if element > pivot: # The bigger ones go in a new list
new_list.append(element)
elif element == pivot: # The equal ones go into, uh
list2.append(element) # The second list from before
# Hang on, let me name the lists
list_a = list1 # This is list A
list_b = new_list # The new one is list B
# Put the big ones into list B
list_b += big_ones := [elem for elem in list_a if elem > pivot]
# Now take the second list
list_a2 = list2 # Call it list, uh, A2
input("Which one was the pivot in?")
# Scratch all that
def scratch_all_that(): ...
scratch_all_that()
# It just recursively calls itself
# Until both lists are empty
while list1 and list2:
job_interview_quick_sort(lst)
# Right?
# Not empty, but you know what I mean
assert "you know what I mean"
input("Am I allowed to use the standard libraries?")