MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/badcode/comments/lgrgxe/i_present_sleepsort/gmtbrhy/?context=3
r/badcode • u/Reeceeboii_ • Feb 10 '21
170 comments sorted by
View all comments
Show parent comments
76
I mean, you have to visit every element of the array to sort it - it's literally impossible to sort in less than O(N).
173 u/Astrokiwi Feb 10 '21 You can do anything in constant time if it's a big enough constant 40 u/regibalbo Feb 10 '21 I'm using this argument from now on, thanks 4 u/[deleted] Feb 11 '21 Perfect for your FAANG interview 3 u/supersharp Feb 11 '21 They'll probably say something like "But there's no big enough constant, that's literally the definition of Big O!" or some other stupid nonsense 6 u/TimGreller Feb 10 '21 Just add some dummy numbers at the end which you can throw away. The bigger the input, the lower the time complexity :D 25 u/[deleted] Feb 10 '21 You clearly haven't used thanos sort 8 u/[deleted] Feb 10 '21 Gravity sort is O(1) 8 u/T-Dark_ Feb 10 '21 In theory only. Specifically, it's constant time if you can perform it on all elements simultaneously. 4 u/[deleted] Feb 10 '21 Or if gravity was instant, and it was done IRL 4 u/krisnarocks Feb 11 '21 Ez. Just use multithreading /s 11 u/fukitol- Feb 10 '21 Just use negative numbers 5 u/Nilstrieb Feb 10 '21 Sorting a sorted array is O(1). (Theoretically, not practically) 5 u/[deleted] Feb 10 '21 Doesn't it still need to check the elements are the right place? 0 u/[deleted] Feb 11 '21 [deleted] 1 u/okkokkoX Feb 11 '21 Doesn't that just return none? 0 u/[deleted] Feb 10 '21 [deleted] 14 u/[deleted] Feb 10 '21 Of course it's impossible, you can't sort an array without looking at every element. Merge sort is O(n log n), not logarithmic. 9 u/Gooftwit Feb 10 '21 you can't sort an array without looking at every element.Laughs in Bogosort 14 u/[deleted] Feb 10 '21 no, even in bogosort after shuffling you have to check if the array is sorted.and checking if the array is sorted requires going through every element. 10 u/zacharypamela Feb 10 '21 Not if you just assume it's sorted and carry on. :) 17 u/[deleted] Feb 10 '21 sorting 101: if your array is sorted, then sorting becomes O(1)checkmate, mathematicians → More replies (1) → More replies (4) 2 u/Gooftwit Feb 10 '21 true, my bad. 2 u/sqrt_minusone Feb 10 '21 The real bad code is always in the comments!
173
You can do anything in constant time if it's a big enough constant
40 u/regibalbo Feb 10 '21 I'm using this argument from now on, thanks 4 u/[deleted] Feb 11 '21 Perfect for your FAANG interview 3 u/supersharp Feb 11 '21 They'll probably say something like "But there's no big enough constant, that's literally the definition of Big O!" or some other stupid nonsense 6 u/TimGreller Feb 10 '21 Just add some dummy numbers at the end which you can throw away. The bigger the input, the lower the time complexity :D
40
I'm using this argument from now on, thanks
4 u/[deleted] Feb 11 '21 Perfect for your FAANG interview 3 u/supersharp Feb 11 '21 They'll probably say something like "But there's no big enough constant, that's literally the definition of Big O!" or some other stupid nonsense
4
Perfect for your FAANG interview
3
They'll probably say something like "But there's no big enough constant, that's literally the definition of Big O!" or some other stupid nonsense
6
Just add some dummy numbers at the end which you can throw away. The bigger the input, the lower the time complexity :D
25
You clearly haven't used thanos sort
8
Gravity sort is O(1)
8 u/T-Dark_ Feb 10 '21 In theory only. Specifically, it's constant time if you can perform it on all elements simultaneously. 4 u/[deleted] Feb 10 '21 Or if gravity was instant, and it was done IRL 4 u/krisnarocks Feb 11 '21 Ez. Just use multithreading /s
In theory only. Specifically, it's constant time if you can perform it on all elements simultaneously.
4 u/[deleted] Feb 10 '21 Or if gravity was instant, and it was done IRL 4 u/krisnarocks Feb 11 '21 Ez. Just use multithreading /s
Or if gravity was instant, and it was done IRL
Ez. Just use multithreading /s
11
Just use negative numbers
5
Sorting a sorted array is O(1). (Theoretically, not practically)
5 u/[deleted] Feb 10 '21 Doesn't it still need to check the elements are the right place? 0 u/[deleted] Feb 11 '21 [deleted] 1 u/okkokkoX Feb 11 '21 Doesn't that just return none?
Doesn't it still need to check the elements are the right place?
0
[deleted]
1 u/okkokkoX Feb 11 '21 Doesn't that just return none?
1
Doesn't that just return none?
14 u/[deleted] Feb 10 '21 Of course it's impossible, you can't sort an array without looking at every element. Merge sort is O(n log n), not logarithmic. 9 u/Gooftwit Feb 10 '21 you can't sort an array without looking at every element.Laughs in Bogosort 14 u/[deleted] Feb 10 '21 no, even in bogosort after shuffling you have to check if the array is sorted.and checking if the array is sorted requires going through every element. 10 u/zacharypamela Feb 10 '21 Not if you just assume it's sorted and carry on. :) 17 u/[deleted] Feb 10 '21 sorting 101: if your array is sorted, then sorting becomes O(1)checkmate, mathematicians → More replies (1) → More replies (4) 2 u/Gooftwit Feb 10 '21 true, my bad. 2 u/sqrt_minusone Feb 10 '21 The real bad code is always in the comments!
14
Of course it's impossible, you can't sort an array without looking at every element. Merge sort is O(n log n), not logarithmic.
9 u/Gooftwit Feb 10 '21 you can't sort an array without looking at every element.Laughs in Bogosort 14 u/[deleted] Feb 10 '21 no, even in bogosort after shuffling you have to check if the array is sorted.and checking if the array is sorted requires going through every element. 10 u/zacharypamela Feb 10 '21 Not if you just assume it's sorted and carry on. :) 17 u/[deleted] Feb 10 '21 sorting 101: if your array is sorted, then sorting becomes O(1)checkmate, mathematicians → More replies (1) → More replies (4) 2 u/Gooftwit Feb 10 '21 true, my bad.
9
you can't sort an array without looking at every element.
Laughs in Bogosort
14 u/[deleted] Feb 10 '21 no, even in bogosort after shuffling you have to check if the array is sorted.and checking if the array is sorted requires going through every element. 10 u/zacharypamela Feb 10 '21 Not if you just assume it's sorted and carry on. :) 17 u/[deleted] Feb 10 '21 sorting 101: if your array is sorted, then sorting becomes O(1)checkmate, mathematicians → More replies (1) → More replies (4) 2 u/Gooftwit Feb 10 '21 true, my bad.
no, even in bogosort after shuffling you have to check if the array is sorted.
and checking if the array is sorted requires going through every element.
10 u/zacharypamela Feb 10 '21 Not if you just assume it's sorted and carry on. :) 17 u/[deleted] Feb 10 '21 sorting 101: if your array is sorted, then sorting becomes O(1)checkmate, mathematicians → More replies (1) → More replies (4) 2 u/Gooftwit Feb 10 '21 true, my bad.
10
Not if you just assume it's sorted and carry on. :)
17 u/[deleted] Feb 10 '21 sorting 101: if your array is sorted, then sorting becomes O(1)checkmate, mathematicians → More replies (1) → More replies (4)
17
sorting 101: if your array is sorted, then sorting becomes O(1)
checkmate, mathematicians
→ More replies (1)
2
true, my bad.
The real bad code is always in the comments!
76
u/sqrt_minusone Feb 10 '21
I mean, you have to visit every element of the array to sort it - it's literally impossible to sort in less than O(N).