Hacker Times
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
ac42
on Oct 5, 2021
|
parent
|
context
|
favorite
| on:
Is this the simplest (and most surprising) sorting...
I am not clear why the proof is so long. By induction, the first i elements are already smaller than the A[i], so it's essentially an unoptimised version of
for i: 0..n-1 A[i] = min(A[i:n])
areyousure
on Oct 6, 2021
[–]
After the first iteration of the loop (and every other one too), A[i] is the maximum of the array, not the minimum.
ac42
on Oct 6, 2021
|
parent
[–]
Oh crap, now I see it. Thanks!
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
for i: 0..n-1 A[i] = min(A[i:n])