Explain Insertion Sorting with example in Data Structures and Algorithm?

Answer 1

Insertation Sorting:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Code:

def insertionSort(alist):
   for index in range(1,len(alist)):

     currentvalue = alist[index]
     position = index

     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1

     alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

Example:

Answer 2

Algorithm

for i = 2 to n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--) 
        swap a[k,k-1]
    invariant: a[1..i] is sorted
end

Properties

Time Complexity: O(n^2)
Space Complexity: O(1) extra space
Best Case: O(n) time when nearly sorted

Answer 3

Algorithm

Lets take an example suppose we have an array of size 8 bytes , Eg A[8]={12,3,1,5,8}
step 1: compare the first element of the array with the immediate next to it. Here compare 12 with 3, since 12 is greater than 3, we swap 12 with 3, then it becomes 3,12,1,5,8

Step 2: Then compare 1 with 12 since 12 is greater than swap it, and check whether 3 is greater than 1 since it is so the array becomes 1,3,12,5,8

Step 3: Repeat step 2 unitill we reach the last element of the array.