Please answer using python, thanks! Implement the swap-based insertion sort algo
ID: 3834178 • Letter: P
Question
Please answer using python, thanks!
Implement the swap-based insertion sort algorithm. This algorithm has a nice benefit - it can be done "in place" without requiring a result list to be created because it modifies the given unsorted list. The insertion sort algorithm is described as follows: We begin by assuming that a list with one item (position 00) is already sorted. We use a loop iteration variable (index) to keep track of the position in our list for which elements to the left are sorted and elements to the right are unsorted. On each loop iteration (one for each index 1 through n -1 n - 1), the current item at index is checked against those in the already sorted sublist. To do this we have a nested loop that iterates backwards from index to position 0 and shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted. You must write the function insertion_sort which consumes an unsorted list as a parameter. Your function must modify the given list AND keep track of and return how many comparisons of values are done throughout the insertion sort algorithm. Here is the pseudo-code from https://en.wikipedia.org/wiki/lnsertion_sort: for i leftarrow 1 to length (A)-1 j leftarrow i while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j leftarrow j - 1 end while end for See the wiki page for more details on the algorithm and diagrams that show the steps of the above described algorithm.Explanation / Answer
#Python 3.6
from __future__ import print_function
def insertion_sort(value_list):
length = len(value_list)
comp = 0
for i in range(1,length):
j = i
while j > 0 :
comp += 1
if(value_list[j-1] > value_list[j]):
temp = value_list[j-1]
value_list[j-1] = value_list[j]
value_list[j] = temp
j -= 1
else:
break
return comp
def main():
alon = [32, 19, 12]
#alon = [1, 52, 32, 19, 12]
#alon = [32, 1, 53]
print(insertion_sort(alon))
print(alon)
if __name__ == '__main__':
main()