Inspired by one of many bugs I ran into while implementing selection sort in trilangle.
Given a non-empty list of non-negative integers, "sort" the list using the following procedure:
- Find and output the smallest value in the list.
- If the list only has one element, stop.
- Recurse on a sublist:
- If the last element in the list is the smallest, recurse on everything but the last value.
- Otherwise, recurse on everything but the first value.
Your code doesn't have to follow this procedure exactly, as long as the result is the same.
Sample implementation in JS:
function* sort(arr) {
if (arr.length === 1) {
return yield arr[0];
}
const min = Math.min(...arr);
yield min;
if (min === arr.at(-1)) {
arr.pop();
yield* sort(arr);
} else {
const [, ...rest] = arr;
yield* sort(rest);
}
}
Some notes on the algorithm:
- The output will always contain the same number of elements as the input.
- The input may contain duplicates.
- Every element in the output is an element of the input, but they don't necessarily appear the same number of times.
- The elements of the output will be in nondecreasing order.
I/O
I/O defaults apply. Since I don't see this mentioned there, I will explicitly add the following rule:
You are allowed to implement this destructively. If taking the input by reference, the input does not have to have the same value once the procedure is completed. Note that I use this in the sample implementation above: I call .pop() without copying the array first.
Examples
[4, 3, 1, 2] => [1, 1, 1, 2]
[1, 2, 3, 4] => [1, 2, 3, 4]
[3, 2, 1, 0] => [0, 1, 2, 3]
[1, 2, 3, 1] => [1, 1, 2, 3]
[101, 103, 101, 105] => [101, 101, 101, 105]
Scoring
This is code-golf, so shortest program (per language) wins.
