• Post Reply Bookmark Topic Watch Topic
  • New Topic

Count comparisons and assignments in three sorting algorithms  RSS feed

 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone,

I have three sorting algorithms in which I must count the number of swaps/copies and comparisons. I am meant to only count the swaps and comparisons that involve anything other than indexes as they are too fast to really matter (according to the professor). Could anyone please look over my work and let me know if my counters are in the right position. I keep coming up with swaps/comparisons that don't necessarily match the formulas I'm finding for best/worst case. Makes me think that my counters are somehow out of place or that I don't have enough of them.

Insertion Sort:


Selection Sort:



Quick sort:
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Mike,

Had a change to have a look only at the quick sort at the moment.

Lines:



You have to clarify, what do you call a swap. Actually over here, is just a one "visible" swap. Technically, I do agree that we could state swaps count as you did. In fact, I still think your professor expects as a 1 swap over here.
Please clarify.

 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda,

In the swap method I should have labeled the swaps++ as moves++ because that is a more accurate description of what is going on.
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Stein wrote:In the swap method I should have labeled the swaps++ as moves++ because that is a more accurate description of what is going on.




I'll ask differently.
Assume you have an array:

In order to get sorted array, you need to swap elements with a content 2 and 1.
How many swaps you considering you need to make?

It is important to make it clear, so someone could answer your main question correctly.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just one swap would be needed.
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Stein wrote:Just one swap would be needed.


Good.



Those code lines from your quick sort algorithm does 1 swap. Changing places of numbers 2 and 1.
But you are counting as 3 swaps. So you have to fix it.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Those code lines from your quick sort algorithm does 1 swap. Changing places of numbers 2 and 1.
But you are counting as 3 swaps. So you have to fix it.


Liutauras, I understand completely that this should be considered one swap. However, for my particular project I have to count every assignment (e.g. temp = array[index]) and every single comparison (array[index] < value or something like that). The only assignments and comparisons that I don't count involve indexes. I should only be counting the statements on array elements or elements of the same type such as tmp = array[i]. Trouble is, I'm not quite sure that I spotted or counted all of these operations in my sorting classes.
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Stein wrote:for my particular project I have to count every assignment (e.g. temp = array[index]) and every single comparison (array[index] < value or something like that).

Mike Stein wrote:

Then you should be very carefully when you choose variable names. As it is hell confusing (moves, swaps, compares, comparisons)

Beside that, there are misplaced positions.

Line 10 wrong, should be after curly bracket on line 9. More better, on a separate line for better readability.

1. I would suggest you choose more precise variable names for counting (the same in all three programs).
2. Make bigger gaps between separate tasks, so you could better understand where one task finish, where other starts.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for the suggestion. I see how it is a confusing mess. I have a specific question about the quicksort comparison count. I see that all the operations are occurring in the method that creates the partition. I'm having a hard time deciding where to put the comparison counter for the if statement. Specifically, I have counter for when the condition is true, but I don't know where to put the comparison counter when the condition is false. I tried placing it right outside the if statement, but that causes the comparison to be counted twice. I then tried putting it outside the for loop but that causes the comparison to be counted regardless of the conditions Boolean value.



I can't get how to count the comparisons when the condition is false. Any pointers?
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Probably we over complicating this problem. Or we don't understand this problem at all (please paste the exact requirements over here, so we could exactly understand what they are).
As for me still lots of ambiguities in this problem.

Beside that, how about this idea?

1. for loop number of iterations/compares (scan <= right) is exactly "scan + 1". At the end you could add it to total.
2. instead "compares++" at line 21, move it to line 18. So you could check before, in case when false occurs.

To simplify you could count "for" and "if" compares as "total = scan * 2 + 1"


 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras,

Thank you very much for all of your insight. Can't tell you how awful it is not to have someone to beat ideas back and forth with. So, I talked to the professor and was given a huge hint. I need to have two comparison counts (one for false and one for when the condition is true). Before reading your post, I thought well I can just add the comparison counter right before the if statement! So, you read my mind a bit :-). What I have now is a counter for when true and a counter in the event that what ever is outlined in the if statement is false. Does this make sense?

 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Remove line 22 "comparisons++". It is a duplicate from line 18 (increments in both situations true or false).

You have to understand, that such a task requires a bit creativity.
For loop iterations is equal to if condition checks. So you don't need to separate variables for that.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, okay, I see. Since I need it to count when both true and false it is redundant to have the counter in the if statement! Thanks!
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I still strongly advise you to post exact requirements over here, as the problem is not clear enough.
Of course you will have to solve it yourself, but at least we could point you to a right direction.

I could be wrong about many points, because for me still lots of ambiguities left about requirements.
 
Paul Clapham
Sheriff
Posts: 22827
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Stein wrote:Since I need it to count when both true and false it is redundant to have the counter in the if statement!


No, I don't think that's the right way to think of it. You don't need to increment the number of comparisons when something is true or false. You need to increment the number of comparisons when a comparison takes place.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't need to increment the number of comparisons when something is true or false. You need to increment the number of comparisons when a comparison takes place.


Paul Clapham,

I see. This counting project is so seemingly simple (just count the comparisons and the assignments when they occur). Yet, I am having such a terrible time with it! You are right; my thinking on this is wrong. I am only concerned when a comparison is taking place. That being said, this is what I have come up with for the quicksort:



In all likelihood what I've come up with is most likely wrong, but my inferior logic is telling me that it works! ;-) :-(
 
Paul Clapham
Sheriff
Posts: 22827
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, that looks like the right way to count the number of comparisons to me.
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you follow that logic, then you need counter within the "if" statement.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!