Question

wap to perform insertion sort in list​

Answer 1

Answer:

Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Algorithm

To sort an array of size n in ascending order:

1: Iterate from arr[1] to arr[n] over the array.

2: Compare the current element (key) to its predecessor.

3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Answer 2

Answer:

def insertionSort(arr):

   for i in range(1,len(arr)):

       current = arr[i]

       j = i - 1

       while(j >= 0 and arr[j] > current):

           arr[j+1] = arr[j]

           j = j - 1

       arr[j+1] = current

arr = [9,8,4,5,2,7,1,3,0,2]

print("list before sorting:",arr)

insertionSort(arr)

print("list after sorting:",arr)

Explanation: