I'm supposed to sort a list of numbers, but I'm super lazy. It's really hard to figure how to swap all the numbers around until all of them are in increasing order, so I cam up with my own algorithm that will guarantee that the new list is sorted¹. Here's how it works:
For a list of size N, we'll need N-1 iterations. On each iteration,
Check if the N'th number is smaller than the N+1'th number. If it is, then these two numbers are already sorted, and we can skip this iteration.
If they are not, then you need to continually decrement the first N numbers until these two numbers are in order.
Let's take a concrete example. Let's say the input was
10 5 7 6 1 On the first iteration, we'll compare 10 and 5. 10 is larger than 5, so we decrement it until it's smaller:
4 5 7 6 1 Now we compare 5 and 7. 5 is smaller than 7, so we don't need to do anything on this iteration. So we go to the next and compare 7 and 6. 7 is larger than 6, so we decrement the first three numbers until it's smaller than 6, and we get this:
2 3 5 6 1 Now we compare 6 and 1. Again, 6 is smaller than 1, so we decrement the first four numbers until it's smaller than 1, and we get this:
-4 -3 -1 0 1 And we're done! Now our list is in perfect sorted order. And, to make things even better, we only had to iterate through the list N-1 times, so this algorithm sorts lists in O(N-1) time, which I'm pretty sure is the fastest algorithm there is.²
Your challenge for today is to implement this Lazy Sort. Your program or function will be given an array of integers in whatever standard format you like, and you must perform this lazy sort and return the new "sorted" list. The array will never be empty or contain non-integers.
Here are some examples:
Input: 10 5 7 6 1 Output: -4 -3 -1 0 1 Input: 3 2 1 Output: -1 0 1 Input: 1 2 3 Output: 1 2 3 Input: 19 Output: 19 Input: 1 1 1 1 1 1 1 1 1 Output: -7 -6 -5 -4 -3 -2 -1 0 1 Input: 5 7 11 6 16 2 9 16 6 16 Output: -27 -25 -21 -20 -10 -9 -2 5 6 16 Input: -8 17 9 7 Output: -20 5 6 7 As always, this is code-golf, so write the shortest program you can!
¹ This doesn't mean what it sounds like it means, but it is technically true
² I am completely kidding, please don't hate me