Building an Insertion Sort Demo

Building the Insertion Sort Demo

An Insertion Sort Demo

The previous three lessons, Creating User Interactive Applications Part 1, Creating User Interactive Applications Part 2 and Creating User Interactive Applications Part 3, lay out a basic plan for developing a user interactive application. What we want to do in this lesson is to take that plan to build the Insertion Sort Demo.

Starting the lesson

To start this lesson, I have created some templates that you can use to start. The templates will include the node.mjs and pointers.mjs modules from the last lesson. The templates also will have starting code for index.html and index.mjs for the main application. You can review how to use a starter template here: Using a starter template

Starting with CodeSandbox

Login to your CodeSandbox account. In a different tab in the browser, navigate to this link: Starter template for Insertion Sort Lesson. Click on the Fork drop-down menu and save it to your project area. In the EXPLORER area, open the SANDBOX INFO drop-down and click on the pencil icon to edit the sandboxes' information. Change the Title to "Insertion Sort Demo".

Starting with Vite

Run the following commands from a terminal:

$ cd ~/Documents
$ npx degit takebayashiv-cmd/insertion-sort-template sort2
$ cd sort2
$ npm install
$ npm run dev

Line 1 changes to the directory where you have been storing all your projects. Line 2 will get the template from a GitHub account and save the project files inside the sort2 directory. Line 3 changes into that sort2 directory. Line 4 installs all the required packages, and line 5 will start up the Vite server.

To add new files to the project, use Visual Studio Code and Open the folder that contains the main files (e.g. index.html and index.mjs).

Modifying the front end, index.html

Let’s modify the front end of our application by editing index.html. This will involve adding in a number of elements. These include:

A <textarea> element that will be used to hold the Status messages.
A <label> element that will display the running total of the number of Locate clicks.
Another <label> element that will display the running total of the number of Insert clicks.
Three <button> elements. These are the Next Pos, Locate and Insert buttons that will be clicked on by the user to step through the Insertion Sort process.

The advantage of modifying the front end first, is that this serves as a prototype. The look of the final application can be shown by adding HTML markup. The added elements may not do anything yet, but we do see how they will be laid out. Then, in later steps we will gradually add code to make these elements interact with the user. This is an important early step in building the user interface for the application. To save some time, the template you are using already has an input text box where the user can enter the comma-separated value string. In addition, the Ok button is already shown, although the code to handle clicking on the Ok button has not been added yet.

Here is the new version of index.html:

index.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <script type="module" src="index.mjs"></script>
    <title>Insertion Sort Demo</title>
  </head>
  <body>
    <h1>Insertion Sort</h1>
    Enter a comma separated list of numbers, then click <b>Ok</b>:
    <input type="text" id="numbox" />
    <button id="ok_button">Ok</button>
    <br /><br />
    <textarea id="status_area" style="width: 80%;" rows="3">Status Area</textarea>
    <br />
    Locates:
    <label id="locates_label"></label>&nbsp; &nbsp; &nbsp;
    Inserts:
    <label id="inserts_label"></label>
    <br /><br />
    <button id="next_button">Next Pos</button>
    <button id="locate_button">Locate</button>
    <button id="insert_button">Insert</button>
    <br />
    <svg
      id="svg_area"
      width="1000"
      height="130"
      xmlns="http://www.w3.org/2000/svg"
    ></svg>
  </body>
</html>

The new lines are 14-24. Line 14 sets up a <textarea> element. The style attribute will make this <textarea> have a width of 80% of the browser window. The number of rows is set to 3. If you enter more text than would fit in 3 rows, the <textarea> will become scrollable. Line 15 just adds a blank line before the <label> elements set up on lines 16-19. Note on line 16 and line 18, that we add some text to show what the labels will be used for.

Line 20 adds a blank line before the <button> elements. Lines 21-23 put in the Next Pos, Locate and Insert buttons respectively. Line 24 just adds another blank line before the svg area.

The following screen shot shows what the app looks like after these changes:

Create the insert_sorter.mjs module

Next, we can create the insert_sorter.mjs module. This module will define the InsertionSorter class that will perform the actual Insertion Sort and generate the sort steps that will be used to animate the sort.

If you are using CodeSandbox, go to the EXPLORER section, right-click on src, select New File and add the file insert_sorter.mjs. If you are using Vite, start up Visual Studio Code and open the folder that you have your project files in. In the Explorer section on the left, right click in the area where your files are shown and select New File.

The InsertionSorter class will be set up in a similar fashion to the SelectionSorter class we used for the last two lessons. This class will have a constructor that will have a parameter that is the string that contains the comma-separated numbers to create the array that is to be sorted. In addition, the InsertionSorter class will have a method called getSortSteps() that will perform the actual Insertion Sort on the array, and also return the sort steps needed to animate the sort. The InsertionSorter class will also have a method getOriginalArray() that returns the original unsorted array of numbers.

Let’s work on the InsertionSorter class in three steps. Here are the steps:

Define the constructor and getOriginalArray() methods.
Develop the algorithm for the Insertion Sort and implement the first version of the getSortSteps() method.
Modify the getSortSteps() method to add the sort steps needed to animate the sort in the main application.

Defining the constructor and getOriginalArray() methods for the InsertionSorter class

The first step will be to set up the constructor and define the getOriginalArray() method to return the original array of numbers to the calling program, index.mjs. So, here is the first version of the insert_sorter.mjs module:

insert_sorter.mjs

export class InsertionSorter {
  constructor(numstring) {
    this.num_array = [];
    this.originalArray = [];
    const nums = numstring.trim().split(",");
    for (let num of nums) {
      this.num_array.push(Number(num));
      this.originalArray.push(Number(num));
    }
  }

  getOriginalArray() {
    return this.originalArray;
  }
}

Lines 2-10 define the constructor for the InsertionSorter class. This constructor has a single parameter, numstring, that is the comma-separated value string passed from the calling program. Lines 3 and 4 declare empty arrays for storing the numbers obtained by processing that string. The reason why we need two such arrays, is that we want to return the unsorted array, originalArray, to the calling program. The array, num_array, is the array that we perform the Insertion Sort on. So, this array will wind up being in sorted order. In programming, there are different ways of sorting an array, but there is no algorithm for "unsorting" an array. So, we have to keep a copy of the original unsorted array if we want to be able to access that array.

Line 5 first calls trim() to remove any potential leading or trailing whitespace, then calls split() to split the string into an array of strings. If you had a string that was defined as this " 1, 2, 3, 4 ", the trim() method will turn that string into "1, 2, 3, 4". So, the spaces at the beginning and end are trimmed off. The spaces in between the first non-whitespace character and the last non-whitespace character are left unchanged.

Lines 6-9 define the for loop that converts the array elements in nums to a number, using the Number() function and then stores the resulting numbers in the num_array and originalArray arrays. Lines 12-13 define the getOriginalArray() method, that will return the original unsorted array of numbers to the calling program.

Since we already have index.html and index.mjs set up to the point where we have a prototype. We can make some modifications to index.mjs to test out the InsertionSorter class. Here is the new version of index.mjs that does this:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk() {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
    },

    handleNextPos() {},

    handleLocate() {},

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk();
  });
}

The new lines are 3, 19-20 and 40-42. Line 3 imports the InsertionSorter class from the insert_sorter.mjs module. Line 19 gets a reference to the input text box where the user will enter a comma-separated value string. Line 20 declares the in_srt variable. The in_srt variable will be the reference to the InsertionSorter object that will be constructed inside the handleOk() handler. We need to reconstruct in_srt each time the user hits the Ok button.

Line 40 takes the value from the input text box and constructs the InsertionSorter object, in_srt. Line 41 uses in_srt to call the getOriginalArray() method to return the original array of unsorted numbers. Line 42 simply displays that array to the Console.

Here is a screen shot showing the app with the user entering "5,3,9" and hitting the Ok button.

As you can see, the correct array of numbers has been returned. Let’s modify index.mjs to make use of this original array of numbers. We can use this array to to display the numbers as Node objects. Here is the next version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk() {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
    },

    handleNextPos() {},

    handleLocate() {},

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk();
  });
}

The new lines are 21-26 and 49-55. Lines 21-26 add more private variables and constants to the factory function. Lines 21 and 22 set coordinates that determine where the nodes will be drawn. Lines 23 and 24 set the width and heigh of those nodes, respectively. Line 25 declares node_array. Recall that this is the array that must be manipulated to perform the sort animation with the nodes. Line 26 obtains a reference to the svg area, and stores this reference as svg_area. This is needed to draw our nodes in the window.

Line 49 resets node_array to be an empty array. Each time the user click on the Ok button, you need to do this. Otherwise, you will have elements left over from a previous run. Lines 50-55 define a for loop that iterates over originalArray. Line 51 is just for convenience so that the instruction on line 52 does not get even longer. Line 52 constructs a new Node object. Line 53 stores that node in node_array and line 54 draws the node in the svg area.

Here is a screen shot showing the result of the user entering the string "4,13,7,6,22" and clicking the Ok button.

Our prototype is starting to shape up, as now the app can actually do something. The second step that we can take for the insert_sorter.mjs module is to create the getSortStep() method for the InsertionSorter class.

Developing the algorithm for the Insertion Sort

The way that the Insertion Sort works, is that we start with the second element in the array and check if that element has a value less than the array element to its left. Since we want the sorted array to go from the smallest to largest element, this means that the starting element should move to the left. That "locate" process continues until either the end of the array is reached or the element to the left is not smaller than the starting element’s value. Once either of those two conditions are met, the correct insertion point has been located. At that point, the starting element is inserted in that position after moving all the elements from the starting point to the insertion point one position to the right. After that, the starting position is moved one to the right and the process is repeated. This continues until the starting position has reached the last position in the array and has been properly inserted. We can get a better feel for this by using some screen shots from the Insertion Sort Demo.

