Selection Sort Implementation

Implement the classic selection sort algorithm in pure Python.

sorting selection-sort algorithm in-place lists

Write a function `selection_sort(arr)` that takes a list of integers (or floats) and returns a new list sorted in ascending order using the selection sort algorithm. The input list should not be modified. Selection sort works by repeatedly finding the minimum element from the unsorted part and placing it at the beginning. Your implementation must follow this algorithm — do not use built-in sorting functions like `sorted()` or `list.sort()`. The algorithm should be implemented manually.

The function signature is:
```python
def selection_sort(arr):
    pass
```

**Details:**
- `arr` is a list of numbers (integers or floats).
- The function must return a new list sorted in ascending order.
- The original list must remain unchanged.
- You are expected to implement the selection sort algorithm explicitly (nested loops).

**Examples:**
- `selection_sort([64, 25, 12, 22, 11])` returns `[11, 12, 22, 25, 64]`.
- `selection_sort([3, 1, 2])` returns `[1, 2, 3]`.
- `selection_sort([])` returns `[]`.

Your solution will be tested with various lists, including empty, single-element, already sorted, reverse sorted, and lists with duplicates.

Constraints

Input constraints:
- `0 <= len(arr) <= 5000`
- Each element is an integer or float (no NaN or infinity).
- Time complexity: O(n^2) is acceptable, but aims for practical efficiency.
- Space complexity: O(n) for the new list, or O(1) extra space if you copy and sort in place (but the original must not be modified).

Example

>>> selection_sort([64, 25, 12, 22, 11])
[11, 12, 22, 25, 64]
>>> selection_sort([5, 2, 8, 1, 9, 3])
[1, 2, 3, 5, 8, 9]
>>> selection_sort([1])
[1]
>>> selection_sort([])
[]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of dividing the list into a sorted prefix and an unsorted suffix.

In each pass, find the index of the minimum element in the unsorted suffix.

Swap that minimum with the first element of the unsorted suffix (or build a new list by appending the minimum each time).

Remember to work on a copy of the input list so the original is not changed.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.