### Implementing Selection Sort in Python

#### What is Selection Sort?

Selection Sort is a comparison-based sorting algorithm. It works by dividing the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list, and a sublist of the remaining unsorted items. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on the sorting order) element from the unsorted sublist, swapping it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.

#### How Does Selection Sort Work?

Here’s a step-by-step breakdown of the Selection Sort algorithm:

1. **Find the minimum element** in the unsorted part of the list.

2. **Swap** the found minimum element with the first element of the unsorted part.

3. **Move the boundary** between the sorted and unsorted parts one element to the right.

4. **Repeat** the process until the entire list is sorted.

#### Selection Sort Algorithm in Python

Now, let's implement Selection Sort in Python:

```python

def selection_sort(arr):

n = len(arr)

for i in range(n):

# Assume the minimum is the first element

min_index = i

# Find the minimum element in the remaining unsorted array

for j in range(i + 1, n):

if arr[j] < arr[min_index]:

min_index = j

# Swap the found minimum element with the first element

arr[i], arr[min_index] = arr[min_index], arr[i]

return arr

```

#### Detailed Explanation of the Code

- **Initialize Variables:**

```python

n = len(arr)

```

We start by getting the length of the list `arr`.

- **Outer Loop:**

```python

for i in range(n):

```

The outer loop iterates over each element of the list, considering each element as the starting point for the unsorted sublist.

- **Assume Minimum:**

```python

min_index = i

```

We assume the current element (`arr[i]`) is the minimum in the unsorted part.

- **Inner Loop:**

```python

for j in range(i + 1, n):

if arr[j] < arr[min_index]:

min_index = j

```

The inner loop searches for the actual minimum element in the unsorted part of the list. If a smaller element is found, we update `min_index`.

- **Swap Elements:**

```python

arr[i], arr[min_index] = arr[min_index], arr[i]

```

After finding the minimum element in the unsorted part, we swap it with the first unsorted element (`arr[i]`).

- **Return Sorted List:**

```python

return arr

```

Finally, we return the sorted list.

#### Example Usage

Here’s how you can use the `selection_sort` function:

```python

if __name__ == "__main__":

unsorted_list = [64, 25, 12, 22, 11]

print("Unsorted list:", unsorted_list)

sorted_list = selection_sort(unsorted_list)

print("Sorted list:", sorted_list)

```

**Output:**

```

Unsorted list: [64, 25, 12, 22, 11]

Sorted list: [11, 12, 22, 25, 64]

```

#### Complexity Analysis

- **Time Complexity:**

- Best, Worst, and Average Case: O(n²)

- This is because we have two nested loops, each of which can run up to `n` times.

- **Space Complexity:**

- O(1)

- Selection Sort is an in-place sorting algorithm, meaning it requires a constant amount of extra memory.

#### Conclusion

Selection Sort is an excellent algorithm for educational purposes due to its simplicity. However, it is not efficient for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort, which have better average-case performance. Nonetheless, understanding Selection Sort provides a solid foundation for learning more complex sorting algorithms.

Experiment with the provided code and try modifying it to sort in descending order or to handle different data types. Happy coding!