Skip to main content

Iterative

Bubble Sort​

Worse Time complexity O(N^2) Best Time complexity O(n) Space complexity constant

Explanation​

The bubble sort is the concept that compare two numbers and the larger one goes right.

ex: [5,3,2,4,1]

First round​

  • The first item 5 compare to second 3, so 5 larger than 3 and then two numbers swap => [3,5,2,4,1]
  • Next, 5 will continue to compare with 2, so 5 and 2 will swap => [3,2,5,4,1]
  • Next, 5 will continue to compare with 4, so 5 and 4 will swap => [3,2,4,5,1]
  • Next, 5 will continue to compare with 1, so 5 and 1 will swap => [3,2,4,1,5]

Second round​

[3,2,4,1,5]

  • The first item 3 compare to second 2, so 3 larger than 2 and then two numbers swap => [2,3,4,1,5]
  • Next, 3 will continue to compare with 4, but 4 is larger => [2,3,4,1,5]
  • And then it pick 4 to compare with 1 => [2,3,1,4.5]

Third round​

[2,3,1,4.5]

  • The first item 2 compare to second 3, so 3 larger than 2 => [2,3,1,4,5]
  • Next, 3 will compare with 1, so they will swap => [2,1,3,4,5]

Fourth round​

[2,1,3,4.5]

  • The first item 2 compare to second 1, so 2 larger than 1 => [1,2,3,4,5]

Fifth round​

[1,2,3,4.5]

  • Check all the item if there is need to be swap, if there is no swap then stop the while loop

Implementation​

function bubbleSort(nums){
    let swaped = false
    
    do {
        swaped = false

        for(let i = 0; i < nums.length ; i++){
            if (nums[i] < numsp[i+1]){
                const temp = nums[i]
                nums[i] = nums[i + 1]
                nums[i + 1] = temp
                swaped = true
            }
        }   
    } while(swaped)
}

bubbleSort([10,5,6,3,2,7,1,4,8,9])

Insert Sort​

Worse Time complexity O(n^2) Best Time complexity O(n) Space complexity constant

Explanation​

The insert sort is the concept of keep the left list to be sorted list and then take the target item to compared from the end of the sorted list to the beginning. If the the left item is smaller then insert into it.

ex: [5,3,4,2,1]

First round​

  • The first item will be the sorted list
  • The target will start from index 1 which is number 3.
  • Because 3 is smaller than five, so 5 will move one step right => [5,5,4,2,1]
  • Then 3 will insert into the first index => [3,5,4,2,1]

Second round​

  • 3 and 5 will be the sorted list
  • The target will start from index 2 which is number 4.
  • Because 4 is smaller than 5, so 5 will move one step right => [3,5,5,2,1]
  • Next, 4 will continue to compare with 3, but 4 is larger than 3
  • So 4 will insert into the first index => [3,4,5,2,1]

Third round​

  • 3 ,4 and 5 will be the sorted list
  • The target will start from index 3 which is number 2.
  • Because 2 is smaller than 5, so 5 will move one step right => [3,4,5,5,1]
  • Next, 2 will continue to compare with 4, so 4 will move one step right => [3,4,4,5,1]
  • Next, 2 will continue to compare with 3, so 3 will move one step right => [3,3,4,5,1]
  • And then 2 will insert into the first index => [2,3,4,5,1]

Fourth round​

  • 2, 3 ,4 and 5 will be the sorted list
  • The target will start from index 4 which is number 1.
  • Because 1 is smaller than 5, so 5 will move one step right => [2,3,4,5,5]
  • Next, 1 will continue to compare with 4, so 4 will move one step right => [2,3,4,4,5]
  • Next, 1 will continue to compare with 3, so 3 will move one step right => [2,3,3,4,5]
  • Next, 1 will continue to compare with 2, so 2 will move one step right => [2,2,3,4,5]
  • And then 1 will insert into the first index => [1,2,3,4,5]

Implementation​

function insertSort(nums){
    for (let i = 1; i < nums.length; i++){
        const temp = nums[i]
        let j   
        
        for (j = i - 1; nums[j] > temp && j < nums.length; j--){
            nums[j + 1] = nums[j]   
        }

        nums[j + 1] = temp
    }
}

insertSort([10,5,6,3,2,7,1,4,8,9])