I'd like to write a insertion sort algorithm. I've almost finished it, but the function itself seems to not even bothering about last number. What could be wrong here?
def insertion_sort(user_list):
sorted_list = []
sorted_list.append(user_list[0])
for index in range(0, len(user_list)):
if user_list[index] < user_list[-1]:
for reversed_index in range(index, 0, -1):
if user_list[reversed_index] < user_list[reversed_index-1]:
user_list[reversed_index], user_list[reversed_index-1] = user_list[reversed_index-1], user_list[reversed_index]
print(user_list)
print("\n\n", user_list)
if __name__ == '__main__':
user_list = [4, 3, 2, 10, 12, 1, 5, 6]
insertion_sort(user_list)
CodePudding user response:
replace if user_list[index] < user_list[-1]
with if user_list[index] < user_list[index-1]
.
While doing insertion sort, we compare two consecutive elements to check if they are out of order. Comparing with the last element of user_list seems like a typo.