Question

Sort the following lists with bubble sort and insertion sort algorithms. Show your steps.

10,11,5,3,15,17,1,2,20,21,4

Answer 1

Bubble Sort: Bubble sort begins the algorithm by comparing the adjacent elements one by one and swapping if element at current index is greater than element next to current index. Like this algorith will run for n-1 passes and produce an list of sorted elements. In each pass a greater element or smaller element will be bubbled out ana in the next pass comparision will continue before to that bubbled element. consider the tracing of below example.
Elements:10,11,5,3,15,17,1,2,20,21,4
First Pass:
since 10 is less than 11 no swapping is required and now index will movw to next position and picks the next element 11
sice 11 is greater than 5 now elements will be swapped after this comparision list will be like this
10,5,11,3,15,17,1,2,20,21,4
now index will movw to next position that is position 2 and element at that position is 11 now 11 will be compared with 3 since 11 is greater than 3 bothe the elements will be swapped afther this comparision list will be as follows
10,5,3,11,15,17,1,2,20,21,4
now 11 will be compared with 15 no swapping required as 11 < 15
now 15 will be compared with 17 and no swapping required since 15<17
now 17 will be compared with 1 and both elements will be swapped as 17 > 1 now list is as follows
10,5,3,11,15,1,17,2,20,21,4
now 17 will be compared with 2 and both elements will be swapped since 17 > 2
10,5,3,11,15,1,2,17,20,21,4
now 17 will be compared with 20 and no swapping required since 17 < 20
now 20 will be compared with 21 and no swapping required since 20 < 21
now 21 will be compared with 4 and both the elements will be swapped since 21 > 24
with this first was completed and list will be as follows
10,5,3,11,15,1,2,17,20,4,21
if you observe the above list as said earlier after the first pass one element will be bubbled up and that is 21
now in the second pass the comparision will occur before the index of 21
Second pass:
10>5 so list will be
5,10,3,11,15,1,2,17,20,4,21
since 10>3 list is as follows
5,3,10,11,15,1,2,17,20,4,21
since 10 < 11 no change in list
11 < 15 so no change in list
15 < 1 so list is as follows
5,3,10,11,1,15,2,17,20,4,21
in next comparision 15 < 2 so list is as follows
5,3,10,11,1,2,15,17,20,4,21
since 15 < 17 no change in list
since 17 < 20 no changes in list
since 20 < 4 list is as follows
5,3,10,11,1,2,15,17,4,20,21
no need of comparinhg 20 with 21 as the position of 21 is fixed
5,3,10,11,1,2,15,17,4,20,21
if you observe in this pass 20 is bubbled up and placed in its correct position
Third pass:
after third pass list is as follows
5,3,10,11,1,2,15,4,17,20,21
after 4th pass list will be like this
5,3,10,11,1,2,4,15,17,20,21
after fifth pass list is as follows
5,3,10,1,2,4,11,15,17,20,21
after 6 th pass list is a s follows
5,3,1,2,4,10,11,15,17,20,21
after 7 th pass list is as follows
3,1,2,4,5,10,11,15,17,20,21
after 8 th pass list will be as follows
1,2,3,4,5,10,11,15,17,20,21
as list is already sorted there is no change in the list for 9th and 10th passes.

Insertion Sort:

list: 10,11,5,3,15,17,1,2,20,21,4

in insertion sort one element is picked up and will be compared with the elements before it and swapping the elements if required.
10,11,5,3,15,17,1,2,20,21,4
Insertion sort starts comparing the first two elements since 10 and 11 are already in sorting order they will not be swapped and now 11 will be compared with 5 and they will be swapped since 11 >5 now the list will be
10,5,11,3,15,17,1,2,20,21,4
and now 5 will be compared with 10 since 5 is less than 10 5 and 10 will be swapped now the list will be
5,10,11,3,15,17,1,2,20,21,4
and now element 11 is picked and will be compared with all the elements before it
since 11 and 10 will not be swapped since 11 > 10 now change in list
now 1 is compared with 5 since 1 < 5 both will be swapped.
1,5,10,3,15,17,1,2,20,21,4
like this each time one element will be picked up and array will be sorted as follows
1,2,3,4,5,10,11,15,17,20,21