First one: Insertion Sort
def insertion_sort(sort_list):
iter_len = len(sort_list)
if iter_len < 2:
return sort_list
for i in range(1, iter_len):
key = sort_list[i]
j = i - 1
while j>=0 and sort_list[j]>key:
sort_list[j+1] = sort_list[j]
j -= 1
sort_list[j+1] = key
return sort_list
Insertion sort has two nested loops:
Outer loop runs once for each element in the original unsorted loop
Inner loop runs through sorted list to find the right insertion point
And thus the efficiency is O(n^2)
Second one: Selection Sort
def selection_sort(sort_list):
iter_len = len(sort_list)
if iter_len < 2:
return sort_list
for i in range(iter_len-1):
smallest = sort_list[i]
location = i
for j in range(i, iter_len):
if sort_list[j] < smallest:
smallest = sort_list[j]
location = j
if i != location:
sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
return sort_list
The basic idea of selection sort is:
For each element i in the list:
1) „Find the smallest element j in the rest of the list
2) Swap i and j
And thus the efficiency is O(n^2/2)=O(n^2)
Third one: Bubble Sort
def bubble_sort(sort_list):
iter_len = len(sort_list)
if iter_len < 2:
return sort_list
for i in range(iter_len-1):
for j in range(iter_len-i-1):
if sort_list[j] > sort_list[j+1]:
sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j]
return sort_list
The basic idea of bubble sort is:
Run through the array, exchanging values that are out of order
Outer loop can execute a maximum of n-1 times
Inner loop can execute a maximum of n-1 times
And thus the efficiency is O((n-1)^2) = O(n^2)
For now we can see that the three sorting algorithms introduced above all have the same efficiency O(n^2)
So do we have any more efficient algorithm?
And the answer is Yes!
Fourth one: Merge Sort
def merge_sort(sort_list):
def merge2(L1:list, L2:list) -> list:
L = []
L1.reverse()
L2.reverse()
while L1 and L2:
if L1[-1] < L2[-1]:
L.append(L1.pop())
else:
L.append(L2.pop())
L1.reverse()
L2.reverse()
return L + L1 + L2
if len(sort_list) < 2 :
return sort_list
else :
left_sublist = sort_list[:len(sort_list)//2]
right_sublist = sort_list[len(sort_list)//2:]
return merge(merge_sort(left_sublist), merge_sort(right_sublist))
The basic idea of Merge Sort is:
1）Break the data into two equal halves
2）Sort the halves
3）Merge the two sorted lists
And here we sort the halves by recursion
It's easy to find out that the efficiency of step Merge is O(n)
And it's also not difficult to conclude that the number we splits the list is O(logn)
And thus the efficiency of Merge Sort is O(nlogn) < O(n^2)
