Selection sort algorithm:

Sorting algorithms are essential in computer science and programming, and they help us to organize data in a specific order. One of the most straightforward sorting algorithms is Selection sort, and it is an excellent starting point for beginners who want to learn sorting algorithms. In this blog post, we will discuss Selection sort in Python with examples, applications, pros and cons, and time and space complexity.

What is Selection Sort?

Selection sort is a simple, in-place, and comparison-based sorting algorithm. It works by dividing the input list into two parts: sorted and unsorted. Initially, the sorted part is empty, and the unsorted part contains all the elements. Selection sort then repeatedly selects the smallest element from the unsorted part and moves it to the end of the sorted part. This process continues until the entire list is sorted.

The selection sort algorithm consists of two loops. The outer loop selects an element from the unsorted part and moves it to the end of the sorted part. The inner loop finds the smallest element in the unsorted part.

Here’s how the algorithm works:

1. Find the minimum element in the unsorted list.
2. Swap the minimum element with the first element in the unsorted list.
3. Move the boundary between the sorted and unsorted parts one element to the right.
4. Repeat steps 1–3 until the entire list is sorted.

Example of Selection Sort in Python

Let’s take an example of an unsorted list [64, 25, 12, 22, 11]. We will apply the Selection sort algorithm to sort this list.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)

The output of this code will be:

[11, 12, 22, 25, 64]

Applications of Selection Sort

Although Selection sort is not the most efficient sorting algorithm, it has some practical applications. For example:

• Selection sort is useful when memory is limited because it sorts the list in place, without needing extra memory.
• It is used in small-scale systems where the number of elements to be sorted is small.
• Selection sort is often used as a building block for other sorting algorithms such as Quick sort.

Pros and Cons of Selection Sort

Pros:

• Simple and easy to understand.
• In-place sorting algorithm, which means it requires only a constant amount of additional memory to perform the sort.
• Performs well on small lists.

Cons:

• Not suitable for large datasets as its time complexity is O(n²).
• Inefficient, as it always performs the same number of comparisons even if the list is already sorted.
• Selection sort is not stable; it can change the relative order of equal elements.

Time and Space Complexity of Selection Sort

The time complexity of Selection sort is O(n²) in the worst-case scenario, where n is the number of elements to be sorted. This is because the algorithm needs to perform n-1 comparisons in the first loop and n-2 comparisons in the second loop. In the best-case scenario, the time complexity is O(n²) because it performs the same number of comparisons, even if the list is already sorted.

The space complexity of Selection sort is O(1) because it sorts the list in place, without needing extra memory.