### Implementing Selection Sort in Python: Step-by-Step
Selection Sort is a simple and intuitive sorting algorithm, ideal for beginners to understand the basic concepts of sorting. In this blog post, we'll explore how Selection Sort works and visualize its step-by-step process with an example. We'll also provide a Python implementation of the algorithm.
#### What is Selection Sort?
Selection Sort is a comparison-based algorithm that divides the input list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region. The process continues until the entire list is sorted.
#### Step-by-Step Example
Let's walk through an example to see how Selection Sort works in practice. Consider the following unsorted array:
```
[64, 25, 12, 22, 11]
```
We will sort this array in ascending order using Selection Sort.
1. **Initial Array:**
```
[64, 25, 12, 22, 11]
```
2. **First Pass (i = 0):**
- Find the minimum element in the unsorted part `[64, 25, 12, 22, 11]`, which is `11`.
- Swap `11` with the first element `64`.
- Array after the first pass:
```
[11, 25, 12, 22, 64]
```
3. **Second Pass (i = 1):**
- Find the minimum element in the unsorted part `[25, 12, 22, 64]`, which is `12`.
- Swap `12` with the second element `25`.
- Array after the second pass:
```
[11, 12, 25, 22, 64]
```
4. **Third Pass (i = 2):**
- Find the minimum element in the unsorted part `[25, 22, 64]`, which is `22`.
- Swap `22` with the third element `25`.
- Array after the third pass:
```
[11, 12, 22, 25, 64]
```
5. **Fourth Pass (i = 3):**
- Find the minimum element in the unsorted part `[25, 64]`, which is `25`.
- Since `25` is already in its correct position, no swap is needed.
- Array after the fourth pass:
```
[11, 12, 22, 25, 64]
```
6. **Fifth Pass (i = 4):**
- Only one element `[64]` is left, which is already sorted.
The array is now fully sorted:
```
[11, 12, 22, 25, 64]
```
#### Python Implementation
Here's how you can 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
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 running up to `n` times.
- **Space Complexity:**
- O(1)
- Selection Sort is an in-place sorting algorithm, requiring a constant amount of extra memory.
#### Conclusion
Questions
### 5 Programming Assignments Using Selection Sort
Selection Sort is a fundamental sorting algorithm that helps build a strong understanding of sorting techniques. Here are five programming assignments to deepen your understanding and proficiency with Selection Sort:
#### Assignment 1: Basic Selection Sort Implementation
**Objective:** Write a function to implement Selection Sort and sort an array of integers in ascending order.
**Details:**
- Function Signature: `def selection_sort(arr: list) -> list:`
- Input: A list of integers.
- Output: A sorted list of integers in ascending order.
- Example:
```python
arr = [29, 10, 14, 37, 14]
print(selection_sort(arr)) # Output: [10, 14, 14, 29, 37]
```
#### Assignment 2: Selection Sort in Descending Order
**Objective:** Modify the basic Selection Sort algorithm to sort an array of integers in descending order.
**Details:**
- Function Signature: `def selection_sort_desc(arr: list) -> list:`
- Input: A list of integers.
- Output: A sorted list of integers in descending order.
- Example:
```python
arr = [29, 10, 14, 37, 14]
print(selection_sort_desc(arr)) # Output: [37, 29, 14, 14, 10]
```
#### Assignment 3: Selection Sort for Strings
**Objective:** Implement Selection Sort to sort an array of strings based on their alphabetical order.
**Details:**
- Function Signature: `def selection_sort_strings(arr: list) -> list:`
- Input: A list of strings.
- Output: A sorted list of strings in alphabetical order.
- Example:
```python
arr = ["apple", "orange", "banana", "grape"]
print(selection_sort_strings(arr)) # Output: ['apple', 'banana', 'grape', 'orange']
```
#### Assignment 4: Sorting an Array of Tuples
**Objective:** Implement Selection Sort to sort an array of tuples based on the second element of each tuple.
**Details:**
- Function Signature: `def selection_sort_tuples(arr: list) -> list:`
- Input: A list of tuples where each tuple contains two elements.
- Output: A sorted list of tuples based on the second element of each tuple.
- Example:
```python
arr = [(1, 3), (4, 2), (2, 5), (3, 1)]
print(selection_sort_tuples(arr)) # Output: [(3, 1), (4, 2), (1, 3), (2, 5)]
```
#### Assignment 5: Finding the k-th Smallest Element
**Objective:** Use Selection Sort to find the k-th smallest element in an unsorted array.
**Details:**
- Function Signature: `def kth_smallest_element(arr: list, k: int) -> int:`
- Input: A list of integers and an integer `k` (1 ≤ k ≤ len(arr)).
- Output: The k-th smallest element in the sorted list.
- Example:
```python
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(kth_smallest_element(arr, k)) # Output: 7
```
### Solutions
Here are the solutions for each assignment:
#### Solution 1: Basic Selection Sort Implementation
```python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
```
#### Solution 2: Selection Sort in Descending Order
```python
def selection_sort_desc(arr):
n = len(arr)
for i in range(n):
max_index = i
for j in range(i + 1, n):
if arr[j] > arr[max_index]:
max_index = j
arr[i], arr[max_index] = arr[max_index], arr[i]
return arr
```
#### Solution 3: Selection Sort for Strings
```python
def selection_sort_strings(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
```
#### Solution 4: Sorting an Array of Tuples
```python
def selection_sort_tuples(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j][1] < arr[min_index][1]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
```
#### Solution 5: Finding the k-th Smallest Element
```python
def kth_smallest_element(arr, k):
sorted_arr = selection_sort(arr)
return sorted_arr[k - 1]
```
Contact us for software training, education or development
.png)
0 Comments