← Back to Data Structures and Algorithms in Python

1. Introduction

The Selection Sort algorithm is a simple comparison-based sorting technique. The main idea behind this algorithm is to divide the input list into two parts: a sorted and an unsorted region. With each iteration, the algorithm finds the smallest (or largest, depending on the order) element from the unsorted region and swaps it with the leftmost unsorted element, thus extending the sorted region by one.

2. Implementation Steps

1. Start at the beginning of the list and search for the smallest element.

2. Swap the smallest element found with the first element of the list.

3. Move to the next element and repeat the process until the entire list is sorted.

3. Implementation in Python

def selection_sort(arr):
    # Traverse through all elements in the list
    for i in range(len(arr)):
        # Find the minimum element's index in the remaining unsorted array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap the found minimum element with the first element of the current position
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
# Test the selection_sort function
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Explanation:

1. We define the selection_sort function that takes a list arr as its argument.

2. Inside the function, we traverse through the list using a for loop.

3. For each iteration, we assume the current element as the smallest by setting min_idx to the current index i.

4. We then iterate over the remaining unsorted part of the list. If we find an element smaller than the element at min_idx, we update min_idx.

5. Once the inner loop completes, we have the index of the smallest element in the unsorted part of the list. We then swap this smallest element with the element at the current index i.

6. The process is repeated until the entire list is sorted.

Note: While Selection Sort is straightforward and easy to understand, it is inefficient for large lists due to its O(n^2) time complexity.