JavaScript for Absolute Beginners 5

In this tutorial, we’re going to implement insertion sort algorithm using JavaScript.



Other tutorials of this series.

Notes for this tutorial:

Task for this tutorial:

  • Implement insertion sort algorithm

There are many sorting algorithm, e.g.:

  • quick sort
  • merge sort
  • insertion sort
  • bubble sort

What is an array?

  • a contiguous block of allocated memory used to store a list of data
  • fixed size

What is a list?

  • just like array but with dynamic size

Operations of a list

Operations of a list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//initialization
const list = [10, 20, 30, 40, 50];

//assign value
list[1] = 21;
//[10, 21, 30, 40, 50]

//get length
console.log(list.length); //5

//push (add element to the end)
list.push(60);
//[10, 21, 30, 40, 50, 60]

//insert
list.splice(1, 0, 22);
//[10, 21, 22, 30, 40, 50, 60]

//delete
list.splice(3, 1);
//[10, 21, 22, 40, 50, 60]

//iterate a list
for (let i=0; i<list.length; i++) {
console.log(list[i]);
}
//10
//21
//22
//40
//50
//60

for loop

for loop
1
2
3
4
const list = [1, 2, 3, 4, 5];
for (let i = 0; i < list.length; i++) {
console.log(list[i]);
}

while loop

while loop
1
2
3
4
5
6
const list = [1, 2, 3, 4, 5];
let i = 0;
while (i < list.length) {
console.log(list[i]);
i++
}

Using debugger

  • Set breakpoints
  • Step over
  • Step into
  • Examine the values of variables

Time complexity of insertion sort

  • \(O(n^2)\)

The source code of the program in this tutorial on GitHub.