Master the art of using Insertion Sort in javascript with the help of Khan Academy

Question

Master the art of using Insertion Sort in javascript with the help of Khan Academy

Seems like I am almost there with solving this problem, but my code isn't running as expected. Can someone offer some feedback and point out where I went wrong?

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, array.length -1, 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]);

When I use insert(array, array[i], i);, the output is:

Array after sorting: 22,11,12,100,89,10,8,43,5,,4,,1,,

javascript algorithm

Answer 1

Answer №1

Here is another approach to solving the insertion sort problem:


const insertValue = function(arr, index, val) {
    for(let j = index; j >= 0 && arr[j] > val; j--) {
        arr[j + 1] = arr[j];
    }
    arr[j + 1] = val;
};

const performInsertionSort = function(arr) {
    for(let i = 0; i < arr.length-1; i++){
        insertValue(arr, i, arr[i+1]);
    }
};

let numArray = [34, 56, 22, 78, 90, 10];
performInsertionSort(numArray);

Answer 2

Here is another approach to solving the insertion sort problem:


const insertValue = function(arr, index, val) {
    for(let j = index; j >= 0 && arr[j] > val; j--) {
        arr[j + 1] = arr[j];
    }
    arr[j + 1] = val;
};

const performInsertionSort = function(arr) {
    for(let i = 0; i < arr.length-1; i++){
        insertValue(arr, i, arr[i+1]);
    }
};

let numArray = [34, 56, 22, 78, 90, 10];
performInsertionSort(numArray);

Answer 3

Answer №2

It appears there is an issue that needs addressing:

Within the line

insert(array, array.length -1, i);

, it should actually be

insert(array, array.length -1, array[i]);

The mistake made was inserting the array index instead of the value

Additionally, a potential array out-of-bounds error exists in array[j + 1] = array[j]; since j starts from array.length -1. It would be more appropriate to use array[j] = array[j-1]; while ensuring j>0.

One final point: The rightIndex variable should be i for each iteration, not array.length -1.

Updated code snippet :

var insert = function(array, rightIndex, value) {
        for(var j = rightIndex;
                j > 0 && array[j-1] > value;
                j--) {
                array[j] = array[j-1];
            }   
            array[j] = value; 
        };

        var insertionSort = function(array) {
            for(var i = 0; i < array.length; i++){
                insert(array, i, array[i]);
            }

        };

        var array = [22, 11, 99, 88, 9, 7, 42];
        insertionSort(array);

Answer 4

It appears there is an issue that needs addressing:

Within the line

insert(array, array.length -1, i);

, it should actually be

insert(array, array.length -1, array[i]);

The mistake made was inserting the array index instead of the value

Additionally, a potential array out-of-bounds error exists in array[j + 1] = array[j]; since j starts from array.length -1. It would be more appropriate to use array[j] = array[j-1]; while ensuring j>0.

One final point: The rightIndex variable should be i for each iteration, not array.length -1.

Updated code snippet :

var insert = function(array, rightIndex, value) {
        for(var j = rightIndex;
                j > 0 && array[j-1] > value;
                j--) {
                array[j] = array[j-1];
            }   
            array[j] = value; 
        };

        var insertionSort = function(array) {
            for(var i = 0; i < array.length; i++){
                insert(array, i, array[i]);
            }

        };

        var array = [22, 11, 99, 88, 9, 7, 42];
        insertionSort(array);

Answer 5

Answer №3

Insertion sort is a sorting algorithm that involves dividing the initial unsorted array into two parts: the sorted part and the unsorted part. At first, the sorted part consists of just one element (an array with only one element is considered sorted). Elements are then selected one by one from the unsorted part and inserted into the correct position in the sorted part, gradually expanding the sorted part as each element is inserted.

var numbers = [34, 203, 3, 746, 200, 984, 198, 764, 9];

function insertionSort(arr) {
  var len = arr.length;
  for(var i = 1; i < len; ++i) {
    var tmp = arr[i];
    var j = i - 1;
    for(; j >= 0 && arr[j] > tmp; --j) {
      arr[j+1] = arr[j];
    }
    arr[j+1] = tmp;
  }
};

console.log(numbers);
insertionSort(numbers);
console.log(numbers);

Answer 6

Insertion sort is a sorting algorithm that involves dividing the initial unsorted array into two parts: the sorted part and the unsorted part. At first, the sorted part consists of just one element (an array with only one element is considered sorted). Elements are then selected one by one from the unsorted part and inserted into the correct position in the sorted part, gradually expanding the sorted part as each element is inserted.

var numbers = [34, 203, 3, 746, 200, 984, 198, 764, 9];

function insertionSort(arr) {
  var len = arr.length;
  for(var i = 1; i < len; ++i) {
    var tmp = arr[i];
    var j = i - 1;
    for(; j >= 0 && arr[j] > tmp; --j) {
      arr[j+1] = arr[j];
    }
    arr[j+1] = tmp;
  }
};

console.log(numbers);
insertionSort(numbers);
console.log(numbers);

Answer 7

Answer №4

Arriving a bit fashionably late to the event, it seems there are numerous methods to tackle this challenge, yet the golden figure on KA prefers a specific approach. Here is the solution that brought a smile to its face:

function insertValue(array, rightIdx, val) {
 for(let i=rightIdx; i >= 0 && array[i] > val ; i--){
    array[i+1] = array[i];
 }
 array[i+1] = val;
};

Answer 8

Arriving a bit fashionably late to the event, it seems there are numerous methods to tackle this challenge, yet the golden figure on KA prefers a specific approach. Here is the solution that brought a smile to its face:

function insertValue(array, rightIdx, val) {
 for(let i=rightIdx; i >= 0 && array[i] > val ; i--){
    array[i+1] = array[i];
 }
 array[i+1] = val;
};

Master the art of using Insertion Sort in javascript with the help of Khan Academy

Answer №1

Answer №2

Answer №3

Answer №4

Similar questions

Facing compatibility problems with JavaScript and Cascading Style Sheets in Google Chrome?

Is there a way to incorporate jQuery into SharePoint 2010?

Utilize Laravel 8 and Vue Js to dynamically showcase retrieved data in input fields

Exploring the effectiveness of testing Svelte components

Switch to display only when selected

Assigning an identification number to specify the type of Chip

Tips for displaying only a list of folders in elfinder, a jquery file management plugin

Error: The JavaScript function you are trying to use is not defined

Generating an array of objects using Jquery from XML data

Is it possible to manipulate the attribute of an object using Object.defineProperty when a value is passed as a function parameter?

Tips for creating a concise summary of written content

Trouble arises when accessing GET form in php/Ajax

the div background is limited to the exact size of the text, not filling the entire

What is the solution for displaying just a single panel?

Content obscuring dropdown menu

Can you explain the distinction between key and id in a React component?

Clicking on a date in Vue.js Fullcalendar

What are some ways to enhance the functionality of the initComplete feature in Dat

Stop the setTimeout function after redirecting in the controller

Tips for adding a CSS marker to the Videogular timeline at a designated time