  # Explain Insertion Sorting with example in Data Structures and Algorithm?

235 views
Explain Insertion Sorting with example in Data Structures and Algorithm? posted Feb 10, 2015

### 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 Feb 13, 2015

### 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 Feb 12, 2015
+1 vote

Algorithm

Lets take an example suppose we have an array of size 8 bytes , Eg A={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. answer Feb 11, 2015
Similar Questions