How does bubble sort and insertion sort workSolutionBubble s

How does bubble sort and insertion sort work?

Solution

Bubble sort uses two nested loops and compares adjacent elements
=> swaps if they are not in order else continue
Basically, bubble sort compares adjact elements in array during multiple passes through the array and exchanges those that are out of order. During each pass through the array, the value of next largest elemnt is determined and the it is bubbled up to the location it belongs.
Since two nested loops are involved time complexity is O(n^2)

Insertion Sort also works in O(n^2) time but in a different manner. It works by maintaining a sorted subarray in the lower positions of the array. Every new item is then inserted back into the previous sorted subarray such that the size of sorted subarray is increased by one. the process continues until we reach the end of array.