python coding test course, selection sort

Improving algorithmic problem-solving skills is very important in the programming journey. Especially, understanding basic algorithms is necessary for job interviews or coding tests. In this article, we will explore the Selection Sort algorithm and detail the process of solving a problem using it.

What is Selection Sort?

Selection Sort is a simple sorting algorithm that finds the smallest (or largest) value from a given list and places it at the front, then repeats the process for the next position. Selection Sort proceeds as follows:

  1. Find the smallest element in the list.
  2. Swap that element with the first element of the list.
  3. Repeat the above process for the remaining elements excluding the first one.

The time complexity of Selection Sort is O(n²), where n is the length of the list. This algorithm works well for small lists but may degrade in performance with larger datasets.

Problem Description

Let’s solve the following problem:

Problem: Given a list composed of integers, sort this list in ascending order using the Selection Sort algorithm.

Input:

  • Integer n (1 ≤ n ≤ 1000): Length of the list
  • List: n integers separated by spaces

Output:

  • Print the list sorted in ascending order.

Problem Solving Process

Step 1: Input and Initialization

We need to receive the input required to solve the problem. In Python, we can use the input() function to obtain input. Then, we convert the received values into a list format.

n = int(input("Enter the length of the list: "))
arr = list(map(int, input("Enter the integer list: ").split()))

Step 2: Implementing Selection Sort

To implement the Selection Sort algorithm, we use two loops. The first loop indicates the start of the unsorted portion, while the second loop finds the smallest element within that range.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Initialize the index of the smallest element at the current position
        min_index = i
        # Find the minimum value among the elements after the current position
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the found minimum value with the current position
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

Step 3: Output the Result

We print the sorted list. This can be easily implemented using the print() function.

sorted_arr = selection_sort(arr)
print("The list sorted in ascending order is as follows:")
print(sorted_arr)

Full Code

def selection_sort(arr):
    n = len(arr)
    # Iterate through each element of the list
    for i in range(n):
        # Initialize the index of the smallest element at the current position
        min_index = i
        # Find the minimum value among the elements after the current position
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the found minimum value with the current position
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Take the length of the list as input and the list elements
n = int(input("Enter the length of the list: "))
arr = list(map(int, input("Enter the integer list: ").split()))

# Perform Selection Sort
sorted_arr = selection_sort(arr)

# Output the result
print("The list sorted in ascending order is as follows:")
print(sorted_arr)

Complexity Analysis

The time complexity of Selection Sort is O(n²). Therefore, using Selection Sort on large datasets can be inefficient. However, Selection Sort is simple to implement and can be useful for initial educational purposes.

Conclusion

In this article, we closely examined the process of solving a problem based on the Selection Sort algorithm. I hope this helped enhance your basic understanding of algorithms by understanding and implementing Selection Sort. We look forward to covering more beneficial algorithm topics in the next article!

Related References