Bubble sort and insertion sort are two commonly used sorting algorithms in computer science. Both algorithms work by repeatedly comparing and swapping elements in a list until the list is sorted.
Bubble Sort:
Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm takes its name from the way smaller elements "bubble" to the top of the list.
Here is how bubble sort works:
1) Start at the beginning of the list.
2) Compare the first two elements. If the first element is greater than the second element, swap them.
3) Move to the next pair of elements and repeat step 2.
4) Continue this process until the end of the list is reached.
5) Repeat steps 1-4 until no swaps are made on a pass through the list.
Here is an example of how bubble sort works on a list of numbers:
Unsorted List: 4, 2, 7, 1, 3
Pass 1: 2, 4, 1, 3, 7
Pass 2: 2, 1, 3, 4, 7
Pass 3: 1, 2, 3, 4, 7
The sorted list is 1, 2, 3, 4, 7.
Code for Bubble sort:-
function bubbleSort(arr){
let n = arr.length;
for(var i=0;i < n;i++) {
for(var j=0;j < (n-i-1);j++) {
if(arr[j] > arr[j+1]) {
var temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
var arr=[2,3,1,4,7,6];
const sortedArray = bubbleSort(arr);
console.log(sortedArray); //output : [1,2,3,4,6,7]
Time complexity and space complexity of Bubble sort:
Time complexity: o(n^2) // as we have nested for loops
Space complexity: o(1) // as we are not storing anything in array, object etc
Insertion Sort:
Insertion sort is another simple sorting algorithm that works by building a sorted list one item at a time. The algorithm works by iterating through an unsorted list, and inserting each element into the correct position in a new, sorted list.
Here is how insertion sort works:
1) Start at the beginning of the list.
2) Take the next element and insert it into the correct position in the sorted list.
3) Repeat step 2 until all elements have been inserted.
Here is an example of how insertion sort works on a list of numbers:
Unsorted List: 4, 2, 7, 1, 3
Pass 1: 2, 4, 7, 1, 3
Pass 2: 2, 4, 1, 7, 3
Pass 3: 2, 1, 4, 7, 3
Pass 4: 1, 2, 4, 7, 3
Pass 5: 1, 2, 4, 3, 7
Pass 6: 1, 2, 3, 4, 7
The sorted list is 1, 2, 3, 4, 7.
Code for Insertion sort:-
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j;
for (j= i - 1; j >= 0 && arr[j] > key; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
return arr;
}
// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = insertionSort(unsortedArray);
console.log(sortedArray); // Output: [11, 12, 22, 25, 34, 64, 90]
Time complexity and space complexity of Insertion sort:
Time complexity: o(n^2) // as we have nested for loops
Space complexity: o(1) // as we are not storing anything in array, object etc
Conclusion:
As you can see,
bubble sort and
insertion sort are both effective sorting algorithms, but bubble sort can be less efficient than insertion sort due to its need to perform many swaps, while insertion sort only needs to insert elements into the correct position.