Here is a screen shot showing the first starting position after hitting the Next Pos button:

Note that the starting position begins with the second element of the array. When the Locate button is clicked, the program checks to see if the value at the start position is less than the element to its left.

Since 16 is indeed less than 42, the blue arrow pointer is moved to the left. Since we have reached the end of the array, the "locate" process is stopped. So, an Insert will be done.

The following shows that the 16 has been inserted into the first position.

Since we have sorted correctly with the second array element in the starting position, we can proceed to make the starting position the third array element. So, after hitting the Next Pos button, the blue arrow pointer points to the new starting position.

When you hit the Locate button next, 9 will be compared to 42. Since 9 is less than 42, the blue arrow pointer is moved to the left.

When the Locate button is next hit, 9 will be compared to 16. Since 9 is less than 16, the blue arrow pointer will be moved to the left.

At that point, we have reached the end of the array, so the next step will be an Insert. After clicking on the Insert button, the 9 is inserted into the new position.

At this point, you can see that the array has been correctly sorted for the first three positions. These are not necessarily the final positions. But, you can hopefully see how the Insertion Sort works. From wherever the starting position is, the sort will insert the element in the starting position into the correct position from that starting position up to the rest of the array to the left. When the Next Pos button is clicked, the new starting position will be pointing to the 18. Where will the 18 be inserted? If you said that 18 will be inserted between the 16 and the 42, you are correct. That is shown in the next three screen shots.

Since 18 is not less than 16, the next step is an Insert. The 18 is now shown in the correct position.

When, the Next Pos button is clicked, the blue arrow pointer will move to the new starting position and be pointing to the 14. This is because the first four positions of the array have already gone through the location and insertion process. Where will the 14 be inserted? If you said that 14 will be inserted between the 9 and the 16, you are correct. This will be shown in the next series of screen shots.

Here is the starting position:

14 is less than 42 so the blue arrow pointer moves to the left.

14 is less than 18 so the blue arrow pointer moves to the left.

14 is less than 16 so the blue arrow pointer moves to the left. But 14 is not less than 9 so an insert be performed.

So, the 14 has now been inserted into the correct position.

The next screen shot is where the Next Pos button has already been clicked and the new starting position is being pointed at.

The following animated gif will show the rest of the sorting steps until the array is completely sorted. The Status Area is included in this animated gif, so you can view those messages.

Click on Reload gif to replay animation.

Hopefully, you now have a decent idea of how the Insertion Sort works. It would be a good idea to go back to the Insertion Sort Demo and try a few examples with just a few numbers to make sure you can predict what will happen before you click on the enabled button.

Coming up with the algorithm for the Insertion Sort

Let’s start with a very simple algorithm for the Insertion Sort

Insertion Sort algorithm: first pass

Set a start position
Compare the value at this start position to the elements to the left
If array end is reached OR value is not less than an element
    insert at that position
Increment the start position and repeat steps 1-4 until done

This is not a proper computer algorithm, but it roughly describes what has to be done. Let’s turn this into a more proper computer algorithm

Insertion Sort algorithm: second pass

Preconditions:
An array of numbers with n elements with index i, a[i]

For i = 1 up to end of array, increment i
    temp = a[i]
    pos = i
    While pos > 0 and temp < a[pos-1]
        pos = pos - 1
    Slide the array elements from i to pos-1 to the right
    Insert temp into a[pos]

This looks more like a computer algorithm. But steps 9 and 10 are not detailed enough. So, here is a better algorithm:

Insertion Sort algorithm: third pass

Preconditions:
An array of numbers with n elements with index i, a[i]

For i = 1 up to n-1, increment i
    temp = a[i]
    pos = i
    While pos > 0 and temp < a[pos-1]
        pos = pos - 1
    For j = i down to pos, decrement j
        a[j] = a[j-1]
    a[pos] = temp

In an algorithm we sometimes set preconditions. These are things that must be set before the algorithm is applied. So, this is all that lines 1 and 2 are about.

Lines 4-11 define a for loop, that iterates over the elements of the array, but starting at the second element (i=1). Line 5 stores a[i] as temp. We need this value to do the insert after the end of the inner while loop. Line 6 sets the variable pos to start at i. The variable pos is a pointer to the correct insertion point. So, while i is fixed inside the outer for loop, pos changes inside the inner while loop.

Lines 7-8 define the inner while loop. This will loop will run if pos > 0 and temp < a[pos-1]. The way that the and operator works is that if the statement before the and is false, then the whole statement is false. What this means is that once we reach the end of the array, the while loop will stop running. The condition: temp < a[pos-1] is a test to see if the value at the starting point is less than the value of the array element just to the left. If that test is not true, the while loop stops running. The purpose of this while loop is to find the correct insert position for the element at the starting point.

Lines 9-10 define the inner for loop that will cause the "slide" to occur. This is kind of tricky to understand, so let’s add some diagrams to try to make this easier to understand. In the first diagram, the starting position is i=2. So, the 9 is what we want to place in the correct position.

Now that you have a feel for how the Insertion Sort works, you probably know that the 9 will be inserted at the very start of the array where the 16 is currently located. There is no "slide" operation for arrays, so we need to just copy array elements. So, starting at j = 2, the for loop will perform:

a[j] = a[j-1]

Right after that step, the array would look like this:

So, now there are two elements that hold 42, because a[2] is a copy of a[1]. The next step of this inner for loop will decrement j. So, j = 1 and the operation,

a[j] = a[j-1]

occurs again. So, now the array looks like this:

So, now two elements hold 16 because a[1] is a copy of a[0]. At this point the inner for loop will end. So line 11 will be executed which copies the value of temp to a[pos], were pos = 0.

a[pos] = temp

So, the array will look like this:

So, this shows that the "slide" and insert is really a series of copies. From a computer execution standpoint, copy operations are very efficient. So, this is a good way to carry out that procedure.

Implementing the algorithm to create the getSortSteps() method

With the last version of the algorithm, we can go back to modifying the insert_sorter.mjs module to implement the first version of the getSortSteps() method:

insert_sorter.mjs

export class InsertionSorter {
  constructor(numstring) {
    this.num_array = [];
    this.originalArray = [];
    const nums = numstring.trim().split(",");
    for (let num of nums) {
      this.num_array.push(Number(num));
      this.originalArray.push(Number(num));
    }
  }

  getOriginalArray() {
    return this.originalArray;
  }

  getSortSteps() {
    let a = this.num_array;
    for (let i = 1; i < a.length; i++) {
      const temp = a[i];
      let pos = i;
      while (pos > 0 && temp < a[pos-1]) {
        pos--;
      }
      for (let j = i; j > pos; j--) {
        a[j] = a[j-1];
      }
      a[pos] = temp;
    }
    console.log(a);
  }
}

The new lines are 16-30. These lines define the first version of the getSortSteps() method. This is not the finished version because this only implements the Insertion Sort algorithm. It does not create any of the sort steps needed to animate the SVG objects in the main application.

Line 17 is for convenience. This allows use to refer to a[i] instead of this.num_array[i]. So, the code looks more like the algorithm that we need to implement. Lines 18-28 define the outer for loop that iterates over num_array starting at the second element out to the last element. Line 19 stores the value at the starting position so that we can copy this into the correct insertion position at the end of this for loop. Line 20 sets the starting value for pos to i. If the element is not in the right position, than pos will be decreased inside the while loop on lines 21-23, until pos points to the correct insert position. Lines 24-26 define the inner for loop that starts at the original starting position, i, and decrements down to one greater than pos. Inside this inner for loop, we perform a copy command so that by the end of the for loop all the elements that need to "slide" are copied into the correct positions. Finally, on line 27 temp is copied into the correct insert position.

Line 29 just prints the array to the Console. This is for debugging purposes and is there to let us know if the sort was carried out correctly.

To check if the getSortSteps() method is working correctly, we need to add a line to index.mjs and run the application. Here is the modified version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk() {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      in_srt.getSortSteps();
    },

    handleNextPos() {},

    handleLocate() {},

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk();
  });
}

The new line is line 56. Line 56 just calls the getSortSteps() method of the InsertionSorter class. Here is a screen shot showing that the sort of the array of numbers is being done correctly.

Adding the sort steps to the getSortSteps() method

The third step of creating the insert_sorter.mjs module is to start adding in the sort steps inside the getSortSteps() method. The steps must take into account the Next Pos, Locate and Insert buttons. So, looking at the implementation of the insertion sort, we should figure out what should be stored in the sort_steps array.

When creating the sort steps inside the getSortSteps() method, keep the following in mind about the handlers we need to create:

The handleNext() handler will be used to point to the start position where we can begin to locate the actual insertion point. This should involve a single sort step.
The handleLocate() handler will be moving the pointer to the actual insert location. So, for every step inside the inner while loop, a sort step must be generated.
The handleInsert() handler will handle the actual insertion. This should involve a single sort step.

With those items in mind, let’s start modifying the getSortSteps() method of the insert_sorter.mjs module.

insert_sorter.mjs

export class InsertionSorter {
  constructor(numstring) {
    this.num_array = [];
    this.originalArray = [];
    this.sort_steps = [];
    const nums = numstring.trim().split(",");
    for (let num of nums) {
      this.num_array.push(Number(num));
      this.originalArray.push(Number(num));
    }
  }

  getOriginalArray() {
    return this.originalArray;
  }

  getSortSteps() {
    this.sort_steps = [];
    const steps = this.sort_steps;
    let a = this.num_array;
    for (let i = 1; i < a.length; i++) {
      const temp = a[i];
      let pos = i;
      let obj = {};
      obj.type = "next";
      obj.start = i;
      obj.temp = a[i];
      steps.push(obj);
      while (pos > 0 && temp < a[pos-1]) {
        pos--;
        obj = {};
        obj.type = "locate";
        obj.pos = pos;
        steps.push(obj);
      }
      obj = {};
      obj.type = "insert";
      obj.begin = i;
      obj.end = pos;
      steps.push(obj);
      for (let j = i; j > pos; j--) {
        a[j] = a[j-1];
      }
      a[pos] = temp;
    }
    //console.log(a);
    return steps;
  }
}

The new lines are 5, 18-19, 24-28, 31-34, 36-40 and 46-47. Line 5 adds the instance variable, sort_steps. This is the array that will hold the sort steps. Line 18 sets sort_steps to an empty array so that each time the getSortSteps() method is called, we start with this array being empty. Line 19 just makes it so that we can use steps instead of this.sort_steps inside this method.

Lines 24-28 set up the object, obj, that will need to be stored as one of the sort steps. Line 24 makes sure this object is empty. Line 25 stores "next" as the object’s type property. Line 26 stores i as the object’s start property. This will be needed to point to the starting position each time the outer for loop in the sorting algorithm repeats. Line 27 stores a[i] as the object’s temp property. This is needed so we can compare temp to the element to the current positions’s left. Line 28 stores obj inside of steps.

Lines 31-34 are used to store the sort step needed for a "locate" step. Line 31 empties out obj. Line 32 sets "locate" to be the object’s type property. Line 33 stores pos as the object’s pos property. This will keep track of the current value of pos. Line 34 stores obj inside of steps.

Lines 36-40 are used to store the sort step needed for an "insert" step. Line 36 empties out obj. Line 37 sets "insert" as the object’s type property. Line 38 stores i as the object’s begin property. This is where the copying of elements to perform the "slide" should begin. Line 39 store pos as the object’s end property. The copying of elements to perform the "slide" should end right after this end value. Line 40 stores obj inside of steps.

Line 46 comments out the printing of the sorted array. Line 47 returns the sort steps.

At this point, we can modify index.mjs to make use of the new version of the getSortSteps() method. Within index.mjs we will display the sort steps to the Console, so that we can see if those steps should be adequate to do what we want to animate the sort. Here is the modified version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk() {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
    },

    handleNextPos() {},

    handleLocate() {},

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk();
  });
}

The new lines are 21 and 57-60. Line 21 adds sort_steps as another private variable for the factory function. That is because sort_steps will need to be accessed by all of the handler functions. Line 57 is modified so that instead of just calling getSortSteps() we get the return value and store this as sort_steps.

Lines 58-60 use a for loop to print out all the steps from sort_steps to the Console. Using a for loop will make the output easier to discuss.

The following output to the Console is for the input string "4,13,7,6,22":

console output for "4,13,7,6,22" as input string

index.mjs:72 init called
index.mjs:49 originalArray: (5) [4, 13, 7, 6, 22]
index.mjs:59 {type: 'next', start: 1, temp: 13}
index.mjs:59 {type: 'insert', begin: 1, end: 1}
index.mjs:59 {type: 'next', start: 2, temp: 7}
index.mjs:59 {type: 'locate', pos: 1}
index.mjs:59 {type: 'insert', begin: 2, end: 1}
index.mjs:59 {type: 'next', start: 3, temp: 6}
index.mjs:59 {type: 'locate', pos: 2}
index.mjs:59 {type: 'locate', pos: 1}
index.mjs:59 {type: 'insert', begin: 3, end: 1}
index.mjs:59 {type: 'next', start: 4, temp: 22}
index.mjs:59 {type: 'insert', begin: 4, end: 4}

The sort steps start on line 3. Line 3 is the first sort step. This tells us that the start position is 1, the second element in the array. This also tells us that the value at that position is 13.

Line 4 is the next step. The type for this step is insert. That means that the 13 is already in the correct place. This makes sense because 13 is not less than 4. Note that on line 4, the begin and end value are the same number. This means that no "slide" will take place.

Line 5 is the next step and this is a "next" type step. This tells us that the start position is 2, the third element in the array. The value at that position, which will be set to temp, is 7.

Line 6 is a "locate" type step. This means that the inner while loop is running. That is because 7 is less than the neighbor to its left, the 13. So, line 6 tells us that the new value of pos is 1 at that point. So, the blue arrow pointer we will implement should be pointing at that position in the array.

Line 7 is an "insert" type step. This tells us that the array elements that need to be moved will be from position 2 down to position 2 (one more than end). Is this enough information to perform the "insert". We will discuss this after going through all the lines of output.

Line 8 is a "next" type step. This tells us the position to start at is 3 (4th array element) and that the value of temp is 6.

Line 9 is a "locate" type step. This makes sense because 6 is less than 13 the current left neighbor. The value of pos tells us to point at the third element (pos = 2).

Line 10 is another "locate" type step. This makes sense because 6 is also less than 7, the current left neighbor. The value of pos tells us to point at pos = 1, or the second element in the array.

Line 11 is an "insert" type step. The values of the begin and end property means that the array elements from 3 down to 2 (one more than *end) must be moved over to make room for the insertion. Again, we will discuss if this is enough information to perform the "insert".

Line 12 is a "next" type step. This tells us to point to position 4, the 5th element in the array, and that temp is 22.

Line 13 is an "insert" type step. There is no "locate" step, because 22 is not less than its left neighbor, 13. So, the begin and end values being the same means that the element is already in the correct position.

To perform the copying for the "slide" and insert was somewhat tricky inside the getSortSteps() method. This required a for loop that started from the back end and moved forward. A regular for loop that increments the index would not work because this would copy over the values we needed to perform the "slide". So, we needed a for loop that decremented the loop variable. Then, after that for loop we still needed to do one more copy. This is one of standard ways of performing that part of an Insertion Sort. But, JavaScript arrays have more functionality than arrays in languages like Java or C. In JavaScript, arrays have a splice() method that can remove elements and also add in an element. This makes it much easier to perform the insert in terms of node_array, the array of Node objects. Here is how we remove elements using splice()

splice() to remove elements

array.splice(startIndex, deleteCount);

splice() to add elements

array.splice(startIndex,0, item1, item2, ... itemN);
// note that deletecount is set to 0, to add elements.

example code

let array = [4,13,1,6,22];
console.log(array);
const removed = array.splice(2,1); // removed is [1]
array.splice(0,0,removed[0]); // add the 1 at the front of the array
console.log(array);

The output from the last line would show [1, 4, 13, 6, 22]

It is not obvious if using array.splice() is more efficient than the for loop and copying. But, since all we are doing here is doing the animation for a sort demonstration, we are not worrying about efficiency. If we wanted to sort an array of number in JavaScript most efficiently, we might use the arrays.sort() method of JavaScript arrays.

Anyway, it does seem we are passing enough information for the sort steps to animate the Insertion Sort.

Modifying the pointer.mjs module

We want to use the Pointer class from the pointer.mjs module. At this stage, the Pointer class only has the draw() method implemented. We want to add a moveHorizontal() method to be able to move the Pointer object horizontally for this application. Here is the new version of pointer.mjs:

pointer.mjs

export class Pointer {
  constructor(x1, y1, x2, y2, arrowsize, color, markerId) {
    this.svgNS = "http://www.w3.org/2000/svg";

    this.pointerDefs = document.createElementNS(this.svgNS, "defs");
    this.arrow = document.createElementNS(this.svgNS, "marker");
    this.arrow.setAttribute("id", markerId);
    this.arrow.setAttribute("markerWidth", arrowsize);
    this.arrow.setAttribute("markerHeight", arrowsize);
    this.arrow.setAttribute("refX", arrowsize / 2);
    this.arrow.setAttribute("refY", arrowsize / 2);
    this.arrow.setAttribute("orient", "auto");

    const path = document.createElementNS(this.svgNS, "path");
    const d_val = `M 0 0 L ${arrowsize} ${arrowsize / 2} L 0 ${arrowsize} z`;
    path.setAttribute("d", d_val);
    path.setAttribute("fill", color);

    this.arrow.appendChild(path);
    this.pointerDefs.appendChild(this.arrow);

    this.line = document.createElementNS(this.svgNS, "line");
    this.line.setAttribute("x1", x1);
    this.line.setAttribute("y1", y1);
    this.line.setAttribute("x2", x2);
    this.line.setAttribute("y2", y2);
    this.line.setAttribute("stroke", color);
    this.line.setAttribute("stroke-width", 2);
    this.line.setAttribute("marker-end", `url(#${markerId})`);
  }

  draw(svg_area) {
    svg_area.appendChild(this.pointerDefs);
    svg_area.appendChild(this.line);
  }

  moveHorizontal(newX) {
    this.line.setAttribute("x1", newX);
    this.line.setAttribute("x2", newX);
  }
}

class Line {
  constructor(x1, y1, x2, y2, color) {
    this.svgNS = "http://www.w3.org/2000/svg";
    this.line = document.createElementNS(this.svgNS, "line");
    this.line.setAttribute("x1", x1);
    this.line.setAttribute("y1", y1);
    this.line.setAttribute("x2", x2);
    this.line.setAttribute("y2", y2);
    this.line.setAttribute("stroke", color);
    this.line.setAttribute("stroke-width", 2);
  }
}

export class TwoHeadPointer {
  constructor(
    x1,
    y1,
    x2,
    y2,
    x3,
    y3,
    x4,
    y4,
    arrowsize,
    startcol,
    middlecol,
    endcol,
    startId,
    endId
  ) {
    this.svgNS = "http://www.w3.org/2000/svg";
    this.start = new Pointer(x1, y1, x2, y2, arrowsize, startcol, startId);
    this.middle = new Line(x1, y1, x3, y3, middlecol);
    this.end = new Pointer(x3, y3, x4, y4, arrowsize, endcol, endId);
  }

  draw(svg_area) {
    svg_area.appendChild(this.start.pointerDefs);
    svg_area.appendChild(this.end.pointerDefs);
    svg_area.appendChild(this.start.line);
    svg_area.appendChild(this.middle.line);
    svg_area.appendChild(this.end.line);
  }

  slideEnd(x) {
    console.log(this.end.line);
    this.end.line.setAttribute("x1", x);
    this.end.line.setAttribute("x2", x);
    this.middle.line.setAttribute("x2", x);
  }

  setVisible(bool) {
    if (bool === true) {
      this.start.line.setAttribute("visibility", "visible");
      this.middle.line.setAttribute("visibility", "visible");
      this.end.line.setAttribute("visibility", "visible");
    } else {
      this.start.line.setAttribute("visibility", "hidden");
      this.middle.line.setAttribute("visibility", "hidden");
      this.end.line.setAttribute("visibility", "hidden");
    }
  }
}

The new lines are 37-40. Lines 37-40 define the moveHorizontal() method. This is designed to move the Pointer horizontally to a new x-coordinate. Lines 38 and 39 cause the x1 and x2 attributes to both move to the same newX value. This is a very simple method that assumes you just want the shift the Pointer left or right. By keeping the x1 and x2 attributes the same value, the Pointer will maintain its orientation.

The moveHorizontal() method will be tested when we start to modify the main module, index.mjs

Modifying the main JavaScript file, index.mjs

There are a number of things we need to modify in the index.mjs file. Here is a list of things we need to do:

Add a Pointer object to point at the node that is at the position which will be the "insert" position. This Pointer object must point to the starting position each time the Next Pos button is clicked. In addition, the Pointer object must move to the left neighbor node when the Locate button is clicked.
Plan out each handler function in terms of the need for selection statements and/or repetition statements.
1. handleNext() - This handler should increment the step_count. After the step_count is incremented, this handler needs a selection statement with two cases. This selection statement has to do with what the next sort step will be. If the next step is a "locate" step this handler should disable the NextPos and Insert buttons, and enable the Locate button. Else if the next step is an "insert" step, then this handler should disable the Next Pos and Locate buttons, and enable the Insert button. This second case can occur if the element in the starting position is not less than the element to its left. So, the element is already in the right position.
2. handleLocate() - This step will be first used to update the Status area, but that will be taken care of later. For now, step_count should be incremented so we can see what the next sort step will be. This will require a selection statement that checks to see if the next step is an "insert". If so, then the Next Pos and Locate buttons should be disabled and the Insert button should be enabled.
3. handleInsert() - This handler will require two selection statements. The first selection statement will check to see if the node will stay in place or not.
  1. First selection statement.
    
    If the node is already in the correct position, the node does not have to be moved.
    
    If the node must be moved, a for loop to move nodes to make space for the insert position. Then, the node that must be inserted is copied to that position. Since nodes are actually moving, the node_array array must be modified. In addition, after that modification, the id values of the nodes must be reset so that the id matches the index within node_array.
  2. Second selection statement
    
    If there are still more sort steps to be executed. The step_count must be incremented for this case, and the Next Pos button is enabled. The Locate and Insert buttons are disabled.
    
    Otherwise, the sorting process is complete. For this case, the NextPos, Locate and Insert buttons should be disabled.

Modifying index.mjs to use a Pointer

Let’s start by modifying index.mjs to make use of a Pointer object to point to the node being considered for the "insert" position. We can do this by adding a Pointer object to the list of private variables for our factory function. Then, we can just draw this Pointer inside of the handleOk() handler. This is not where we will actually draw the Pointer from, but it is just to display that object for now.

Here is the new version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(45, 10, 45, 50, 5, "blue");

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk() {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
    },

    handleNextPos() {},

    handleLocate() {},

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk();
  });
}

The new lines are 28 and 62. Line 28 constructs a new Pointer object named pointer. You can adjust the x1, y1, x2 and y2 values so that the arrow looks like what you want. Line 62 draws pointer to the svg area. You can enter a comma-separated value string in the input text box and click Ok to see what pointer looks like and adjust the coordinates to make the arrow look like what you want. It is important to get the y1 and y2 values at this point, because when we move pointer, it will only be moved horizontally.

Here is a screen shot showing how the pointer appears after clicking the Ok button:

Modifying the handleNext() handler inside of index.mjs

Now that we can see the Pointer object, let’s work on the handleNext() handler. As stated above, this method will need to handle two cases, so it has a selection statement. This method will also point at the starting position for locating the insert position. Taking care of pointer first, then incrementing step_count will allow checking what the next sort step type will be, "locate" or "insert". The selection statement will be used to deal with those two cases.

Here is the next version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      const step = sort_steps[step_count];
      console.log(JSON.stringify(step));
      temp = step.temp;
      const x = xStart + step.start*(width + 20)+ width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
    },

    handleLocate() {},

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });

}

The new lines are 29-30, 49, 65-68, 71-88, 101-103, 105 and 107-109. Let’s start with the changes inside the init() function. The changes are on lines 101-103, 105 and 107-109. Line 101 gets a reference to the Next Pos button and stores this as next_button. Line 102 does the same thing for "locate_button" and line 103 does the same thing for insert_button. On line 105, we change the arguments passed to handleOk() to be next_button, locate_button and insert_button. This is because the handleOk() handler needs to be able to access all three buttons.

Line 29 declares and initializes the variable step_count to 0. The variable step_count keeps track of which sort step we are on when animating the sort. Line 30 declares the variable temp. The temp variable is what is being compared to in order to locate the correct insert position. We will store the value for temp each time next_button is clicked. The value of temp will be used to update the Status area from the handler functions.

Line 49 modifies the parameter list for the handleOk() handler to include next_button, locate_button and insert_button. This will allow next_button to be enabled on line 66, and the other two buttons to be disabled on lines 67-68. Line 65 sets step_count to 0, because each time the user click on the Ok button, we need to start at the beginning of the sort_steps array.

Lines 72-88 are the new lines for the handleNextPos() handler. Line 71 sets the parameter list of this handler to be next_button, locate_button and insert_button. These references are needed for lines 81-83 and 85-87, to be able to disable and enable the correct buttons. Line 72 checks to see if in_srt has been constructed. If not, then the function ends execution at that line. Line 73 gets the sort step and saves this as step. For debugging purposes, line 74 prints the JSON.stringified version of step to the console. Line 75 saves step.temp as the private variable temp. This will make temp available inside the other handler functions. Line 76 uses step.start to help determine the correct pointer location. Note that step.start is the position in the array that we start with each time we are finding the correct insertion point. The spacing between each node is (width + 20). The additional width/2 is to get pointer to the middle of the node. This is because xStart is at the left edge of the first node, not the center of that node. Line 77 moves pointer to point at the starting position. Line 78 increments step_count. Line 79 stores the next sort step as next_step. Line 80-88 define a selection statement that checks next_step’s type property. If the type is "locate", then lines 81-83 will disable the next_button and insert_button while enabling locate_button. Otherwise if type is "insert", then lines 85-87 will disable next_button and locate_button, while enable insert_button.

With these changes made, here is a screen showing what the application looks like after clicking the Next Pos button after reading in the input string and hitting Ok:

As you can see pointer points correctly at the second node.

Modifying the handleLocate() handler

Next, let’s work on the handleLocate() handler. As stated earlier, this step will first be used to update the Status area, but that will take care of later on in this lesson. The pointer must be moved one position to the left.After that, we want to increment step_count and look at the next step. This will be handled by a selection statement checks to see if the next step is an "insert". In that case, next_button and locate_button must be disabled and insert_button is enabled.

Here is the next version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      const step = sort_steps[step_count];
      console.log(JSON.stringify(step));
      temp = step.temp;
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
    },

    async handleInsert() {},
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
}

The new lines are 91-105 and 124-126. Let’s start with the changes inside of the init() function. Lines 124-126 make it so that the handlers.handleLocate() handler function is called when clicking on the Locate button. Note that the references to next_button, locate_button and insert_button are passed as arguments.

Lines 91-105 are the changes made to the handleLocate() handler. Line 91 changes the parameter list of this function to include next_button, locate_button and insert_button, as we need access to those references within this function. Line 92 gets the current sort_step and stores it as step. Line 93 is a comment to remind us that we will use step to update the Status area. Line 94 gets the current x1 value of pointer and converts this to a number. Line 95 causes the pointer to move to the left by (width + 20), which is the spacing between nodes. Line 96 increments step_count. Line 97 obtains the next sort step. Lines 98 and 99 are for debugging purposes and just print out the next_step object. Lines 100-104 form a selection statement that checks to see if the next step is an "insert". If the next sort step is an "insert", then lines 101-103 disable next_button and locate_button, and enable insert_button.

We will be able to see the results of the changes made here, after we modify the handleInsert() handler. So, that is what we will do next.

Modifying the handleInsert() handler in index.mjs

The handleInsert() handler is the most involved handler for this application. There is actually a selection statement before we move any of the nodes. This is because if the node is already in position, it will only bounce up and down. So the first selection statement will test to see if the begin and end properties of the sort step are the same or not. If they are the same, the node will just bounce up and down. Otherwise, a for loop to move the SVG objects (nodes) to make space for the node that will be inserted must be run. Since the nodes are being moved, node_array must be manipulated so that the id of the node can be reset to match the index of the node_array. After these operations, a second selection statement will be needed to see if there are still more sort steps to be executed, or if the end of the sort process has been reached.

Here is the new version of index.mjs:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      const step = sort_steps[step_count];
      console.log(JSON.stringify(step));
      temp = step.temp;
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
    },

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 500);
      }
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
}

The new lines are 107-131 and 150-152. Starting from the modifications to the init() function, lines 150-152 set up the click event handler for insert_button. Lines 108-131 are the new lines for the handleInsert() handler. This handler is not yet complete, but it has enough lines to animate the SVG nodes. We will still need to add more code here, but I only put these lines so that the amount of changes would not be too large. Line 107 has been modified so that the parameter list now includes next_button, locate_button and insert_button. Line 108 obtains the current sort step and stores this as step. Lines 109 and 110 store the begin and end value for the elements that need to slide. Line 111 gets the node at the begin position. This is the starting position for the node that will be inserted. That node is stored as ndToRemove, because this is the node that we will want to temporarily remove before sliding over the nodes that need to be moved to the right.

Lines 112-129 define the first selection statement. This selection statement test to see if begin and end are the same. This first case means that the node is already in the correct position for that iteration of the outer for loop. The second case is when begin and end are not equal, so nodes have to be moved. If begin is the same as end, then line 114 is executed to make the node just bounce up and down and stay in place. Otherwise, lines 116-128 will be executed. Lines 116 and 117 obtain the x and y coordinates of where ndToRemove will be temporarily located. This will be just to drop that node straight down. Line 118 gets the node where ndToRemove will be eventually inserted is located at. Lines 119 and 120 get the x and y coordinates, respectively, for that insert position. Getting the coordinates for the insert position must be done before the for loop, because the for loop on line 122-127 will move the nodes. That will make using getNodeById() return the wrong value, because that node will have been moved to the right by one position. Line 121 moves ndToRemove straight down. Line 121 uses await so that this move down completes before the for loop on lines 122-127 starts.

Lines 122-127 is patterned after the inner for loop in the Insertion Sort algorithm. The header line of the for loop on line 122 is equivalent to the for loop header for the Insertion Sort algorithm. Inside that for loop, line 123 gets the node just to the left of position j. Line 124 calculates the x coordinate where that node must be moved to. Note that this is just the current x coordinate added to (width + 20). This is because the nodes are 30 pixels wide and there is a 20 pixel spacing between the nodes. Line 125 gets the y-coordinate of the current position. Since the node will just move horizontally, the y-coordinate will not change. Line 126 uses await to move the node to its new position. This process repeats in that for loop until all the nodes that have to be moved have been slid into position. When we animate the SVG objects, we can really "slide" them to the right, unlike how we have to use copying for an array.

Finally, line 128 moves the temporarily removed node into the insert position.

The following animated gif shows the application working to sort "5,3,9", up until the first "insert" is completed.

Click on Reload gif to replay animation.

The animation appears a little smoother in the application than shown here. This is because of the way the screen capture works. Anyway, you can see the element to be inserted dropping down, then the elements sliding over and then the dropped down element being inserted into the correct position.

Modifying handleInsert() to allow further sorting

At this point, the handleInsert() handler is not complete. If we incremented the sort step and went to the next sort step, we would find that when we try to "insert" again, the wrong SVG objects (nodes) would move. This is because we have moved several of the SVG objects, but did not update node_array to reflect those changes. Remember, we need to move around the elements in node_array, which is separate from moving those nodes on the screen. Moving the nodes on the screen only changes the positions of those nodes. So, we need to make the corresponding changes to node_array and then reset the id for each element in node_array so that the id matches the index of node_array. That is what this next set of changes will accomplish:

index.mjs showing only the handleInsert() handler

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 500);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
      }
    },

The new lines are 122, 130-131 and 133-142. Line 122 uses node_array.splice(begin,1) to remove an array of elements starting at the position marked as begin. The begin position is where the element that is to be inserted starts off being located at. The second argument, 1, causes only 1 element to be removed. Remember that this returns an array, even if only one element is removed.

Line 130 uses node_array.splice(end,0,removedNodes[0]) to add in the element at removedNodes[0] at the position marked by end. Remember that the end position is the location where the node will be inserted. The second argument, 0, means that the deleteCount is 0. In other words, this means that an element will be added instead of removed.

Line 131 calls resetIds() to make all the id values for node_array have the same value as the index of the node within node_array. So, lines 123 and 130-131, make it possible for the rest of the sort animation to proceed correctly.

Lines 133-142 define the second selection statement for this handler. The step_count is checked to see if the end of sort_steps has been reached. If the end has not been reached line 134-137 are executed. Line 134 will increment step_count to continue to the next sort step. Line 135-137 disable locate_button and insert_button, and enable next_button. If the end has been reached, lines 139-141 are executed. Those lines will disable next_button, locate_button and insert_button, as the sort is complete at this point.

The following animated gif shows the application with "5,3,9" as the input string. Note that the Pointer is not being located correctly:

Click on Reload gif to replay animation.

The last few code listings were only partial listings of the index.mjs file. So, if you wanted to have the source code to replace index.mjs entirely, you can use the following code listing:

index.mjs - full listing

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      const step = sort_steps[step_count];
      console.log(JSON.stringify(step));
      temp = step.temp;
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
    },

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 500);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
      }
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
}

At this point, the animation in terms of moving the Pointer and sliding and inserting nodes works. However, to clean the use of the Pointer up, we need to be able to toggle the Pointer between being visible and being hidden. We can start by making the following changes to the pointer.mjs module:

pointer.mjs

export class Pointer {
  constructor(x1, y1, x2, y2, arrowsize, color, markerId) {
    this.svgNS = "http://www.w3.org/2000/svg";

    this.pointerDefs = document.createElementNS(this.svgNS, "defs");
    this.arrow = document.createElementNS(this.svgNS, "marker");
    this.arrow.setAttribute("id", markerId);
    this.arrow.setAttribute("markerWidth", arrowsize);
    this.arrow.setAttribute("markerHeight", arrowsize);
    this.arrow.setAttribute("refX", arrowsize / 2);
    this.arrow.setAttribute("refY", arrowsize / 2);
    this.arrow.setAttribute("orient", "auto");

    const path = document.createElementNS(this.svgNS, "path");
    const d_val = `M 0 0 L ${arrowsize} ${arrowsize / 2} L 0 ${arrowsize} z`;
    path.setAttribute("d", d_val);
    path.setAttribute("fill", color);

    this.arrow.appendChild(path);
    this.pointerDefs.appendChild(this.arrow);

    this.line = document.createElementNS(this.svgNS, "line");
    this.line.setAttribute("x1", x1);
    this.line.setAttribute("y1", y1);
    this.line.setAttribute("x2", x2);
    this.line.setAttribute("y2", y2);
    this.line.setAttribute("stroke", color);
    this.line.setAttribute("stroke-width", 2);
    this.line.setAttribute("marker-end", `url(#${markerId})`);
  }

  draw(svg_area) {
    svg_area.appendChild(this.pointerDefs);
    svg_area.appendChild(this.line);
  }

  moveHorizontal(newX) {
    this.line.setAttribute("x1", newX);
    this.line.setAttribute("x2", newX);
  }

  setVisible(bool) {
    if (bool === true) {
      this.line.setAttribute("visibility", "visible");
    } else {
      this.line.setAttribute("visibility", "hidden");
    }
  }
}

class Line {
  constructor(x1, y1, x2, y2, color) {
    this.svgNS = "http://www.w3.org/2000/svg";
    this.line = document.createElementNS(this.svgNS, "line");
    this.line.setAttribute("x1", x1);
    this.line.setAttribute("y1", y1);
    this.line.setAttribute("x2", x2);
    this.line.setAttribute("y2", y2);
    this.line.setAttribute("stroke", color);
    this.line.setAttribute("stroke-width", 2);
  }
}

export class TwoHeadPointer {
  constructor(
    x1,
    y1,
    x2,
    y2,
    x3,
    y3,
    x4,
    y4,
    arrowsize,
    startcol,
    middlecol,
    endcol,
    startId,
    endId
  ) {
    this.svgNS = "http://www.w3.org/2000/svg";
    this.start = new Pointer(x1, y1, x2, y2, arrowsize, startcol, startId);
    this.middle = new Line(x1, y1, x3, y3, middlecol);
    this.end = new Pointer(x3, y3, x4, y4, arrowsize, endcol, endId);
  }

  draw(svg_area) {
    svg_area.appendChild(this.start.pointerDefs);
    svg_area.appendChild(this.end.pointerDefs);
    svg_area.appendChild(this.start.line);
    svg_area.appendChild(this.middle.line);
    svg_area.appendChild(this.end.line);
  }

  slideEnd(x) {
    console.log(this.end.line);
    this.end.line.setAttribute("x1", x);
    this.end.line.setAttribute("x2", x);
    this.middle.line.setAttribute("x2", x);
  }

  setVisible(bool) {
    if (bool === true) {
      this.start.line.setAttribute("visibility", "visible");
      this.middle.line.setAttribute("visibility", "visible");
      this.end.line.setAttribute("visibility", "visible");
    } else {
      this.start.line.setAttribute("visibility", "hidden");
      this.middle.line.setAttribute("visibility", "hidden");
      this.end.line.setAttribute("visibility", "hidden");
    }
  }
}

The new lines are 42-47. Lines 42-47 define the setVisible() method for the Pointer class. If we pass this method a true value, then the Pointer will be visible. Otherwise, the Pointer will be hidden. We can make some modifications to the index.mjs module to make use of this new method.

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      removeChildren(svg_area);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      pointer.setVisible(false);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      pointer.setVisible(true);
      const step = sort_steps[step_count];
      console.log(JSON.stringify(step));
      temp = step.temp;
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
    },

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 1000);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      pointer.setVisible(false);
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
      }
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
}

The new lines are 51, 66, 75, 132 and 136. Line 51 is something that should have been added much earlier in the coding process. I forgot to put this line in, and only discovered this was missing when I tried to sort a string with 5 numbers and then without reloading the page, tried to sort a string with 3 numbers. That allowed me to see that nodes from the previous sort were still in the svg area. This can sometimes happen when you use CodeSandbox or a Vite environment, as those reload the page each time you save a change to the code. That’s not an excuse for me to have found this so late in coding the program. This is only a warning to be careful when you are using such environments.

Line 66 makes pointer hidden. This is in the handleOk() handler. This makes it so that the initial placement of pointer is hidden as it is not pointing to any node. Previously, it was somewhat distracting to see pointer on the left of all the nodes.

Line 75 makes pointer visible again so that pointer can be seen pointing at the node that we are looking to find the insert position for.

Line 132 is a modification of the instruction to move the node into place after the sliding has completed. The change is that the delay time is set to 1000 ms instead of 500 ms. By adjusting the delay time, I found that 1000 ms looks better than 500 ms for this particular part of the animation. This is a good point to bring up. The delay times used in animations such as we are doing here, are values that you will want to experiment with. When the animation has effect you want, then that is a good value for the delay time. This will involve some trial and error, and you can do this when you have mostly completed the application as one of the finishing touches to the user interface.

Line 136 makes pointer hidden again. This is right after the node has been placed into the insert position. At that point, if there are still sort steps to be executed, the handleNext() handler will make pointer visible again to point at the next node to be inserted.

Here is an animated gif that shows the changes that were just made:

Click on Reload gif to replay animation.

So, now the Pointer points to the correct locations, and is hidden when it does not have to be shown pointing at anything. What remains is to make it so that the Status area and labels are updated.

Updating the Status Area and labels

The Status Area should be updated each time the user clicks on any of the buttons. So, this means that we should update that <textarea> inside all four of the handlers, handleOk(), handleNext(), handleLocate() and handleInsert(). We are using a <textarea> instead of a label to allow for a message that could be more than a single line. Considering that there could be several lines of text, it would be good to be able to format the text. That is, use bold or italics to emphasize certain words. The default HTML <textarea> cannot do this. So, we are going to use a Node.js package called tinymce to make this type of formatting possible.

Installation of the tinymce package

Installation on CodeSandbox

In your CodeSandbox sandbox, you need to edit the package.json file:

package.json

{
  "name": "javascript",
  "version": "1.0.0",
  "description": "The JavaScript template",
  "main": "./src/index.html",
  "scripts": {
    "start": "parcel ./src/index.html",
    "build": "parcel build ./src/index.html"
  },
  "dependencies": {
    "tinymce": "^8.3.1"
  },
  "devDependencies": {
    "parcel": "^2.0.0",
    "babel-eslint": "^10.1.0",
    "eslint": "^7.2.0"
  },
  "keywords": ["css", "javascript"]
}

The new lines are 10-12. These add the tinymce dependency to the project. When you make this change, CodeSandbox will download and install the package. This can take a minute or so to complete.

Installation for Vite

To install tinymce for a Vite project, you need to open a terminal, change into the project directory and run npm install tinymce. Here are the detailed instructions.

to install tinymce for Vite project

$ cd ~/Documents/sort2
$ npm install tinymce

Modifying index.mjs to update the Status Area using tinymce

Here is the first modification to index.mjs that starts to use the tinymce editor:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";
import tinymce from 'tinymce';
import 'tinymce/themes/silver';
import 'tinymce/models/dom';
import "tinymce/icons/default";
import 'tinymce/skins/ui/oxide/skin.min.css';
import 'tinymce/skins/content/default/content.css';
import 'tinymce/skins/content/default/content.js';

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;
  const status_area = document.getElementById("status_area");
  let msg = "";

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      removeChildren(svg_area);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      pointer.setVisible(false);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
      msg = "To go through the sorting process,"
      msg +=" click on the button that is enabled. <br/>";
      msg += "e.g. click on <b>Next Pos</b> to start";
      status_area.value = msg;
      tinymce.activeEditor.load();
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      pointer.setVisible(true);
      const step = sort_steps[step_count];
      console.log(JSON.stringify(step));
      temp = step.temp;
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
    },

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 1000);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      pointer.setVisible(false);
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
      }
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
  tinymce.init({
    selector: 'textarea#status_area',
    toolbar: false,
    license_key: 'gpl',
    menubar: false,
    statusbar: false,
    height: 70,
    max_height: 100,
    min_height: 70
  });
}

The new lines are 4-10, 38-39, 80-84 and 184-193. Lines 4-10 are the import statements needed to use the tinymce editor. Line 38 gets a reference to the <textarea> with an id="status_area" attribute, and stores this reference as status_area. Line 39 declare the private variable msg. This is where we will build up the string to use for our status_area.

Lines 80-84 show the first message placed in status_area using the tinymce editor. Lines 80-82 set the value for msg. Note that this is done over several lines to make it easier to see the full message. Note on line 81, the use of the <br /> element. This is so that the next part of the message will be on the next line. Line 82 uses the <b></b> to enclose Next Pos so that will show up in bold. Line 83 sets the status_area's value property to msg. Finally, on line 84, the instruction:

tinymce.activeEditor.load()

is called. Each time you want status_area to update, you must call that load instruction.

Lines 184-193 initialize the tinymce editor. Line 185 sets the selector property to "textarea#status_area". This means selecting <text id="status_area">. Lines 186, 188 and 189 prevent the toolbar, menubar and statusbar from being displayed. Those are not needed for our application and would just be distractions. Line 187 sets the license_key to 'gpl' as this is not a commercial application. Lines 190-192 control the height of the status area. You could change these to suit your preferences for the application you are creating.

With those changes made, this is the resulting screen shot after clicking Ok in the application.

As you can see, there is a line break after "enabled.", and Next Pos is in bold. This makes for an enhanced user experience, rather than just using a plain <textarea>.

The next version of index.mjs will add in more status messages:

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";
import tinymce from 'tinymce';
import 'tinymce/themes/silver';
import 'tinymce/models/dom';
import "tinymce/icons/default";
import 'tinymce/skins/ui/oxide/skin.min.css';
import 'tinymce/skins/content/default/content.css';
import 'tinymce/skins/content/default/content.js';

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;
  const status_area = document.getElementById("status_area");
  let msg = "";

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function getValueAt(pos) {
    const nd = getNodeById(pos);
    const value = nd.g.childNodes[1].textContent;
    return Number(value);
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      removeChildren(svg_area);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      pointer.setVisible(false);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
      msg = "To go through the sorting process,"
      msg +=" click on the button that is enabled. <br/>";
      msg += "e.g. click on <b>Next Pos</b> to start";
      status_area.value = msg;
      tinymce.activeEditor.load();
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      pointer.setVisible(true);
      const step = sort_steps[step_count];
      const pos = step.start;
      temp = step.temp;
      msg = `Starting at position ${pos}, with temp = ${temp}.`;
      console.log(JSON.stringify(step));
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        const value = getValueAt(pos-1);
        msg += `<br />Since ${temp} is less than ${value},`;
        msg += " pointer will be moving left";
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        msg += `<br />Since ${temp} is already in place,`;
        msg += " an <b>Insert</b> will be done";
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const pos = step.pos;
      msg = `pointer is at pos ${pos}. `;
      if (pos === 0) {
        msg += "<br />Since this is the end of the array, ";
        msg += " this is the <b>Insert</b> position";
      } else {
        const value = getValueAt(pos-1);
        if (temp < value) {
          msg += `<br />Since ${temp} < ${value}, pointer moving left`;
        } else {
          msg += `<br />Since ${temp} is not less than ${value}, `;
          msg += "this is the <b>Insert</b> position";
        }
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
    },

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 1000);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      pointer.setVisible(false);
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "Click on <b>Next Pos</b>";
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "All done";
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
  tinymce.init({
    selector: 'textarea#status_area',
    toolbar: false,
    license_key: 'gpl',
    menubar: false,
    statusbar: false,
    height: 70,
    max_height: 100,
    min_height: 70
  });
}

The new lines are 51-55, 97-99, 106-108, 113-114, 119-120, 126-141, 187, 192 and 194-195. Lines 51-55 define another helper function called getValueAt(). This function is used to get the value of the node at a given position. Line 52 uses the helper function getNodeById() to get the node at that position. Then line 53 obtains the value of that node. Line 54 just converts that string to a number and returns that number. Since that value will be compared to other numbers, the value should be a number (not a string).

Line 97 stores the step.start as pos, which is the starting position. Line 98 updates the value of temp. Each time we click on the Next Pos button, we need to update the value of temp as this is used to locate the insertion point. Line 99 sets msg to display a string that when the value of the variables are plugged in will look like:

Starting at position 2, with temp = 5.

Line 106 gets the value that will be compared to temp. Since we are inside the case of a "locate" being called right after a "next" step, this means that the pointer is going to be moved to the left. So, lines 107 and 108 add that to the end of msg.

Lines 113 and 114 will be executed instead of lines 107 and 108 if the next step is an "insert". If an "insert" is right after a "next", the node must already be in place. So, lines 113 and 114 are added to the end of msg to reflect that case.

Line 119 sets the status_area value to msg, and line 120 refreshes that status area.

Lines 126-141 are the changes made to the handleLocate() handler for updating the status message. Line 126 gets the current pointer position and stores this as pos. Line 127 starts of the value of msg with a string indicating where the pointer is current located at. Lines 128-139 define a selection statement that tests whether or not the value of pos is 0 or not. If pos is 0, then lines 129 and 130 will be used to add to the end of msg to indicate that the pointer is at the end of the array, so that has to be the insert position. If pos is not zero, then lines 132-138 will be executed. Line 132 will get the value using getValueAt() and store the returned number as value. Lines 133-138 form a nested selection statement that tests whether temp < value. If that is true, then line 134 is added to the end of msg. If temp is not less than value, the lines 136 and 137 are used to add to the end of msg. So, if temp < value, the message will end with "Since 4 < 7, pointer moving left". Otherwise, the message will end with "Since 22 is not less than 14, this is the Insert position". Those are just example numbers substituted into those strings.

Lines 140 and 141 update status_area's value and refresh the status textarea.

Lines 187, 192 and 194-195 are inside the handleInsert() handler. So, if the Insert button is clicked, line 187 is executed if there are still more sort steps to be performed. In that case, "Click on Next Pos" is displayed in the status_area. On the other hand, if the sort is finished, line 192 will cause "Add done" to be displayed in the status_area. Lines 194 and 195 just update status_area's value and refresh that status textarea.

This completes the changes to update status_area. The following animated gif goes through a sort of the input string "4,13,1,6,22". It is kind of a long animation, but this is so that you can read the status messages.

Click on Reload gif to replay animation.

Updating locations_label and inserts_label

locations_label - This should be updated each time the Locate button is clicked. This will be used to count the total number of Locate steps that are taken.
inserts_label - This should be updated each time the Insert button is clicked. This will be used to count the total number of Insert steps that are taken.

