Main content
Computer science
Insertion sort pseudocode
Now that you know how to insert a value into a sorted subarray, you can implement insertion sort:
- Call
insertto insert the element that starts at index 1 into the sorted subarray in index 0. - Call
insertto insert the element that starts at index 2 into the sorted subarray in indices 0 through 1. - Call
insertto insert the element that starts at index 3 into the sorted subarray in indices 0 through 2. - …
- Finally, call
insertto insert the element that starts at index n, minus, 1 into the sorted subarray in indices 0 through n, minus, 2.
As a reminder, here's the visualization that steps through the algorithm on a deck of cards:
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Want to join the conversation?
Why do you we have to use "var someFunc = function() {}" rather than "function someFunc() {}" ? The differences between the two are minor and I prefer the latter syntax when possible.(3 votes)
The code inside the code window is working within an environment.
-variables and object which appear to be global within the environment aren't really global in scope, they are just at the scope level that the environment is at
- I suspect that, you can't usefunction foo(){}because this would make the function truly global
i.e. it would be at the level of the window object, which could cause all kinds of problems
- I suspect, the same rationale applies to why variables must be declared usingvarinstead of them automatically being created as globals
So, I believe that the syntax is restricted, because you're stuck in the Matrix, and allowing you to use the restricted syntax would cause the illusion to be shattered.
Hope this makes sense(16 votes)
in the inset function var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
j >= 0 && array[j] > value;
j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
can someone explain to me array[j + 1] = value; this line?
I know array[j + 1] = array[j]; this is sliding all bigger element than the value to its right but should not the small value be inserted at array[j] position? why array[j+1] position??(3 votes)- if you exited the loop you have just failed the check for
j >= 0 && array[j] > value.
There are two cases where this would happen:
1) j is -1, (to the left of the array), in which case value is the smallest element, which you want to be inserted at index 0.
Note that: j + 1 = -1 + 1 = 0
2) j is the index of the largest element that is smaller than value. In which case you want to insert value immediately after it i.e. j+1(8 votes)
I can't understand what happen with the array of learn?
I think it should printArray after sorting: [10, 23, 25, 32]
but it not?var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
j >= 0 && array[j] > value;
j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
var insertionSort = function(array) {
for (var i = 1; i < array.length; i++) {
insert(array, i-1, this.array[i]);
}
};
var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);
var learn = [10, 23, 32, 25];
insertionSort(learn);
//println(learn);
println("Array after sorting: " + learn);
Program.assertEqual(learn, [10, 23, 25, 32]);(3 votes)- You shouldn't need to use
this
When you usethis.arrayit is referring to thevar arraydeclared outside of the function, instead of the local vararraythat was passed in as a parameter the function. Remove thethisand things should work better.(3 votes)
I have written this code and the error message is showing that a function is taking to log to run and it is pointing to the insert function which is pre-written
var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
j >= 0 && array[j] > value;
j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
var insertionSort = function(array) {
for( var i=1; i<array.length ; i++)
{
insert(array,i,array[i]); }
};
var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
println("Array after sorting: " + array);
//Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);(2 votes)
This might be because in the loop, the condition is i < array.length. However, while running the code, array length increases because of the insert function. So, the loop cannot end.(3 votes)
Isn't this more logical :
var insertionSort = function(array) {
for(var i = 0; i < array.length-1; i++) {
insert(array, i , array[i+1]);
}
};
than this :
var insertionSort = function(array) {
for(var i = 1; i < array.length; i++) {
insert(array, i-1 , array[i]);
}
};
why start from i = 1, instead of i = 0?(2 votes)- The 1st element at index 0 is already sorted, so starting at 1 skips it.(2 votes)
- Write an algorithm for a function named finder that recursively goes through a list and returns
the index of the first occurrence of an item of interest. The function takes three parameters: 1. The first
position in the list (or 0) 2. The list we want to iterate over 3. The item we want to find.
If the item is not there in the list and we have iterated over the whole list, then the function should return
0.(2 votes) 
what is the wrong with below code ??
[Edited to include only relevant code]var array = [78, 34, 99, 88, 29, 7, 42];
insertionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [7, 29, 34, 42, 78, 88, 99]);(1 vote)- The code is fine, but you have changed the original array and assert, which is confusing the grader
The original array is:var array = [22, 11, 99, 88, 9, 7, 42];
The original assert is:Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);
Change those two lines back to the original and it should work ok(3 votes)
This sentence doesn't make sense to me. Can someone reword this statement in another way?
Call insert to insert the element that starts at index 1 into the sorted subarray in index 0.(2 votes)- var insertionSort = function(array) {
for(var i = 0; i < array.length-1; i++) {
insert(array, i , array[i+1])(2 votes) 
For the insertion sort function, when I use i = 0, i, and i+1, I get the function is taking to long error.
But when I use i = 1, i-1, and i, I don't get any error.
Though when I println the numbers, everything is the same in both cases. Why is this happening?(2 votes)
