Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Insertion sort counting how many comparisons.  RSS feed

 
Jay Fischer
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey guys, I'm new to coderanch and also java.
I hope this question belongs in this section.

so I wrote a code for insertion sort, and I'm trying to count how many copies/comparisons I make during sorting.

At first, I thought it would be trivial since all the comparisons are made inside the while loop so I added comp++; in the loop.
But just to make sure I'm getting the right answer I came up with a random Array{77,99,44} and did it by hand to see how many copies/comparisons it takes.
The correct answer is 6 Copies and 3 Comparisons.
But I get 6 Copies and 2 Comprisons with my code.
I can't seem to spot where I messed up, could anybody give me some advice?
Thank you in advance.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Call me Jay wrote:The correct answer is 6 Copies and 3 Comparisons.

Says who?

As I recall, insertion sort is extremely good when data are already partially sorted - as yours are. Try them in reverse order and see if you get a different result.

You're also not likely to get an accurate reading from only 3 items. Try 10 and see if your results are as predicted - and try them with some corner cases like reverse order and "almost sorted", along with random arrangements. That'll give you a much better result set to work with.

Winston
 
Jay Fischer
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
Call me Jay wrote:The correct answer is 6 Copies and 3 Comparisons.

Says who?



I did all the processes by hand and it definitely takes 3 comparisons for {77,99,44}.
I'm pretty sure the code for insertion sort is right and properly working. What I'm struggling with is where I put the comp++; to get the right Comparsion number.
 
Stephan van Hulst
Saloon Keeper
Posts: 7806
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The comp variable is only incremented if the comparison evaluates to true. If the comparison evaluates to false, you don't increment the counter, but that doesn't mean the comparison didn't happen.
 
Campbell Ritchie
Marshal
Posts: 55698
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
...and welcome to the Ranch
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!