Detailed explanation of selection sort implementation in Python

Detailed explanation of the selection sort algorithm in Python

Selection sort is a simple but inefficient sorting algorithm. Its basic idea is to start from the items to be sorted each time. Find the smallest (or largest) element in the sequence and put it at the end of the sorted sequence. By repeating this process until all elements are sorted.

The steps for selection sorting are as follows:

1. Traverse the sequence and find the smallest (or largest) element.
2. Exchange the smallest (or largest) element with the element at the current traversal position.
3. Repeat steps 1 and 2 until the entire sequence is traversed.

Let’s explain the selection sort algorithm in detail and give specific code examples.

First, we define a function to implement selection sorting:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序序列中的最小元素的索引
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 将最小元素与当前遍历位置的元素交换
        arr[i], arr[min_index] = arr[min_index], arr[i]

Now, let’s test the effect of selection sorting:

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print(arr[i])

Run the above code, the output results are as follows :

排序后的数组:
11
12
22
25
64

You can see that selection sorting successfully sorts the array in ascending order.

The time complexity of selection sorting is O(n^2), where n is the length of the sequence to be sorted. This is because each time you need to traverse all the elements in the unsorted sequence to find the smallest (or largest) element, you need to perform n comparisons. A total of n-1 rounds of traversal need to be performed, so the time complexity is O(n^2).

Selection sort is an unstable sorting algorithm, that is, the relative order of the same elements may change. This is because selection sort is implemented by continuously exchanging the positions of elements. For example, for the sequence [3, 1, 3], the possible result after sorting using the selection sort algorithm is [1, 3, 3], and the relative position of the originally identical element 3 has changed.

Although selection sorting is less efficient, its implementation is simple and intuitive. In some specific cases, such as when the sequence to be sorted is small or the stability requirements are not high, selection sorting can be used as a simple sorting method.

To summarize, selection sort is an algorithm that completes sorting by continuously finding the smallest (or largest) element in an unsorted sequence and exchanging it with the element at the current traversal position. Although the implementation is simple, the time complexity is high and unstable. In practical applications, the usage scenarios of selection sorting are relatively limited.

The above is the detailed content of Detailed explanation of selection sort implementation in Python. For more information, please follow other related articles on the PHP Chinese website!