Need feedback on solution for sorting problem - insertion sort

I think I solved it correctly and it passes the tests, but I need some feedback, because:

  • I was confused by this one for a while
  • My solution is slightly different than one from guide page
  • FCC test suite for sorting problems allow you to pass the tests, lets say, for selection sort - even if you feed it implementation of bubble sort - you can go to algorithms section of code prep challenges and check it out. There are 5 sorting challenges there, grab just one solution for any of them from guide page - and with it you can pass tests for bunch of sorting challenges.

So I need to make sure that I understood insertion sort correctly and not implemented some other type of sort algo accidentally.

function insertionSort(array) {
  // Only change code below this line
  let copy = array.slice();
  let len = copy.length;
  for (let i = 1; i < len; i++) {   
    for(let j = i; j > 0; j--) {     
      if (copy[j] >= copy[j - 1]) {        
        break;
      }
      else {        
        [copy[j], copy[j - 1]] = [copy[j - 1], copy[j]];
      }
    }    
  }
  return copy;
  // Only change code above this line
}

const testArray1 = [1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92];
const testArray2 = [5, 4, 33, 2, 8];

console.log(insertionSort(testArray1));
console.log(insertionSort(testArray2));

2 quick comments:

Removing the log lines will help others to review more efficiently .

The algorithm may be less than elegant here. My instinct is to advise switching the loops so that the outer loop is the one counting from 0. The resulting code would become easier to read because you could write an if like this

if (copy[j] < copy[i]) {

Instead of like this

1 Like

good point about the logs, thanks, I forgot to clean this up. Now I removed them.

I will try to tinker around this code to improve readabilty, but for me personally when I see this:

it’s readable enough - because here we can see that we are comparing elements which have

  • index j
  • index j - 1

It’s clear that we are comparing two adjacent items of array here.

From notation you suggested:

it’s not so clear - what is connection between copy[j] and copy[i]

:grinning:
You are making me try to recall information I learned in the 90’s ! (I’m too old for that!)

So right now your code resorts to a lot of j-1 statements
This is less elegant than the suggested method for 2 reasons as I recall:

1- your code is longer overall without improving readability
2- every time you have to write j-1 you are introducing a “reason to fail”. Something as simple as a typo can occur each time you have to write it. For longer algorithms this may also start to look ugly.

I hope that satisfies your request for review. As well, you can always look up insertion sort pseudocode in CS50X or any other freely available university-level computer science course to review how they structure their loops. (Perhaps you will find my review to be less relevant as you look at more code)

1 Like

Sorry about that, that wasn’t my intention :slightly_smiling_face:

ok, this can be solved by declaring some variables with some decent names
under this line

for(let j = i; j > 0; j--) {

I can say that

let [j, j - 1] = [current, previous]

Names for variables are debatable. But there will be no more j - 1 in the code.

And to make whole stuff little bit shorter I also can replace if...else block with ternary operator I think.

Another option would be to follow your suggestion of course.

Thanks for that, I will try to take a look at those.

But first I need to deal with quick sort - there is some recursion which is bothering me :upside_down_face: But that’s a story for another thread, maybe.

1 Like

I understand your instinctive thought here but it will not result in more elegant code unfortunately. (It may actually highlight to an interviewer your inexperience as simple for loops should rely on the i/j only, I would prefer your first solution over that!)

1 Like

Ok, that’s useful hint. I’ve never run into situations where some variables like that can be considered bad practice

I think if you do a lot of code reviews you start to get an instinct for what is expected. Try to volunteer to review code for others and you will see what you hate, and what you like quickly.
But again, take what I say with some dash of salt as I mentioned, what I know comes from a long time ago and may no longer be the norm (and we circle back again to reviewing code online to find out if my review is any good)…

1 Like

Oh, i am getting there - I am participating in some open source and reviewing bunch of stuff.

Maybe. But I have a suspicion that there is more than one norm out there.
And your review was useful and made me think about stuff, even if you consider some of your knowledge outdated. So thanks again!

1 Like

Note - This isn’t a Javascript brace style. It’s a bit uncommon of of C++ brace style.

I’m not sure I understand the reason for splitting out the len into a separate variable?

I remember our discussion couple of months ago:
here goes a link
After your explanation I thought that it’s better to use just variables for loop conditions - did I misunderstand something back then?

Ah. The Pow computation is expensive. Array length is basically free.

1 Like

Thanks for clarification. Then I can get rid of len variable of course

1 Like