I have written a program that creates two lists of names, in the first list (unsorted) the names are not alphabetically sorted - I press a button then the names appear in the second list (sorted) in alphabetical order (this is complete and working). Moreover, I have to create a variable called ‘count’ (which I have done), and this variable should count the comparisons???

How do I count the comparisons, or more importantly - what does it mean? A simple explanation would be most welcome please!!.

Thank-you.

So every time you check one item against another you add one to the count.

The forum members are going to need a lot of patience with me on this!?!

Example: if I have two lists and one list is full, if I empty the full list into the other empty list - the ‘count’ variable should count one by one each name/item that moves into the new list?

Is that correct?

jacob_1986 wrote:

The forum members are going to need a lot of patience with me on this!?!

Example: if I have two lists and one list is full, if I empty the full list into the other empty list - the ‘count’ variable should count one by one each name/item that moves into the new list?

Is that correct?

Every comparison doesn't result in a move so that doesn't sound right to me.

I will try again, I think I understand.
Comparison is (n-1) x (n-1) / 2?
Example: 10 items = (10-1) x (10-1) = 81. 81 / 2 = 40.5?

This is obviously an exercise you and others have been given.

When you've compared gone through the list once and found the first one you've done 9 comparisons. How many are you going to compare next time? And so on.

Hey Jacob,

Did you find a solution? I think I've been given a similar problem for my A-Level CS homework Would love you forever if you could share the solution!

Thanks,
Jon

Want a computer science-y answer?

There are basically two ways to determine how many elements in two sorted lists are the same.

The first way is to start with the first item in the first list, then look at all the items in the second list to see if any of them match. If one does, you increase the count. Once you do this, you move to the second item in the first list and once again look through all the items in the second list. You do this for each item in the first list then return the count as your answer. This method works on both sorted and unsorted lists.

The second way is to start at the beginning of each list and keep track of where you are in that list. So start with entry 1 on both lists. If they match, increase the count and move your place in each list to the next item in the list. If they do not match and the item in the first list comes alphabetically or numerically before the item in the second list, you only move your pointer to the place in the first list but keep your pointer to the place in the second list to the same position. If the item in the second list is alphabetically or numerically first, then you move the position of your pointer in the second list up by one and leave the place in the first list where it is. You keep repeating this from the beginning until you reach the end of either list. This method only works on sorted lists.

The first method takes n*m (or generally n^2) number of steps to complete, where n and m are the number of items in the lists. The second approach is linear and takes only n+m steps. Thus it is much, much faster. Sorting the lists takes n*log(n) steps. So sorting and counting takes n*log(n) + (n+m) steps and is still much faster than the first approach.

bustedthumbs wrote:

Want a computer science-y answer?

That's not what they're saying though - they're taking an unsorted list and an empty list and copying the first to the second in the right order. I'm pretty sure that's the case - as is often the case with course work there have been several similar topics recently and I may have the advantage of having seen the other topics.

Using the program below, you need to import a txt file (of names or numbers into the list). You also need to create two variables ‘position’ and ‘comparison_count’. The second block ‘swap’ needs a number output so you can store ‘position’ in it.

The program should count the comparisons of the list i.e. eight names in list = 49 comparisons.

define swap [number1]

define do_swapping_pass
set [position] to [1]
repeat ((length of [ v] :: list) - (1))
if <(item (position) of [list v] :: list) > (item ((position) + (1)) of [list v] :: list)> then
swap(position)
end
change [comparison_count] by (1)
change [position] by (1)
end

when [space] key pressed
set [comparison_count] to [0]
repeat ((length of [list v] :: list) - (1))
do_sawpping_pass
end

So what you have there clearly has two loops, each taking n-1 passes so you get n-1 squared.

But that doesn't look like two lists, just one list being sorted.

In passing, apologies to @bustedthumbs - this seems to be a different exercise to the one I'd looked at elsewhere although very similar.

Jacob, I'm not sure if im just being a bit ditsy, but I can't get that solution to work with my project. 've adapted it slightly to so it uses all the variables youve stated. Only I get 98 instead of 48

Strictly speaking you're doing a bubble sort and after the first pass the largest value will be at the end of the list. On that basis you shouldn't need to compare that value next time round. After the second pass the highest values are in their correct positions so you don't need to look at them.

So the count should still decrease 1 per time which means the number of comparisons required for a list of 10 is 9 + 8 + 7 + … 1. That's the sum of the first n-1 integers which is n*(n-1) / 2.

Obviously this isn't an option if you've been given that custom block and told to use it and perhaps your teacher is leading up to doing it properly!

Thanks, deck, I'm kind of getting it. Just a side note, my teacher has given us free reign find a solution. He wants us to use “21st-century” methods to fix it (his words!) So I'm not cheating haha!

Can I share with you my project so far? And should I create a new thread as I feel like I'm being rude and hijacking Jacobs!

CrackerGirl14 wrote:

Thanks, deck, I'm kind of getting it. Just a side note, my teacher has given us free reign find a solution. He wants us to use “21st-century” methods to fix it (his words!) So I'm not cheating haha!

Can I share with you my project so far? And should I create a new thread as I feel like I'm being rude and hijacking Jacobs!

I would create a new topic.

Only I get 98 instead of 48

How long is the list you have imported?