foreword
This article describes the implementation of selection sort, bubble sort, insertion sort and example applications in python. There will be new sorting algorithm implementations and example applications in the future.
One, selection sort
The so-called selection sort is to repeatedly extract the largest or smallest element from the unsorted sequence and insert it into a new sequence, and finally form an ordered sequence. There are two types of selection sorts: ascending sort and descending sort.
- Ascending sort: Each time the smallest value in the unsorted sequence is selected, it is swapped with the first value of the unsorted sequence.
- Descending sort: Each time the largest unsorted sequence is selected, it is swapped with the first value of the unsorted sequence.
(1) Code to see the sorting process
data = [56,18,49,84,72]
def choose_high(data):
for i in range(len(data)-1):#iterate over the list
for j in range(i+1,len(data)):#Each scan from the back of the last row
if data[i] > data[j]:#In ascending sort, the small one is placed first; in descending sort, just replace greater than with less than
data[i],data[j] = data[j],data[i]
print("the first",i+1,"secondary sorting results:",end="")
for i in data:
print("%3d"%i,end="")
print("")
print("Ascending sort:")
print("The sequence before sorting is:",end="")
for i in data:
print("%3d"%i,end="")
print("\n================================")
print("The sorting process is as follows:")
choose_high(data)
print("================================")
print("The sorted sequence is:",end="")
for i in data:
print("%3d"%i,end="")
operation result: Ascending sort: The sequence before sorting is: 56 18 49 84 72 ================================ The sorting process is as follows: 1st sort result: 18 56 49 84 72 Result of the 2nd sort: 18 49 56 84 72 Results of the 3rd sort: 18 49 56 84 72 4th sort result: 18 49 56 72 84 ================================ The sequence after sorting is: 18 49 56 72 84 Process finished with exit code 0
(2) Example application of the code
# Sort the following grades from largest to smallest
dic = {"haha":90,"xixi":100,"koko":80,"niki":75,"baby":88}
# Define a function to sort by grades from big to small
def key(x):
return x[1]
def choose_low(data:list,key):
for i in range(len(data)-1):
for j in range(i+1,len(data)):
if (key(data[i])<key(data[j])):
data[i],data[j] = data[j],data[i]
return data
dic_item = list(dic.items())#must be converted to a list
print("Before sorting:")
for i in range(len(dic_item)):
print(dic_item[i])
print("After sorting:")
after_sort = choose_low(dic_item,key)
for index,info in enumerate(after_sort):
print("the first",index+1,"name",info)operation result:
Before sorting:
('haha', 90)
('xixi', 100)
('koko', 80)
('niki', 75)
('baby', 88)
After sorting:
1st place ('xixi', 100)
Article 2 ('haha', 90)
3rd Place ('baby', 88)
4th ('koko', 80)
5th ('niki', 75)
Process finished with exit code 0
2. Bubble sort
The idea of bubble sort is to start from the first number, compare the size of two adjacent numbers at a time, and arrange them from small to large or from large to small.
(1) Code to see the sorting process
data = [56,20,84,66,13]
def bubles(data):
i = len(data)-1 #Control the number of times to be sorted, the number of sorting is the number of sorting minus one
while (i>0):
for j in range(i):
if data[j]>data[j+1]:
data[j],data[j+1] = data[j+1],data[j]
print("the first%d The sorting process is:"%(len(data)-i), end="")
i -= 1
for k in data:
print("%3d"%k,end="")
print("")
print("Before bubble sort:",end="")
for i in data:
print("%3d"%i,end="")
print("\n==========================")
print("Start bubble sort...")
bubles(data)
print("============================")
print("After bubble sort:",end="")
for i in data:
print("%3d"%i,end="")operation result: Before bubble sort: 56 20 84 66 13 ========================== Start bubble sort... The first sorting process is: 20 56 66 13 84 The second sorting process is: 20 56 13 66 84 The 3rd sort process is: 20 13 56 66 84 The 4th sort process is: 13 20 56 66 84 ============================ After bubble sort: 13 20 56 66 84 Process finished with exit code 0
(2) Example application of code
data = {"Wang Yibo":98,"Zhang Binbin":100,"Wu Lei":97,"Yang Yang":99}
def key(x):
return x[1]
def bubles(data:list,key):
i = len(data)-1 #Control the number of times to be sorted, the number of sorting is the number of sorting minus one
while (i>0):
for j in range(i):
if key(data[j])<key(data[j+1]):
data[j],data[j+1] = data[j+1],data[j]
print("the first%d The sorting process is:"%(len(data)-i), end="")
i -= 1
for k in data:
print(k,end="")
print("")
data2 = list(data.items())
print("Before bubble sort:",end="")
for i in data2:
print(i,end="")
print("\n==============================================================")
print("Start bubble sort...")
bubles(data2,key)
print("==============================================================")
print("After bubble sort:")
for index,info in enumerate(data2):
print("the first",index+1,"name:",info)operation result:
Before bubble sort:('Wang Yibo', 98)('Zhang Binbin', 100)('Wu Lei', 97)('Yang Yang', 99)
==============================================================
Start bubble sort...
The first sorting process is:('Zhang Binbin', 100)('Wang Yibo', 98)('Yang Yang', 99)('Wu Lei', 97)
The second sorting process is:('Zhang Binbin', 100)('Yang Yang', 99)('Wang Yibo', 98)('Wu Lei', 97)
The third sorting process is:('Zhang Binbin', 100)('Yang Yang', 99)('Wang Yibo', 98)('Wu Lei', 97)
==============================================================
After bubble sort:
1st place: ('Zhang Binbin', 100)
Article 2: ('Yang Yang', 99)
3rd Place: ('Wang Yibo', 98)
4th: ('Wu Lei', 97)
Process finished with exit code 0
3. Insertion sort
The algorithm idea of insertion sort is to compare the elements in the sequence with the sorted elements one by one, and then find the appropriate position to insert.
(1) Code to see the sorting process
data = [58,29,86,69,10]
def insert(data):#Insertion sort from smallest to largest
for i in range(len(data)):
temp = data[i]
j = i-1#last sorted
while(j>=0 and temp<data[j]):#If the one to be inserted is smaller than the last one in the sorted order
data[j+1]=data[j]#Shift the original element back by one
j = j-1
data[j+1] = temp
print("the first", i + 1, "secondary sorting results:", end="")
for k in data:
print("%3d"%k,end="")
print("")
print("Insertion sort:")
print("The sequence before sorting is:",end="")
for i in data:
print("%3d"%i,end="")
print("\n================================")
print("The sorting process is as follows:")
insert(data)
print("================================")
print("The sorted sequence is:",end="")
for i in data:
print("%3d"%i,end="")operation result: Insertion sort: The sequence before sorting is: 58 29 86 69 10 ================================ The sorting process is as follows: 1st sort result: 58 29 86 69 10 Result of the 2nd sort: 29 58 86 69 10 Results of the 3rd sort: 29 58 86 69 10 4th sort result: 29 58 69 86 10 5th sort result: 10 29 58 69 86 ================================ The sequence after sorting is: 10 29 58 69 86 Process finished with exit code 0
(2) Example application of code
# The beauty scores of the beautiful female stars in my mind are as follows:
data = {"Dilireba":99,"Zhao Liying":97,"Tang Shiyi":100,"white deer":96}
def key(x):
return x[1]
def insert(data:list,key):#Sort from largest to smallest
for i in range(len(data)):
temp = data[i]
j = i - 1#Last sorted last
while (j>=0 and key(temp)>key(data[j])):#If the insert to be inserted is larger than the last time
data[j+1] = data[j]
j = j - 1
data[j+1] = temp
print("the first",i+1,"Secondary sorting results:",end="")
print(data)
data2 = list(data.items())
print("Before insertion sort:",end="")
for i in data2:
print(i,end="")
print("\n===========================================================================")
print("Start Insertion Sort...")
insert(data2,key)
print("===========================================================================")
print("After insertion sort:")
for index,info in enumerate(data2):
print("the first",index+1,"name:",info)operation result:
Before insertion sort:('Dilireba', 99)('Zhao Liying', 97)('Tang Shiyi', 100)('white deer', 96)
===========================================================================
Start Insertion Sort...
1st sort result:[('Dilireba', 99), ('Zhao Liying', 97), ('Tang Shiyi', 100), ('white deer', 96)]
2nd sorting result:[('Dilireba', 99), ('Zhao Liying', 97), ('Tang Shiyi', 100), ('white deer', 96)]
3rd sort result:[('Tang Shiyi', 100), ('Dilireba', 99), ('Zhao Liying', 97), ('white deer', 96)]
4th sort result:[('Tang Shiyi', 100), ('Dilireba', 99), ('Zhao Liying', 97), ('white deer', 96)]
===========================================================================
After insertion sort:
1st place: ('Tang Shiyi', 100)
Article 2: ('Dilireba', 99)
3rd Place: ('Zhao Liying', 97)
4th: ('white deer', 96)
Process finished with exit code 0
Summarize
Whether it is selection sort, bubble sort or insertion sort, the time complexity of these three sorts is
Selection sort is to select the largest or smallest element in the unsorted sequence each time, and put it first in the unsorted sequence.
Bubble sort requires an outer loop to control the number of sorting, and an inner loop to compare two adjacent data, and to sort from large to small or from small to large. The number of times of sorting is the number of elements to be sorted minus one.
Insertion sort is the default first sorting to determine the position of the first element, and then traverse the unsorted sequence, each time inserting the sorted sequence into the appropriate position. The algorithm sets a pointer to the last sorted element, and then compares the element to be sorted with it and inserts it into the appropriate position.