Interview essential algorithm | graphic selection sorting (Python)

Selection sort

The idea of sorting

​ The idea of selecting sorting is more intuitive : First, find the minimum in the unsorted sequence ( Big ) Elements , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements ( Big ) Elements , And then at the end of the sorted sequence . And so on , Until all elements are sorted .

Graphic selection sort

 Insert picture description here

Select the nature of the sort

  • Optimal time complexity : O ( n 2 ) O(n^2) O(n2)
  • Worst time complexity : O ( n 2 ) O(n^2) O(n2)
  • stability : unstable ( Consider the case in which ascending order selects the maximum each time )

​ Explain the case of considering ascending order : Use the same two data in the following table as (1)(2) Distinguish , If we choose the largest data to put at the end ( Traversing from front to back ):

Raw data 45(2) 23 77 45(1) 56
for the first time 45(2) 23 45(1) 56 77
The second time 45(2) 23 45(1) 56 77
third time 23 45(1) 45(2) 56 77
result 23 45(1) 45(2) 56 77

​ As can be seen from the above process (2) After sorting and (1) There was an exchange , So we say the algorithm is unstable .

Choose the code implementation of sorting

lst = list(map(int, input().split(',')))
def select_sort(alist):
n = len(alist)
for j in range(n - 1):
min_index = j
for i in range(j + 1, n):
if alist[min_index] > alist[i]:
min_index = i
alist[j], alist[min_index] = alist[min_index], alist[j]
return alist
select_sort(lst)
Please bring the original link to reprint ,thank
Similar articles

2021-06-05

2021-06-05

2021-06-06

2021-06-09

2021-06-09

2021-06-09

2021-06-10

2021-06-11

2021-06-13

2021-06-13

2021-06-15

2021-06-16