• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Insertion Sort pseudocode

 
Anna Greene
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can't spot where my java implementation of insertion sort differs from the pseudocode here:
Well, there is one difference in the parameters used by the insert method, which is inconsistent in the pseudocode.
I'm pretty sure it should be calling insert (a,n) instead of (a,i,n);



Here is my attempt at a java implementation, which doesn't actually seem to do anything.
I've kept variable names as in the pseudocode. Might technically be bad practice, but
I think it should make it easier to follow in this particular scenario.


Why am I so interested in this pseudocode when there are simpler java-ready examples of insertion sort on the internet? Simply because this is the code the professor uses, so I should be able to understand it.
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15441
41
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's how you can discover what's wrong:

Add System.out.println(...); statements at strategic places in your code, to print the value of variables at a certain point. Then run the program and look at what is being printed. Try following in the code, line by line, what's happening, until you discover what is going wrong.

You could also run the program in a debugger and step through it line by line, so that you can inspect at each line what is happening and how the values of variables change. But using println(...); statements is an easy and quick way to debug code.
 
Winston Gutkowski
Bartender
Pie
Posts: 10505
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anna Greene wrote:Why am I so interested in this pseudocode when there are simpler java-ready examples of insertion sort on the internet? Simply because this is the code the professor uses, so I should be able to understand it.

So I guess the first question should be: Do you understand it?

I have to admit, I find it a bit confusing. For one thing, it looks like a selection sort to me, not an insertion sort, because the latter doesn't normally have a 'select-min()' function - although the two algorithms are very closely related.

A couple of tips for you, to add to Jesper's great advice:
1. Have a look at the animations in the two links I provided; they may help you to visualise what's going on better.
2. Give your fields and indexes more meaningful names. 'm', 'n' and 'k' may be fine when you're looking at algebra; but they can get mighty confusing when you're trying to decipher code. A few possibilities for you - 'valueToInsert', 'at', 'current', 'sorted' - but you should work them out for yourself from your understanding of the algorithm. Good names can often help you track down errors more quickly, because the logic doesn't make sense in context with the name.

HIH

Winston
 
Anna Greene
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
Anna Greene wrote:Why am I so interested in this pseudocode when there are simpler java-ready examples of insertion sort on the internet? Simply because this is the code the professor uses, so I should be able to understand it.

So I guess the first question should be: Do you understand it?

I have to admit, I find it a bit confusing. For one thing, it looks like a selection sort to me, not an insertion sort, because the latter doesn't normally have a 'select-min()' function - although the two algorithms are very closely related.

A couple of tips for you, to add to Jesper's great advice:
1. Have a look at the animations in the two links I provided; they may help you to visualise what's going on better.
2. Give your fields and indexes more meaningful names. 'm', 'n' and 'k' may be fine when you're looking at algebra; but they can get mighty confusing when you're trying to decipher code. A few possibilities for you - 'valueToInsert', 'at', 'current', 'sorted' - but you should work them out for yourself from your understanding of the algorithm. Good names can often help you track down errors more quickly, because the logic doesn't make sense in context with the name.

HIH

Winston


His selection sort looks like this...

and I was actually able to write a version of this one that works (as far as I can tell).


I've just noticed the typos on the bottom part of the original post, but I'm not getting the option to edit it
 
Winston Gutkowski
Bartender
Pie
Posts: 10505
64
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anna Greene wrote:His selection sort looks like this...

And that makes sense.

Looking at your original post, it would appear that his algorithm does an initial placement of the smallest value in the array in the first position. Strictly speaking, this is not necessary (and possibly incorrect), because:
(a) The first element is trivially sorted.
(b) Insertion sort is supposed to sort elements as they are encountered.
but he may have a reason for this "extra" step.

The way I see insertion sort is, for 0-based indexes:I'm afraid my pseudo-code is hopeless, but see if it makes sense to you with his formula.

HIH

Winston
 
Anna Greene
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
Anna Greene wrote:His selection sort looks like this...

And that makes sense.

Looking at your original post, it would appear that his algorithm does an initial placement of the smallest value in the array in the first position. Strictly speaking, this is not necessary (and possibly incorrect), because:
(a) The first element is trivially sorted.
(b) Insertion sort is supposed to sort elements as they are encountered.
but he may have a reason for this "extra" step.

The way I see insertion sort is, for 0-based indexes:I'm afraid my pseudo-code is hopeless, but see if it makes sense to you with his formula.

HIH

Winston


This is what I've gotten from your pseudocode so far. It doesn't work, but the error is more than likely on my end.


I'll keep trying to change it around a bit.

Thanks
 
Winston Gutkowski
Bartender
Pie
Posts: 10505
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anna Greene wrote:This is what I've gotten from your pseudocode so far. It doesn't work, but the error is more than likely on my end.

I'm afraid it is.

Hint: What are you passing to your swap() method? Now think about what you're supposed to pass.

Also: Note that I said move, not swap. I think I'd be more inclined to call the method shiftRight() although, in this particular case, a method might actually be overkill - but don't get me wrong, it's good that you're thinking about methods.

Winston
 
Anna Greene
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I arrived at this by comparing it with the second pseudocode example on wikipedia, which seems kind of close.
I had to comment out the if condition to get it to work though.



At least this is similar and seems to actually work. Am I on the right track?
 
Winston Gutkowski
Bartender
Pie
Posts: 10505
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just another, very trivial point.

You might make your swap() method a little quicker by avoiding the action in cases where it's not needed, viz:You may also be interested in an old "bit trick" called the XOR swap. I only link it as an example of the sort of things that used to amuse us in the BI (Before Internet) era; I certainly wouldn't advise coding a swap that way these days.

Winston
 
Winston Gutkowski
Bartender
Pie
Posts: 10505
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anna Greene wrote:At least this is similar and seems to actually work. Am I on the right track?

Yes, but I think i should be set to n initially if you're doing it that way.

Also, for your test array: include a value that is negative, or greater than the length of the array (or both). That will highlight your original error.

Winston
 
Winston Gutkowski
Bartender
Pie
Posts: 10505
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anna Greene wrote:At least this is similar and seems to actually work. Am I on the right track?

Another point: You might want to think about translating that code back to a functional spec of the type your prof gave you. My pseudo-code is entirely procedural, whereas his is more analytic. It might also help you work out what his original intent was.

For example: What do you think is the intent of that inner 'while' loop? And how do you think you might "methodise" it in Java?

Functional analysis and programming takes a lot of discipline, and I take my hat off to folks that can do it properly. Unfortunately, I'm not one of them.

HIH

Winston
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic