this reminds me of the 4chan's sleepsort: for each number $n in the array, spin a thread that sleeps $n and then append $n to the result array.
Would the algorithmic runtime of this be O(N)?
[deleted]
Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
61–70 of 86 posts
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#62Hilariously awesome. I'm curious whether the multiple warnings about running untrusted code in the browser are necessary. I feel like all websites are already untrusted code, and the browser is quite well sandboxed and protected from anything too bad happening. What is the worst case scenario here for the user within the JS ecosystem, under known avenues of attack, not counting an unknown zero day browser exploit?
Some worst case scenarios:
- Your tab freezes due to an infinite loop for a while until your browser notices and asks you if you want to kill the script.
- The script downloads illegal content, and your ISP notifies authorities.
- CSRF attack against a site you're signed into that's not properly secured.
All of these things are things any site you go to can do. There's nothing special about `eval` that makes this site more dangerous.
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#63Hey, creator here! I built this a few years ago on a whim, and am surprised how well it still works. Thanks for sharing again :) (Psst, if you're an engineer and like dev tools, I'm hiring! https://readme.io/careers )
Is it terrible that I am highly tempted to use this as an API, forcing the value in via headless chrome then printing the page to a PDF and using OCR & regular expressions to extract a sorted list? I'm pretty sure that's an O(1) (ish, not really) which I always heard was the best kind.
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#64Earlier quoted context omitted.
Would the algorithmic runtime of this be O(N)?
No, the runtime complexity is just hidden in the scheduler of your OS
I don’t think this fully resolves the problem. If you had n computers and had each of them sleep for one of the numbers, and then append to a shared list, you could sort in O(n) without a scheduler.
My favorite part about this algorithm is that you can speed it up by a factor of k - for any k! - by simply dividing the time you sleep by by k.
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#65this reminds me of the 4chan's sleepsort: for each number $n in the array, spin a thread that sleeps $n and then append $n to the result array.
Would the algorithmic runtime of this be O(N)?
The O(N log N) best case only applies to comparison sorts. What's described here is not a comparison sort, and could easily be made O(N) with radix sort if the size of the numeric type is constant.
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#66Earlier quoted context omitted.
Would the algorithmic runtime of this be O(N)?
The O(N log N) best case only applies to comparison sorts. What's described here is not a comparison sort, and could easily be made O(N) with radix sort if the size of the numeric type is constant.
[deleted]
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#67Hey, creator here! I built this a few years ago on a whim, and am surprised how well it still works. Thanks for sharing again :) (Psst, if you're an engineer and like dev tools, I'm hiring! https://readme.io/careers )
Is it terrible that I am highly tempted to use this as an API, forcing the value in via headless chrome then printing the page to a PDF and using OCR & regular expressions to extract a sorted list? I'm pretty sure that's an O(1) (ish, not really) which I always heard was the best kind.
It's not O(1). You are only calling the API once, but if you put in a larger list the time will increase in accordance to whatever the complexity is of the sorting happening behind the scenes. Calling this O(1) would be like saying qsort is O(1) because you are only calling the function once.
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#68Relevant Python library (https://github.com/drathier/stack-overflow-import) and previous HN discussion (https://news.ycombinator.com/item?id=12868946).
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#69Wonder how long until this code pops up in some CTF....
Re: Stacksort – Searches StackOverflow for sorting functions and runs them (2013)
#70Doesn't seem to work. Tried with input ["z","b","a","c","d"] and returns the same ["z","b","a" "c","d"] as the output, using StackOverflow answer 4833835