Homework SourseShow me how to do insertion sort on this arraynot the code s
Show me how to do insertion sort on this array(not the code, show me how to do this specific array):
81, 8, 18, 288, 300,50, 15, 788, 10, 1, 4, 384, 898
Solution
Suppose we have an array A with n elements in memory. i.e. A[1], A[2], ……. , A[n]. The insertion sort algorithm scans A from A[1] to A[n], inserting each element A[K] into ts proper position.
Solution:
Pass
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8]
A[9]
A[10]
A[11]
A[12]
A[13]
K = 1
81
8
18
288
300
50
15
788
10
1
4
384
898
K = 2
8
81
18
288
300
50
15
788
10
1
4
384
898
K = 3
8
18
81
288
300
50
15
788
10
1
4
384
898
K = 4
8
18
81
288
300
50
15
788
10
1
4
384
898
K = 5
8
18
81
288
300
50
15
788
10
1
4
384
898
K = 6
8
18
50
81
288
300
15
788
10
1
4
384
898
K = 7
8
15
18
50
81
288
300
788
10
1
4
384
898
K = 8
8
15
18
50
81
288
300
788
10
1
4
384
898
K = 9
8
10
15
18
50
81
288
300
788
1
4
384
898
K = 10
1
8
10
15
18
50
81
288
300
788
4
384
898
K = 11
1
4
8
10
15
18
50
81
288
300
788
384
898
K = 12
1
4
8
10
15
18
50
81
288
300
384
788
898
Sorted
1
4
8
10
15
18
50
81
288
300
384
788
898
Explanation:
Step 1: We are given an unsorted array (K=1).
Step 2: Insertion sort compares the first two elements (in K=1). It finds that 81 and 8 are not in ascending order. So, move 8 in A[1] and 81 in A[2]. We get the result K=2.
Step 3: Insertion sort compares A[2] and A[3] (in K=2). It finds that 81 and 18 are not in ascending order. So, move 18 in A[2] and 81 in A[3]. We get the result K=3.
Step 4: Insertion sort compares A[3] and A[4] (in K=3). It finds that 81 and 288 are in ascending order. So for now, 81 is in sorted sub-list. We get the result K=4.
Step 5: Insertion sort compares A[4] and A[5] (in K=4). It finds that 288 and 300 are in ascending order. So for now, 288 is in sorted sub-list. We get the result K=5.
Step 6: Insertion sort compares A[5] and A[6] (in K=5). It finds that 300 and 50 are not in ascending order. So, move 50 in A[3] and 300 in A[6]. We moved 50 in A[3] as 18 in A[2] is the number smaller than 50.We get the result K=6.
Step 7: Insertion sort compares A[6] and A[7] (in K=6). It finds that 300 and 15 are not in ascending order. So, move 15 in A[2] and 300 in A[7]. We moved 15 in A[2] as 8 in A[1] is the only number smaller than 15. We get the result K=7.
Step 8: Insertion sort compares A[7] and A[8] (in K=7). It finds that 300 and 788 are in ascending order. So for now, 300 is in sorted sub-list. We get the result K=8.
Step 9: Insertion sort compares A[8] and A[9] (in K=8). It finds that 788 and 10 are not in ascending order. So, move 10 in A[2] and 788 in A[9]. We moved 10 in A[2] as 8 in A[1] is the only number smaller than 10. We get the result K=9.
Step 10: Insertion sort compares A[9] and A[10] (in K=9). It finds that 788 and 1 are not in ascending order. So, move 1 in A[1] and 788 in A[10]. We moved 1 in A[1] as 1 is the smallest number in the array. We get the result K=10.
Step 11: Insertion sort compares A[10] and A[11] (in K=10). It finds that 788 and 4 are not in ascending order. So, move 4 in A[2] and 788 in A[11]. We moved 4 in A[2] as 1 in A[1] is the only number smaller than 4. We get the result K=11.
Step 12: Insertion sort compares A[11] and A[12] (in K=11). It finds that 788 and 384 are not in ascending order. So, move 788 in A[12] and 384 in A[11]. We get the result K=12.
Step 13: We get a sorted array. (K=12 is sorted array)
| Pass | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] | A[10] | A[11] | A[12] | A[13] |
| K = 1 | 81 | 8 | 18 | 288 | 300 | 50 | 15 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 2 | 8 | 81 | 18 | 288 | 300 | 50 | 15 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 3 | 8 | 18 | 81 | 288 | 300 | 50 | 15 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 4 | 8 | 18 | 81 | 288 | 300 | 50 | 15 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 5 | 8 | 18 | 81 | 288 | 300 | 50 | 15 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 6 | 8 | 18 | 50 | 81 | 288 | 300 | 15 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 7 | 8 | 15 | 18 | 50 | 81 | 288 | 300 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 8 | 8 | 15 | 18 | 50 | 81 | 288 | 300 | 788 | 10 | 1 | 4 | 384 | 898 |
| K = 9 | 8 | 10 | 15 | 18 | 50 | 81 | 288 | 300 | 788 | 1 | 4 | 384 | 898 |
| K = 10 | 1 | 8 | 10 | 15 | 18 | 50 | 81 | 288 | 300 | 788 | 4 | 384 | 898 |
| K = 11 | 1 | 4 | 8 | 10 | 15 | 18 | 50 | 81 | 288 | 300 | 788 | 384 | 898 |
| K = 12 | 1 | 4 | 8 | 10 | 15 | 18 | 50 | 81 | 288 | 300 | 384 | 788 | 898 |
| Sorted | 1 | 4 | 8 | 10 | 15 | 18 | 50 | 81 | 288 | 300 | 384 | 788 | 898 |
