Learning and applying algorithm in Python must be fun! In this example, we will try read Algorithm pseudo-code and applied into Python code. We will start with “Insertion Sort”. What is this algorithm? Basically in each repetition, it will remove the element and put it into correct position in “sorted list”.
Here is visual example by Wikipedia:
Now, we get the pseudo-code for this algorithm is :
1 2 3 4 5 6 7 8 | Insertion-Sort(A) for j <- 2 to length[A] do key <- A[j] i <- j – 1 while i > 0 and A[i] > key do A[i+1] <- A[i] i <- i – 1 A[i + 1] <- key |
Here is step by step explanation:
0. There will be a function called “Insertion-Sort(A)” and A in arguments is an array
1. Iterate array A with variable “j” as iterator varible that started with second index (2)
2. Assign variable “key” with the second element value in array A
3. Assign value of J – 1 to variable i
4. Do while condition if variable i more than zero and i’th element value more than key.
This mean will compare key (current element) with A[i] which previous element.
5. If condition fulfilled, which previous variable value more then current variable value, assign A[i+1] with A[i]
6. Decrease i value by assign i – 1 into i variable
7. After while condition stop, assign A[i+1]] with key
So, here is the Python code implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def insertion_sort(A): for j in range(1, len(A)): key = A[j] i = j-1 while i > 0 and A[i] > key: A[i+1] = A[i] i = i-1 A[i+1] = key return A if __name__ == "__main__": print insertion_sort([1, 9, 7, 3, 2]) |
To see how it works, we can print the value by:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | def insertion_sort(A): for j in range(1, len(A)): print("Start loop %s" % A) print("Index of %d with value %d " % (j, A[j])) key = A[j] i = j-1 print("Previous Index: %d with value %d " % (i, A[i])) while i > 0 and A[i] > key: print A print("I = %d and previous value %d > current %d " % (i, A[i], key)) A[i+1] = A[i] print A i = i-1 A[i+1] = key print A return A if __name__ == "__main__": print insertion_sort([1, 9, 7, 3, 2]) |
And the results:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | Start loop [1, 9, 7, 3, 2] Index of 1 with value 9 Previous Index: 0 with value 1 [1, 9, 7, 3, 2] Start loop [1, 9, 7, 3, 2] Index of 2 with value 7 Previous Index: 1 with value 9 [1, 9, 7, 3, 2] I = 1 and previous value 9 > current 7 [1, 9, 9, 3, 2] [1, 7, 9, 3, 2] Start loop [1, 7, 9, 3, 2] Index of 3 with value 3 Previous Index: 2 with value 9 [1, 7, 9, 3, 2] I = 2 and previous value 9 > current 3 [1, 7, 9, 9, 2] [1, 7, 9, 9, 2] I = 1 and previous value 7 > current 3 [1, 7, 7, 9, 2] [1, 3, 7, 9, 2] Start loop [1, 3, 7, 9, 2] Index of 4 with value 2 Previous Index: 3 with value 9 [1, 3, 7, 9, 2] I = 3 and previous value 9 > current 2 [1, 3, 7, 9, 9] [1, 3, 7, 9, 9] I = 2 and previous value 7 > current 2 [1, 3, 7, 7, 9] [1, 3, 7, 7, 9] I = 1 and previous value 3 > current 2 [1, 3, 3, 7, 9] [1, 2, 3, 7, 9] [1, 2, 3, 7, 9] [Finished in 0.0s] |
Now we can applied pseudo-code into Python code with insertion sort algorithm as example 🙂