Sort#
This block is to implemnt different kinds of sort algorithms.
Insertion Sort#
Insertion sort is a sorting algorithm that inserts a new vaue to a sorted array at the right place so that the resulting array is also sorted. This sorting is very similar to playing poker when we need reorder the cards.
The pesudo code is shown as follows.
Some Questionable Implementation#
# Wrong implementation 1:
def sort(array):
def insert_sort(A, i):
""" given a array whose prefix A[:i] is sorted, rearrange value A[i] to make the whole array sorted"""
if i == 0:
return A
# swap if A[i] is less than A[i-1]
j = i
while j > 0:
if A[j] < A[j-1]:
A[j], A[j-1] = A[j-1], A[j]
j -= 1
# advance
insert_sort(A, i - 1)
return A
return insert_sort(array, len(array) - 1)
# test
A = [3,4,1,1,7,2]
print(sort(A))
[1, 1, 3, 4, 2, 7]
The above implemention is wrong as L17 should come before L10.
Recursive Implementation#
def sort(A):
def insert_sort(A, i):
""" given a array whose prefix A[:i] is sorted, rearrange value A[i] to make the whole array sorted"""
# base case
if i <= 0:
return A
# divide and conquer: sort A[:i-1]
insert_sort(A, i-1)
# combine solutions
j = i
while j:
if A[j] < A[j-1]:
A[j-1], A[j] = A[j], A[j-1]
j -= 1
return A
return insert_sort(A, len(A)-1)
# test
A = [3,4,1,1,7,2]
print(sort(A))
[1, 1, 2, 3, 4, 7]
Iterative Implementation#
def sort(A):
pass
Selection Sort#
Recursive Implementation#
def sort(A):
def selection_sort(A, i):
"""Select the maximum from A[:i] and swap with A[i]"""
if i < 1:
return A
# move the maximum to right
if A[i] < A[i-1]:
A[i], A[i-1] = A[i-1], A[i]
# divide and conquer
selection_sort(A, i-1)
return A
return selection_sort(A, len(A)-1)
# test
A = [3,4,1,1,7,2]
print(sort(A))
[1, 3, 4, 1, 2, 7]