Original link: http://www.nosuchfield.com/2022/05/27/Principles-and-implementation-of-common-sorting-algorithms/
Bubble Sort
The principle of bubble sort is very simple, that is to move the largest (or smallest) element in the current unordered sequence to the beginning (or end) of the sequence every time, and then do the same operation to the remaining sequences except the element. . When all elements have been bubbled, the entire sequence becomes ordered. The process of bubble sort, as its name suggests, moves the largest element in the sequence to the end each time (assuming we choose this rule), which is like a bubble in water constantly floating from water to surface. .
The implementation of bubble sort is as follows, and a simple observation shows that its time complexity is O(n 2 )
1
2
3
4
5
6
|
def bubble_sort (arr) :
length = len(arr)
for i in range(length - 1 ):
for j in range(length - 1 - i):
if arr[j] > arr[j + 1 ]:
arr[j], arr[j + 1 ] = arr[j + 1 ], arr[j]
|
selection sort
Similar in principle to bubble sort, the difference is that bubble sort compares the size of adjacent elements, while selection sort compares the size with a fixed value, eliminating some unnecessary comparison processes. The same is to get the minimum value of an unordered sequence and put it at the beginning. Bubble sort compares and exchanges values one by one, while selection sort uses the first element as the reference value for comparison. After getting the minimum value, you only need to put the minimum value. Swap with the beginning element.
The selection sort is implemented as follows, and the complexity is O(n 2 )
1
2
3
4
5
6
7
8
|
def select_sort (arr) :
length = len(arr)
for i in range(length):
min_num_index = i
for j in range(i, length):
if arr[j] < arr[min_num_index]:
min_num_index = j
arr[min_num_index], arr[i] = arr[i], arr[min_num_index]
|
Insertion sort
Insertion sort divides the sequence into two parts, one is ordered and the other is unordered. Each time an element is selected from the unordered sequence and inserted into the correct position in the sorted sequence, it is guaranteed that the sorted sequence is still in order, just as the cards are constantly drawn and inserted into the correct position when playing cards. Here we treat the first half of the sequence as an ordered sequence, and the second half as an unordered sequence.
Insertion sort is implemented as follows, and the complexity is O(n 2 )
1
2
3
4
5
6
7
8
9
|
def insert_sort (arr) :
length = len(arr)
for i in range( 1 , length):
value = arr[i]
j = i - 1
while j >= 0 and value < arr[j]: # Move the element forward
arr[j + 1 ] = arr[j] # Shift all one bit backward
j -= 1
arr[j + 1 ] = value
|
merge sort
Merge sort is to merge two ordered sequences into one sequence, and the ordered sequence before merging can be obtained by merging the two ordered sequences, and so on, the sorting is finally realized.
Merge sort is implemented as follows, the complexity is O(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
twenty three
twenty four
25
26
27
28
29
30
31
32
33
34
35
|
def merge_sort (arr) :
def _merge_sort (_arr, left, right) :
if left >= right:
return
# Calculate the middle position
mid = (left + right) // 2
# Get the ordered sequence of the left half
_merge_sort(_arr, left, mid)
# Get the ordered sequence of the right half
_merge_sort(_arr, mid + 1 , right)
tmp = []
i = left
j = mid + 1
while i <= mid or j <= right: # traverse
if i > mid: # i has reached the end, only j
tmp.append(_arr[j])
j += 1
continue
if j > right: # j has reached the end, only i is saved
tmp.append(_arr[i])
i += 1
continue
# take the smaller value
if _arr[i] < _arr[j]:
tmp.append(_arr[i])
i += 1
else :
tmp.append(_arr[j])
j += 1
_arr[left: right + 1 ] = tmp # make this sequence ordered
_merge_sort(arr, 0 , len(arr) - 1 )
|
quick sort
Similar to quicksort and mergesort, they both use divide and conquer. The difference is that merge sort first creates two ordered subsequences, while quick sort randomly selects a pivot, and then places the value greater than the element on the right, and the value less than the element on the left. Repeating this, the final sequence becomes ordered.
Quicksort is implemented as follows, with a complexity of O(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def quick_sort (arr) :
def _quick_sort (_arr, left, right) :
if left >= right:
return
pivot = random.randint(left, right) # random a pivot
_arr[pivot], _arr[right] = _arr[right], _arr[pivot] # put this value on the far right
j = left
for i in range(left, right):
if _arr[i] < _arr[right]: # If the current value is less than the value corresponding to pivot
_arr[i], _arr[j] = _arr[j], _arr[i] # put this value to the left
j += 1
_arr[j], _arr[right] = _arr[right], _arr[j] # Finally put this value in the middle of the small value and the large value
# Divide and conquer the values on the left and right sides
_quick_sort(_arr, left, j - 1 )
_quick_sort(_arr, j + 1 , right)
_quick_sort(arr, 0 , len(arr) - 1 )
|
The complete code with all sorting algorithms and tests is as follows
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
twenty three
twenty four
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
import copy
import random
import time
def time_keep (func) :
def wrapper (*args, **kw) :
start = time.time()
result = func(*args, **kw)
end = time.time()
print( '{:>12}: {}' .format(func.__name__, (end - start) * 1000 ))
return result
return wrapper
def get_array (start= 0 , end= 5000 , length= 1000 ) :
if start >= end or length <= 0 :
return []
random_list = []
for i in range(length):
random_list.append(random.randint(start, end))
return random_list
@time_keep
def bubble_sort (arr) :
length = len(arr)
for i in range(length - 1 ):
for j in range(length - 1 - i):
if arr[j] > arr[j + 1 ]:
arr[j], arr[j + 1 ] = arr[j + 1 ], arr[j]
@time_keep
def select_sort (arr) :
length = len(arr)
for i in range(length):
min_num_index = i
for j in range(i, length):
if arr[j] < arr[min_num_index]:
min_num_index = j
arr[min_num_index], arr[i] = arr[i], arr[min_num_index]
@time_keep
def insert_sort (arr) :
length = len(arr)
for i in range( 1 , length):
value = arr[i]
j = i - 1
while j >= 0 and value < arr[j]: # Move the element forward
arr[j + 1 ] = arr[j] # Shift all one bit backward
j -= 1
arr[j + 1 ] = value
@time_keep
def merge_sort (arr) :
def _merge_sort (_arr, left, right) :
if left >= right:
return
# Calculate the middle position
mid = (left + right) // 2
# Get the ordered sequence of the left half
_merge_sort(_arr, left, mid)
# Get the ordered sequence of the right half
_merge_sort(_arr, mid + 1 , right)
tmp = []
i = left
j = mid + 1
while i <= mid or j <= right: # traverse
if i > mid: # i has reached the end, only j
tmp.append(_arr[j])
j += 1
continue
if j > right: # j has reached the end, only i is saved
tmp.append(_arr[i])
i += 1
continue
# take the smaller value
if _arr[i] < _arr[j]:
tmp.append(_arr[i])
i += 1
else :
tmp.append(_arr[j])
j += 1
_arr[left: right + 1 ] = tmp # make this sequence ordered
_merge_sort(arr, 0 , len(arr) - 1 )
@time_keep
def quick_sort (arr) :
def _quick_sort (_arr, left, right) :
if left >= right:
return
pivot = random.randint(left, right) # random a pivot
_arr[pivot], _arr[right] = _arr[right], _arr[pivot] # put this value on the far right
j = left
for i in range(left, right):
if _arr[i] < _arr[right]: # If the current value is less than the value corresponding to pivot
_arr[i], _arr[j] = _arr[j], _arr[i] # put this value to the left
j += 1
_arr[j], _arr[right] = _arr[right], _arr[j] # Finally put this value in the middle of the small value and the large value
# Divide and conquer the values on the left and right sides
_quick_sort(_arr, left, j - 1 )
_quick_sort(_arr, j + 1 , right)
_quick_sort(arr, 0 , len(arr) - 1 )
if __name__ == '__main__' :
random_array = get_array()
array1 = copy.deepcopy(random_array)
bubble_sort(array1)
print(array1)
array2 = copy.deepcopy(random_array)
select_sort(array2)
print(array2)
array3 = copy.deepcopy(random_array)
insert_sort(array3)
print(array3)
array4 = copy.deepcopy(random_array)
merge_sort(array4)
print(array4)
array5 = copy.deepcopy(random_array)
quick_sort(array5)
print(array5)
|
refer to
Top 10 Common Sorting Algorithms
Common basic sorting algorithms
This article is reprinted from: http://www.nosuchfield.com/2022/05/27/Principles-and-implementation-of-common-sorting-algorithms/
This site is for inclusion only, and the copyright belongs to the original author.