Insertion Sort
Question:
Write a program to perform insertion sort on [85, 63, 0, 12, 47, 96, 52]
Program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 = [85, 63, 0, 12, 47, 96, 52] insertionSort(alist) print(alist) |
Explanation:
Step 1 − If it is the first element, it is already sorted. return 1
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Output:
|
1 |
[0, 12, 47, 52, 63, 85, 96] |
Leave a Reply