insertion sort in python vs javascript

Question

I implemented insertion sort using python and javascript. For some strange reason, the JS code works, and the python code doesn't. Both implementations should do the same thing. I traced over every line of the code, and couldn't find a difference between the two. Take a look and see if you can spot what is different with the python code.

Javascript Code:

function insertionSort(nums) {

  for (let i=0; i<nums.length; i++) {
    const value = nums[i];
    let hole = i;

    while (hole >= 0 && nums[hole-1] > value) {
      nums[hole] = nums[hole-1];
      hole = hole - 1;
    }
    nums[hole] = value;
  }
  return nums;
}


const sorted = insertionSort([5,2,1,3,6,4]);
console.log(sorted);

Python Code:

def insertion_sort(nums):
  for i in range(0,len(nums)):
    value = nums[i]
    hole = i

    while hole >= 0 and nums[hole-1] > value:
      nums[hole] = nums[hole-1]
      hole = hole - 1

    nums[hole] = value
  return nums

sorts = insertion_sort([5,2,1,3,6,4])
print(sorts)

Apparently they don’t do the same thing (because one is reportedly broken). What debugging has been done? Eg. what state is unexpected? — user2864740
– user2864740, Commented Feb 2, 2020 at 19:03

Mark · Accepted Answer · 2020-02-02 19:10:04Z

3

Python and javascript have different ideas about what someList[-1] does.

In your code above you evaluate nums[hole-1]. The way you've written your loop this can be nums[-1] when hole is zero. In the python code this gets the last element of the list. In the javascript code this is undefined. This has a significant effect on what the next part: nums[hole-1] > value means.

In the end you don't need to calculate while hole >= 0 and nums[hole-1] > value when the value of hole is 0, so maybe changing >= to > will be a good option.

answered Feb 2, 2020 at 19:10

Mark

92.6k8 gold badges116 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Amir Over a year ago

ahh makes perfect sense. so when the hole is at 0, no need to execute the loop. and the -1 index for python vs. undefined in javascript makes sense why the output is different. Thanks a bunch @markmeyer!

Ahmad · Accepted Answer · 2020-02-02 21:22:00Z

2

  nums[hole] = nums[hole-1]

If hole == 0, nums[hole-1] becomes nums[-1], which gets the last element of the list. This is not what it does in Javascript.

edited Feb 2, 2020 at 21:22

Ahmad

1,8846 gold badges30 silver badges59 bronze badges

answered Feb 2, 2020 at 19:09

Daniel Solnik

211 bronze badge

Collectives™ on Stack Overflow

insertion sort in python vs javascript

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related