Home  >  Article  >  Backend Development  >  How to implement selection sort using Python

How to implement selection sort using Python

王林
王林Original
2023-06-10 08:54:252460browse

Selection sort is a simple sorting algorithm. Its basic idea is to find the minimum value among unsorted elements and then put it at the end of the sorted elements. Repeat this process until all elements are sorted. In this article, we will introduce how to implement selection sort using Python.

First of all, we need to clearly select the sorting steps.

  1. First, find the smallest element in the unsorted sequence, and then store it at the beginning of the sequence.
  2. Next, continue to find the smallest element among the remaining unsorted elements, and then store it at the end of the sorted sequence.
  3. Repeat step 2 until all elements have been sorted.

Based on the above steps, we can start using Python to implement the selection sort algorithm.

Implementation steps:

  1. Define a function selection_sort() that receives a list as a parameter.
  2. In the function, use a for loop to traverse the list and obtain the length of the list len(arr).
  3. Then use another for loop to find the smallest element in the unsorted array.
  4. After finding the smallest element, exchange it with the i-th element in the current list.
  5. Repeat steps 3 and 4 until all elements are sorted.

The following is the specific code implementation:

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

In the above code, we define a function selection_sort() that accepts a list as a parameter. A for loop is used inside the function to traverse the list and obtain the length of the list. Next, use another for loop to find the smallest element in the unsorted array. Once the smallest element is found, swap it with the i-th element of the current list. Finally, repeat steps 3 and 4 until all elements are sorted.

Now, we can use the selection_sort() function to test it:

arr = [64, 25, 12, 22, 11]

print("原始数组:")
print(arr)

s_arr = selection_sort(arr)

print("排序后的数组:")
print(s_arr)

The output result is:

原始数组:
[64, 25, 12, 22, 11]
排序后的数组:
[11, 12, 22, 25, 64]

Summary

Selection sorting is a Simple but very effective sorting algorithm, its time complexity is O(n²). In the actual programming process, we can use Python to implement the selection sort algorithm.

Through the above demonstration code, we can see that Python's implementation of the sorting algorithm is very simple. If you have not come into contact with sorting algorithms in the process of learning Python, then this article may help you.

The above is the detailed content of How to implement selection sort using Python. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn