JavaScript implementation of insertion sort

Question

I just started reading Introduction to Algorithms and the first algorithm introduced is the insertion sort.

Even though the sort seems to work, I thought I'd ask for feedback right at the start since this is a really new topic to me.

This is the JS implementation I came up with based on the pseudo code:

function insertionSort(arr) {
 for (let j = 1; j < arr.length; j++) {
 let key = arr[j]
 let i = j - 1
 while (i >= 0 && key < arr[i]) {
 i--
 }
 arr.splice(i + 1, 0, key)
 arr.splice(j + 1, 1)
 console.log(arr)
 }
}
const arr = [0, 12, 55, 0, 33333, 5, 1, 7, 2, 3, 3]
insertionSort(arr)

• trognanders: What is the runtime of arr.splice?
• tadadadadi: @trognanders I don't know... Apart from this, I guess using built in functions kind of defeats the purpose of studying algorithms.
• KIKO Software: One way of looking a arrays is that they have keys and values. I'm sure you're familiar with this. Why then do you have a line where the name of an array value is "key"? This line: let key = arr[j]. Should this not be: let value = arr[j];?
• le3th4x0rbot: @KIKOSoftware The pseudocode in the book uses the name key, so it might not be that misguided.
• KIKO Software: @trognanders Good point. I can understand why they chose it, it's the thing that gets moved, they "insert the key", but I still think it is an unfortunate choice.

Answer 1

What you implemented is good, you can test your implementation thinking all the different inputs you can have:

1. Array is empty [ ]
2. Array is already sorted [1,2] or [1,2,3]
3. Array is not sorted [2,1] or [2,1,3]

I have also red the book for school and I can you suggest to not use built in function (it's not the goal of algorithms to learn how to use built in function but how to implement an efficient way to solve a problem. You can simple swap elements with a temporary variable although I think splice() is a in place function.

Answer 2

I just started reading Introduction to Algorithms

Do you mean the popular textbook from MIT Press? In a course taught using this book, it would likely not be acceptable to use other library functions like Array.prototype.splice. Here it glosses over a significant part of insertion sort, which is making space for the next value in the already sorted half of the array. It hides what might be an essential factor in runtime analysis.

In the book pseudocode, it shifts the numbers in the while loop using the assignment A[i + 1] = A[i]. That is more standard array usage and should work just fine in JS.

Pragmatically, using JS arrays for analysis of algorithms is problematic because they can quietly increase in size more like an ArrayList in Java than a regular array. The usage of splice in this code causes the array to change size from n to n+1, then back to n, which is not necessarily trivial at runtime.

I thought I'd ask for feedback right at the start since this is a really new topic to me.

The courses based on this book are often not very heavy on coding, focusing more on reasoning and proofs. As I recall, the book exercises do not feature programming. For hands-on experience implementing algorithms, there may be better books.

In the CS program that I attended, there was an earlier class that used a book like Data Structures and Algorithms in Java by Goodrich and Tamassia which focused heavily on implementation.

• KIKO Software: Here's a link to the pseudo code, so we can all see what this is about.