CodeGym /Java Course /Python SELF EN /Selection Sort

Selection Sort

Python SELF EN

Level 58 , Lesson 2

Available

7.1 Definition of Selection Sort

Selection Sort is a sorting algorithm that finds the smallest element from the unsorted part of an array and swaps it with the first element of this part. The process repeats for the remaining elements until the whole array is sorted.

How it works:

Start with the first element of the array.
Find the smallest element in the remaining unsorted part of the array.
Swap the smallest element with the first element of the unsorted part.
Repeat the process for the next element until the whole array is sorted.

Step-by-step process:

Find the smallest element in the array and swap it with the first element.
Repeat the process for the remaining array (starting from the second element).
Continue the process until the whole array is sorted.

Time and space complexity of selection sort

Time complexity:

Worst case: O(n^2) — happens when elements are initially ordered in reverse or randomly.
Average case: O(n^2) — occurs with random arrangement of elements.
Best case: O(n^2) — even if the array is already sorted, the algorithm still performs the same comparisons.

Space complexity:

O(1) — because the algorithm uses a constant amount of additional memory (just a few variables to hold temporary values).

7.2 Implementation of Selection Sort Algorithm

The implementation of the algorithm is very simple:

Step 1: find the minimum element among all elements and swap it with the first.

Step 2: find the minimum element among all elements except the first and swap it with the second.

Step 3: find the minimum element among all elements except the first and second and swap it with the third.

Python implementation:


def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the minimum element in the remaining unsorted part of the array
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Return the sorted array

# Example usage:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)
# Output: Sorted array: [11, 12, 22, 25, 64]

Example of the algorithm working:

First pass (i = 0):
1. Find the minimum element (11) in the unsorted part of the array [64, 25, 12, 22, 11].
2. Swap 11 with 64.
3. Array: [11, 25, 12, 22, 64]
Second pass (i = 1):
1. Find the minimum element (12) in the unsorted part of the array [25, 12, 22, 64].
2. Swap 12 with 25.
3. Array: [11, 12, 25, 22, 64]
Third pass (i = 2):
1. Find the minimum element (22) in the unsorted part of the array [25, 22, 64].
2. Swap 22 with 25.
3. Array: [11, 12, 22, 25, 64]
Fourth pass (i = 3):
1. Find the minimum element (25) in the unsorted part of the array [25, 64].
2. 25 is already in place, no swap needed.
3. Array: [11, 12, 22, 25, 64]