Bubble Sort / Insertion Sort

index.md

Day 6 Learning DSA / LeetCoding - Bubble Sort / Insertion Sort

Bubble Sort:

This is a bubble sort algorithm that repeatedly loops through an array, comparing adjacent elements. If an element is greater than the next element, it swaps them. This process continues until no more swaps are needed, resulting in a sorted array in ascending order."

-- For Example: [-6, -8, 5, 1, 10] should sort out to be [-8, -6, 1, 5, 10]

[5, 2, 9, 1, 5, 6] should sort out to be [1, 2, 5, 5, 6, 9]

In javascript we can write it as

function bubbleSort(arr: number[]) {
   let swapped
   do {
       swapped = false
       for (let i = 0; i < arr.length - 1; i++) {
           if (arr[i] > arr[i + 1]) {
               let temp = arr[i]
               arr[i] = arr[i + 1]
               arr[i + 1] = temp
               swapped = true
           }
       }
   } while (swapped)
}
let arr = [5, 2, 9, 1, 5, 6]
bubbleSort(arr)

we added a do/while loop so the function can run repeatedly till "swapped" is true. Since we have two nested loops our time complexity becomes O(n^2)

Insertion Sort

Insertion sorting is similar to the bubble sorting style but i this case we save or compair 2 or more element/nodes. One which we think is sorted and the next element after that.

Example:

We have [3,4,6,1]. Firstly, we start with 3 then check if 3 > 4: no it's not so we have [3,4,6,1] Next, is 4 > 3: no it's not so we have [3,4,6,1] Next, is 6 > 3: no | is 6 > 4: no. So we still have [3,4,6,1] Finally, is 1 > 3: yes. now we push 1 and we get [1,3,4,6]

Problem:

In javascript we can write this as:

function insertion(arr: number[]) {
    for (let i = 1; i < arr.length; i++) {
        let currentIndex = arr[i]; // initially from our array this is 4 compared with
        let j = i - 1;            // 2 
        while (j >= 0 && arr[j] > currentIndex) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = currentIndex
    }
    return arr
}
let list = ([2, 4, 1, 5])
insertion(list)