Selection Sort

Selection Sort is one of the classic sorting algorithms used to sort a given array or collection of elements. It works by selecting the smallest element from the unsorted part of the array and placing it at the beginning of the array. This process is repeated until all elements are sorted. Selection Sort is an in-place sorting algorithm with a time complexity of O(n2) in the worst, average, and best cases. It is not an efficient algorithm because it requires O(n) space in the worst case. In this article, we will take a detailed look at how Selection Sort works and its time and space complexities. We will also look at a Python implementation of Selection Sort and some coding exercises to test your understanding.

What is Selection Sort?

Selection Sort is a sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning of the array. This process is repeated until all elements are sorted. The algorithm divides the array into two parts: a sorted part, which is initially empty, and an unsorted part, which contains all the elements. Then, it selects the smallest element from the unsorted part and places it at the end of the sorted part. This process is repeated until all elements are sorted.

Selection Sort Algorithm

The Selection Sort algorithm works as follows:

• Divide the array into two parts: a sorted part and an unsorted part.
• Select the smallest element from the unsorted part of the array.
• Swap the selected element with the element at the beginning of the unsorted part of the array.
• Move the element at the beginning of the unsorted part of the array to the end of the sorted part of the array.
• Repeat steps 2-4 until all elements are sorted.

Selection Sort in Python

Let’s now look at a Python implementation of the Selection Sort algorithm. The following Python code implements the Selection Sort algorithm:

def selection_sort(arr):
    # Iterate over the array
    for i in range(len(arr)):
        # Find the minimum element in the unsorted part of the array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        # Swap the minimum element with the element at the beginning of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = [3, 4, 1, 5, 2]
selection_sort(arr)
print(arr) # Output: [1, 2, 3, 4, 5]

In the above code, we first define a function selection_sort(). This function takes an array as an argument and sorts it using the Selection Sort algorithm. The function iterates over the array and finds the minimum element in the unsorted part of the array. Then, it swaps the minimum element with the element at the beginning of the unsorted part. This process is repeated until all elements are sorted. Finally, we test the code by creating an array and passing it to the selection_sort() function.

Time Complexity

The time complexity of Selection Sort depends on the number of elements in the array. The best case time complexity of Selection Sort is O(n2). This occurs when the array is already sorted and the algorithm needs to iterate over the array only once. The average and worst case time complexities of Selection Sort are also O(n2). This is because the algorithm needs to compare all elements in the array for each iteration.

Space Complexity

The space complexity of Selection Sort is O(n). This is because the algorithm needs to store the minimum element for each iteration.

Conclusion

In this article, we discussed Selection Sort, a classic sorting algorithm used to sort an array. We looked at how Selection Sort works and its time and space complexities. We also looked at a Python implementation of Selection Sort and some coding exercises to test your understanding. Selection Sort is an in-place sorting algorithm with time complexity of O(n2) in the worst, average, and best cases. It is not an efficient algorithm because it requires O(n) space in the worst case.

Exercises

def selection_sort(arr):
    # Iterate over the array
    for i in range(len(arr)):
        # Find the minimum element in the unsorted part of the array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        # Swap the minimum element with the element at the beginning of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = [3, 4, 1, 5, 2]
selection_sort(arr)
print(arr) # Output: [1, 2, 3, 4, 5]

def selection_sort(arr):
    # Iterate over the array
    for i in range(len(arr)):
        # Find the minimum element in the unsorted part of the array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        # Swap the minimum element with the element at the beginning of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = ["cat", "dog", "bird", "fish"]
selection_sort(arr)
print(arr) # Output: ["bird", "cat", "dog", "fish"]

def selection_sort(arr):
    # Iterate over the array
    for i in range(len(arr)):
        # Find the minimum element in the unsorted part of the array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx][0] > arr[j][0]:
                min_idx = j
        # Swap the minimum element with the element at the beginning of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = [(3, "cat"), (4, "dog"), (1, "bird"), (5, "fish")]
selection_sort(arr)
print(arr) # Output: [(1, "bird"), (3, "cat"), (4, "dog"), (5, "fish")]

def selection_sort(arr):
    # Iterate over the array
    for i in range(len(arr)):
        # Find the minimum element in the unsorted part of the array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx]["age"] > arr[j]["age"]:
                min_idx = j
        # Swap the minimum element with the element at the beginning of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = [{"name": "John", "age": 32}, {"name": "Jane", "age": 28}, {"name": "Bob", "age": 45}]
selection_sort(arr)
print(arr) # Output: [{"name": "Jane", "age": 28}, {"name": "John", "age": 32}, {"name": "Bob", "age": 45}]

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

def selection_sort(arr):
    # Iterate over the array
    for i in range(len(arr)):
        # Find the minimum element in the unsorted part of the array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx].age > arr[j].age:
                min_idx = j
        # Swap the minimum element with the element at the beginning of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = [Person("John", 32), Person("Jane", 28), Person("Bob", 45)]
selection_sort(arr)
print([p.name for p in arr]) # Output: ["Jane", "John", "Bob"]