This is a relatively simple modification to index.mjs.

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";
import tinymce from 'tinymce';
import 'tinymce/themes/silver';
import 'tinymce/models/dom';
import "tinymce/icons/default";
import 'tinymce/skins/ui/oxide/skin.min.css';
import 'tinymce/skins/content/default/content.css';
import 'tinymce/skins/content/default/content.js';

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;
  const status_area = document.getElementById("status_area");
  let msg = "";
  let locates_count = 0;
  let inserts_count = 0;
  const locates_label = document.getElementById("locates_label");
  const inserts_label = document.getElementById("inserts_label");

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function getValueAt(pos) {
    const nd = getNodeById(pos);
    const value = nd.g.childNodes[1].textContent;
    return Number(value);
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      removeChildren(svg_area);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      pointer.setVisible(false);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
      msg = "To go through the sorting process,"
      msg +=" click on the button that is enabled. <br/>";
      msg += "e.g. click on <b>Next Pos</b> to start";
      status_area.value = msg;
      tinymce.activeEditor.load();
      locates_count = 0;
      inserts_count = 0;
      locates_label.textContent = locates_count;
      inserts_label.textContent = inserts_count;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      pointer.setVisible(true);
      const step = sort_steps[step_count];
      const pos = step.start;
      temp = step.temp;
      msg = `Starting at position ${pos}, with temp = ${temp}.`;
      console.log(JSON.stringify(step));
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        const value = getValueAt(pos-1);
        msg += `<br />Since ${temp} is less than ${value},`;
        msg += " pointer will be moving left";
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        msg += `<br />Since ${temp} is already in place,`;
        msg += " an <b>Insert</b> will be done";
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const pos = step.pos;
      msg = `pointer is at pos ${pos}. `;
      if (pos === 0) {
        msg += "<br />Since this is the end of the array, ";
        msg += " this is the <b>Insert</b> position";
      } else {
        const value = getValueAt(pos-1);
        if (temp < value) {
          msg += `<br />Since ${temp} < ${value}, pointer moving left`;
        } else {
          msg += `<br />Since ${temp} is not less than ${value}, `;
          msg += "this is the <b>Insert</b> position";
        }
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
      locates_count++;
      locates_label.textContent = locates_count;
    },

    async handleInsert(next_button, locate_button, insert_button) {
      inserts_count++;
      inserts_label.textContent = inserts_count;
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        await ndToRemove.moveTo(insertX, insertY, 1000);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      pointer.setVisible(false);
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "Click on <b>Next Pos</b>";
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "All done";
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
  tinymce.init({
    selector: 'textarea#status_area',
    toolbar: false,
    license_key: 'gpl',
    menubar: false,
    statusbar: false,
    height: 70,
    max_height: 100,
    min_height: 70
  });
}

The new lines are 40-43, 95-98, 161-162 and 166-167. Lines 40 and 41 declare the locates_count and inserts_count variables and initialize them to 0, respectively. These variables will keep track of the number Locate clicks and Insert clicks, respectively. Line 42 gets a reference to the <label> with an id="locates_label" attribute and stores this as locates_label. Line 43 does the same thing as line 42, except for the inserts_label.

Lines 95 and 96 set locates_count and inserts_count to zero again. This is done each time the user clicks on the Ok button, as this signifies the sort process is starting again. Line 97 updates the locates_label's count with the locates_count value. Line 98 does the same thing as line 97, except for the inserts_label and inserts_count.

Line 161 increments locates_count, and line 162 updates locates_label with that count.

Lines 166 increments inserts_count, and line 167 updates inserts_label with that count.

Actually, counting the number of "locate" and "insert" steps was done to get a measure of how many steps are needed to complete the sort. But, if we want to get a measure of the efficiency of the Insertion Sort, the way we have counted the number of "insert" operations is too naive. In actual computing steps, when an "insert" is called for a node that is already in place, actually this does not result in any copying. Although each "locate" is one assignment of a value, we really should look at how many copies/assignments are taking place. So, we could say that one copy takes place for each "locate", but the number of copies for an "insert" is 0 if the node is already in place and a variable number depending on how far the node must move in order to be inserted. Let’s say that the inserted node has to move two positions over. Then, there are two copies to "slide" the array elements to the right, and then one more copy to put the node into the inserted position. So, we can change the way we count inserts to get a more accurate measure of the efficiency of the sort.

Here is the changes to handleInsert() handler inside of index.mjs to get a more accurate counting. We will just make the inserts_count unchanged if the node is already in place, and the inserts_count is increased by the number of elements sliding, which is begin minus end, plus 1 for the copy to insert the node.

index.mjs showing only the handleInsert() handler

    async handleInsert(next_button, locate_button, insert_button) {
      //inserts_count++;
      //inserts_label.textContent = inserts_count;
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        let insert_copies = (begin - end) + 1;
        inserts_count += insert_copies;
        inserts_label.textContent = inserts_count;
        await ndToRemove.moveTo(insertX, insertY, 1000);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      pointer.setVisible(false);
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "Click on <b>Next Pos</b>";
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "All done";
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },

The new lines are 166-167 and 189-191. Lines 166-167 just comment out the previous lines that updated inserts_count in that too naive of a manner. Line 189 calculates the actual number of copies that the insert operation takes, and stores this as insert_copies. Line 190 adds insert_copies to the existing value for inserts_count. Line 191 updates inserts_label with the inserts_count value.

The full source code for index.mjs is shown next. The above snippet was used to just show the part of index.mjs that had to be modified.

index.mjs

import { Node } from "./node.mjs";
import { Pointer } from "./pointer.mjs";
import { InsertionSorter } from "./insert_sorter.mjs";
import tinymce from 'tinymce';
import 'tinymce/themes/silver';
import 'tinymce/models/dom';
import "tinymce/icons/default";
import 'tinymce/skins/ui/oxide/skin.min.css';
import 'tinymce/skins/content/default/content.css';
import 'tinymce/skins/content/default/content.js';

if (document.readyState === "loading") {
  document.addEventListener("DOMContentLoaded", init);
} else {
  init();
}

function removeChildren(elem) {
  while (elem.childNodes.length > 0) {
    elem.removeChild(elem.childNodes[0]);
  }
}

function createHandlers() {
  // put private variables here
  const numbox = document.getElementById("numbox");
  let in_srt; // reference to InsertionSorter object
  let sort_steps = [];
  let xStart = 30;
  let yStart = 60;
  const width = 30;
  const height = 25;
  let node_array = [];
  const svg_area = document.getElementById("svg_area");
  const pointer = new Pointer(5, 10, 5, 50, 5, "blue");
  let step_count = 0;
  let temp;
  const status_area = document.getElementById("status_area");
  let msg = "";
  let locates_count = 0;
  let inserts_count = 0;
  const locates_label = document.getElementById("locates_label");
  const inserts_label = document.getElementById("inserts_label");

  // helper functions
  function getNodeById(id) {
    for (let i = 0; i < node_array.length; i++) {
      const nd = node_array[i];
      if (Number(nd.g.id) === id) {
        return nd;
      }
    }
  }

  function getValueAt(pos) {
    const nd = getNodeById(pos);
    const value = nd.g.childNodes[1].textContent;
    return Number(value);
  }

  function resetIds() {
    for (let i = 0; i < node_array.length; i++) {
      node_array[i].g.setAttribute("id", i);
    }
  }

  return {
    handleOk(next_button, locate_button, insert_button) {
      in_srt = new InsertionSorter(numbox.value);
      removeChildren(svg_area);
      const originalArray = in_srt.getOriginalArray();
      console.log('originalArray:', originalArray);
      node_array = [];
      for (let i = 0; i < originalArray.length; i++) {
        const num = originalArray[i];
        const nd = new Node(xStart + (i*(width+20)), yStart, width, height, num, i);
        node_array.push(nd);
        nd.draw(svg_area);
      }
      sort_steps = in_srt.getSortSteps();
      for (let step of sort_steps) {
        console.log(step);
      }
      pointer.draw(svg_area);
      pointer.setVisible(false);
      step_count = 0;
      next_button.disabled = false;
      insert_button.disabled = true;
      locate_button.disabled = true;
      msg = "To go through the sorting process,"
      msg +=" click on the button that is enabled. <br/>";
      msg += "e.g. click on <b>Next Pos</b> to start";
      status_area.value = msg;
      tinymce.activeEditor.load();
      locates_count = 0;
      inserts_count = 0;
      locates_label.textContent = locates_count;
      inserts_label.textContent = inserts_count;
    },

    handleNextPos(next_button, locate_button, insert_button) {
      if (!in_srt) { return; } // make sure that in_srt has been constructed
      pointer.setVisible(true);
      const step = sort_steps[step_count];
      const pos = step.start;
      temp = step.temp;
      msg = `Starting at position ${pos}, with temp = ${temp}.`;
      console.log(JSON.stringify(step));
      const x = xStart + step.start*(width + 20) + width/2;
      pointer.moveHorizontal(x);
      step_count++;
      const next_step = sort_steps[step_count];
      if (next_step.type === "locate") {
        const value = getValueAt(pos-1);
        msg += `<br />Since ${temp} is less than ${value},`;
        msg += " pointer will be moving left";
        next_button.disabled = true;
        insert_button.disabled = true;
        locate_button.disabled = false;
      } else if (next_step.type === "insert") {
        msg += `<br />Since ${temp} is already in place,`;
        msg += " an <b>Insert</b> will be done";
        next_button.disabled = true;
        insert_button.disabled = false;
        locate_button.disabled = true;
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },

    handleLocate(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      // update Status area with sort step information
      const pos = step.pos;
      msg = `pointer is at pos ${pos}. `;
      if (pos === 0) {
        msg += "<br />Since this is the end of the array, ";
        msg += " this is the <b>Insert</b> position";
      } else {
        const value = getValueAt(pos-1);
        if (temp < value) {
          msg += `<br />Since ${temp} < ${value}, pointer moving left`;
        } else {
          msg += `<br />Since ${temp} is not less than ${value}, `;
          msg += "this is the <b>Insert</b> position";
        }
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
      const x = Number(pointer.line.getAttribute("x1"));
      pointer.moveHorizontal(x - (width + 20));
      step_count++;
      const next_step = sort_steps[step_count];
      console.log('next_step');
      console.log(JSON.stringify(next_step));
      if (next_step.type === "insert") {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = false;
      }
      locates_count++;
      locates_label.textContent = locates_count;
    },

    async handleInsert(next_button, locate_button, insert_button) {
      const step = sort_steps[step_count];
      const begin = step.begin;
      const end = step.end;
      const ndToRemove = getNodeById(begin);
      if (begin === end) {
        //node already in place
        await ndToRemove.bounce();
      } else {
        const x = Number(ndToRemove.g.getAttribute("data-x"));
        const y = Number(ndToRemove.g.getAttribute("data-y")) + 35;
        const insertNode = getNodeById(end);
        const insertX = Number(insertNode.g.getAttribute("data-x"));
        const insertY = Number(insertNode.g.getAttribute("data-y"));
        await ndToRemove.moveTo(x, y, 500);
        const removedNodes = node_array.splice(begin,1);  // remove 1 element at begin
        for (let j = begin; j > end; j--) {
          const nd = getNodeById(j-1);
          const newX = Number(nd.g.getAttribute("data-x")) + (width + 20);
          const newY = Number(nd.g.getAttribute("data-y"));
          await nd.moveTo(newX, newY, 500);
        }
        let insert_copies = (begin - end) + 1;
        inserts_count += insert_copies;
        inserts_label.textContent = inserts_count;
        await ndToRemove.moveTo(insertX, insertY, 1000);
        node_array.splice(end,0,removedNodes[0]); // add removed node at end position
        resetIds();
      }
      pointer.setVisible(false);
      if (step_count < sort_steps.length - 1) {
        step_count++;
        next_button.disabled = false;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "Click on <b>Next Pos</b>";
      } else {
        next_button.disabled = true;
        locate_button.disabled = true;
        insert_button.disabled = true;
        msg = "All done";
      }
      status_area.value = msg;
      tinymce.activeEditor.load();
    },
  };
}

function init() {
  console.log("init called");
  const handlers = createHandlers();
  const ok_button = document.getElementById("ok_button");
  const next_button = document.getElementById("next_button");
  const locate_button = document.getElementById("locate_button");
  const insert_button = document.getElementById("insert_button");
  ok_button.addEventListener("click", () => {
    handlers.handleOk(next_button, locate_button, insert_button);
  });
  next_button.addEventListener("click", () => {
    handlers.handleNextPos(next_button, locate_button, insert_button);
  });
  locate_button.addEventListener("click", () => {
    handlers.handleLocate(next_button, locate_button, insert_button);
  });
  insert_button.addEventListener("click", () => {
    handlers.handleInsert(next_button, locate_button, insert_button);
  });
  tinymce.init({
    selector: 'textarea#status_area',
    toolbar: false,
    license_key: 'gpl',
    menubar: false,
    statusbar: false,
    height: 70,
    max_height: 100,
    min_height: 70
  });
}

Now the application does what it should. We can run it to demonstrate something about the Insertion sort. Consider running the application with the input string "14,3,22,6,4,19". If you run the application, and sort the resulting array, the following screen shot shows the end result:

Note that it takes 7 "locate" copies and 11 "insert" copies. But, what if the array were partially sorted to begin with like this "3,4,14,6,22,19". Running the application with the same set of numbers but with the array partially sorted, is shown in the following screen shot:

In this case it only takes 2 "locate" copies and 4 "insert" copies. That is quite a reduction. This should help you see why the Insertion Sort is one of the fastest sorts for arrays that are mostly sorted to begin with.

Now, let’s take the worst-case scenario, where the array starts off in reverse sorted order. So, the input string would be "22,19,14,6,4,3". Running the application with this input string, results in the following screen shot:

In this case, it takes 15 "locate" copies and 20 insert copies. That is much worse than the unsorted array. So, this is the worst case scenario.

There is a measure of how sorted an array is that can be determined by the number of inversions the array has. There are other ways to come up with a measure of how sorted an array is. But, what is interesting is that if an array is reverse-sorted, this results in the maximum possible number of inversions. This would be given by n(n-1)/2 for an array of size n. So, if you could count the number of inversions and find it is close to this maximum number, you could tell that the array is reverse sorted or close to being reverse sorted. Then, you could reverse the order of the array, which is a fast operation, and follow that by using Insertion Sort to complete the sort. Although this might be complex and not practical, this gives you an idea why the Timsort uses merge sort combined with Insertion sort to sort arrays. The Timsort algorithm is quite complex but takes advantage of the fact the Insertion sort is very fast on nearly sorted arrays. So, Timsort will identify runs where the elements are sorted or nearly sorted and use Insertion sort on those runs. Then, the merge sort is used to combine those runs. If a run is in reverse order, the order is reversed before the Insertion sort is used. The merge sort by itself is a fast sorting process. But, merge sort takes up twice as much memory as sorts like Insertion sort because the merge sort cannot be done in place. That means you need to make a copies of the original array that amount to using twice the size of memory as the original array. Also, merge sort has basically the same performance irrespective of how sorted the array originally is. But, combining merge sort with Insertion sort allows much faster performance if the original array is nearly sorted, even if it is nearly sorted in reverse-order.

By the way, you could do this type of analysis for the Selection Sort. What you would find that the efficiency of the Selection sort does not depend on how sorted the original array is. So, in that sense, the Insertion Sort is a more interesting sort, as the Insertion sort can perform very well for nearly sorted arrays. And, that can be taken advantage of when combining the Insertion sort with other sorts like merge sort.

Summary

We started off this project by adding the HTML markup to index.html so that we had a prototype that showed the user interface elements that we planned to use. Creating a prototype this way is a good way to start off a project as it forces you to think about what you want your project to do. It also forces you to think about what elements you want to be displayed as part of your user interface. Leaving the user interface planning until you have already done a lot of coding often does not work out well. That is mostly because you have not thought through what you want your application to do. So, as we added more code, we could continue to use our prototype to check if things were working correctly.
We made use of Modules for this project. We created the insert_sorter.msj module to handle the parts of the application that had specifically to do with the Insertion Sort. This included implementing the Insertion Sort algorithm as well as generating the sort steps needed to animate the sort. We also modified the pointer.mjs module to be able to create a pointer used to show the node that is being compared to for each step of the sorting process. We did not make changes to the node.mjs module, but we used it to provide the SVG objects as well as animate those SVG objects that were used to represent the array that we wanted to sort.
As in the previous lessons, we developed an algorithm for the sorting process. This kind of process is not simple, especially if sorting is new to you. So, it is worth developing the algorithm before attempting to write the actual code to do the sorting.
For each section of the lesson, we added descriptions of what needed to be taken care of for that part of index.mjs. This type of description is a very useful form of planning, and is highly recommended for any more complex project. This will help to organize your work. In addition, this makes it easier if you have to take a break from the project as this allows getting started again more quickly.
As with the previous lessons, we used a factory function to protect the private variables needed to respond to the user-generated events. The factory function also allowed avoiding the use of global variables. This pattern of using a factory function for this purpose can be applied to any application that is more complex than a simple cookbook application.
Just as with developing the Selection Sort Demo, we needed to have an array of numbers to apply the sorting method to, and also an array of Node objects to be able to animate the sort. Unlike with the Selection Sort Demo, the manipulation of the array of Node objects was performed using Array.splice() to remove and insert nodes.
We made use of the tinymce module so that we could have a formatted <textarea>. This makes for a status area that is probably more effective for the user. So, this is a consideration if you are creating some sort of text area.
Finally we added and then modified the application to keep track of the number of copies required to do the different parts of the sort. This was done to help you understand that the Insertion sort's performance depends on whether or not the array to be sorted is partially sorted or not. If you are going to go further in programming, this type of analysis is something that will eventually become important.