Algorithm help.

[Yendall]

This is the algorithm we are given:

Code: [Select]

Begin {FunctionA}
GoAgain <- True
Repeat
GoAgain <- False
iCount <- 0
For iCount in range(0,Size(A))
If iCount < Size(A)-1
If A[iCount]>A[iCount+1]
tempValue <- A[iCount]
A[iCount] <- A[iCount+1]
A[iCount+1] <- tempValue
GoAgain <- True
End If
End if
iCount <- iCount + 1
End For
Until GoAgain is False
Display A
End
We are asked to show the output of FunctionA, when the following data set is:


I don't actually know where to begin with this. What does actually imply?  What would the size of be?

Any help would be awesome

[Lasercookie]

Apologies if there's any mistakes or conceptual errors here (point them out if there are).

The size of an array is the number of elements contained within it. So size(A) = 6.

In terms of an array, the range of an array is the index of it's lower and upper bounds (in this case 0 to 5). I don't think that's what this range() function is doing though (if it was, we'd just give it the array as the input).

So range(0, size(A)) is the same as range(0, 6). My guess is this range function will create a list of some sort with values 0 to 6. This seems to fit with the fact that the code is going iCount in range(0, size(A)). I think if A[6] is ever attempted in this code will be something to keep an eye out for.

Stepping through the algorithm
GoAgain = True
We enter the loop
GoAgain = False
iCount = 0
We enter the for loop. For iCount in range(0,Size(A)). So we're going to have the values iCount = 0, 1, 2, 3, 4, 5, 6 run through the loop.


For the first run through the loop, iCount = 0
if iCount < 5 --> true (so this is how the index issue is dealt with)
If A[0] > A[1] --> 6a > 7b.

We're comparing strings, so it's sorted alphabetically. I used this page to get my head around it http://stackoverflow.com/questions/1863028/string-compare-logic (has simple explanations and also one relatively in depth one).  Playing around with the code too might be good way to check it too.

That MC question from ITA last year might be a good one to look at too: "Characters entered as text data do not have a place value, so the first digit in "17‟ is worth one and not ten. The items listed are sorted according to the first character of each 1, 2, 3, 6."

So when we're comparing strings, we do it character by character.

For example:
"10" == "10" TRUE
"1" < "2" TRUE
"a" < "b" TRUE
"e" < "c" FALSE
"1" < "10" TRUE
"2" < "10" FALSE
"2c" < "2a" FALSE (if the first characters of each are equal, we then go to the next character)
"2c" < "2d" TRUE
"ee" < "ee" FALSE
"ef" < "ee" FALSE
"ef" < "el" TRUE

I don't completely understand what happens if the strings are of different lengths. I think what happens is that the least number of characters are used.

6 > 7 - false (hence the comparison is false and we go to the end of the if statement)

GoAgain = True
iCount is incremented by 1

We then go onto the next pass of the for loop. A has remained the same.
iCount = 1

if iCount < 5 --> true
If A[1] > A[2] --> 7b > 3c

"7" > "3" true, so the if statement will be  evaluated

tempValue = A[iCount] = A[1] = 7b
A[1] = A[2] = 3c
A[2] = tempValue = 7b (the values of A[1] and A[2] are swapped... this looks like the algorithm for some form of the bubblesort then)

GoAgain = True
iCount is incremented by 1
A now looks like

iCount = 2

A[2] > A[3] --> "3c" > "7b"

False
A now looks like

iCount = 3

A[3] > A[4] --> "7b" > "10b"

"7" > "1" is True.

The values of A[3] and A[4] are swapped

A now looks like

iCount = 4

A[4] > A[5] --> "7b" > "1f"

True. Values are swapped.

A now looks like

iCount = 5

If iCount < Size(A)-1

If 5 < 5

5 < 5 will evaluate to false. We go to the end of the if statement. iCount is incremented by 1

iCount = 6

If 6 < 5
false. We go to the end of the if statement. iCount is incremented by 1.

We're now at the end of the for loop.

We now evaluate the loop condition. If GoAgain = false, we end the loop.
GoAgain is currently set to True. So the loop repeats.

A looks like this currently

The array is sorted again.

Going through the algorithm
iCount = 0 SWAP

iCount = 1 SWAP

iCount = 2 SWAP

iCount = 3

iCount = 4 SWAP

iCount = 5 nothing

iCount = 6 nothing


We go through the loop again.

Initially

iCount = 0 SWAP

iCount = 1 SWAP

iCount = 2

iCount = 3

iCount  = 4

iCount = 5, 6 nothing


Loop again GoAgain = false



iCount = 0

all these evaluate to false.

Evaluate the loop condition, GoAgain was never set to True so the loop ends.


The output is

[Yendall]

Thanks heaps man, that's perfect! I guess I just got super confused when it was asking for a range with values such as "10b", I don't whether to read that as 1 or 10 or 10b. When dealing with alphabetical values, do you treat it like:
a = 1
b = 2
c = 3
d = 4
etc. etc.
So you could determine that:
b < a = FALSE
d > a = TRUE
etc.

[golden]

Laseredd you better get 40+ for this subject.

[Lasercookie]

Thanks heaps man, that's perfect! I guess I just got super confused when it was asking for a range with values such as "10b", I don't whether to read that as 1 or 10 or 10b. When dealing with alphabetical values, do you treat it like:
a = 1
b = 2
c = 3
d = 4
etc. etc.
So you could determine that:
b < a = FALSE
d > a = TRUE
etc.

That would work. I just think of it as alphabetical order though. a comes before b etc. Same thing as what you've figured out though.

For "10b", like with all strings you treat it character by character. You'd look at the 1 first, then the 0 and then the b.

I think that http://stackoverflow.com/a/1863137 link is a good one. "In the old days, before Unicode and the like, the ordering on our symbols was just the ordering for the ASCII character codes." is an interesting quote. That'd be a similar idea to what you just said with assigning numbers to each character. In fact, that post at the bottom says exactly what you just stated. Apparently unicode is similar, but more complicated.

Looking at the ASCII character table (http://www.asciitable.com/index/asciifull.gif), it goes roughly numbers, capital letters, lowercase letters.

So "3" < "A" < "a"

A lot of that wikipedia page linked goes over my head though. I'm interested if this is something that varies from language to language too (it seems that this lexographical order seems to be a fairly standard concept though).

And then yeah also that Question 13 from the ITA exam last year is a good VCAA example for sorting strings (feels good to finally know how to do that question properly now). "Text data is sorted alphabetically, not numerically" is the quote from Mark Kelly.

[MJRomeo81]

Ah yes, VITTA SD Exam 2 - Questions 13 & 14.

Laseredd is correct. The algorithm sorts an array into ascending order. As the array passed into FunctionA is an array of strings, “10b” comes before “1f”.

[Yendall]

Ah yes, VITTA SD Exam 2 - Questions 13 & 14.

Laseredd is correct. The algorithm sorts an array into ascending order. As the array passed into FunctionA is an array of strings, “10b” comes before “1f”.

Is that because f > 0 ?

[MJRomeo81]

In the ascii table numbers come before letters.

So we have 10b, and 1f. Let's do a comparison to see what comes first (if sorting by ascending order), character by character.

1 and 1. Equal. Next character

0 and f.  As you correctly pointed out, f > 0

10b comes before 1f

[Yendall]

In the ascii table numbers come before letters.

So we have 10b, and 1f. Let's do a comparison to see what comes first (if sorting by ascending order), character by character.

1 and 1. Equal. Next character

0 and f.  As you correctly pointed out, f > 0

10b comes before 1f

Say you had 10a and 10aa
Which one comes before which? or do they have to be the same length?

[MJRomeo81]

10a and 10aa

1 and 1. Equal.

0 and 0. Equal.

a and a. Equal.

null and a. Null comes before a, so 10a comes before 10aa.

[Yendall]

10a and 10aa

1 and 1. Equal.

0 and 0. Equal.

a and a. Equal.

null and a. Null comes before a, so 10a comes before 10aa.

Okay, so null would essentially come before all other values?

[Lasercookie]

Okay, so null would essentially come before all other values?

From Wikipedia http://en.wikipedia.org/wiki/Lexicographical_order#Ordering_of_sequences_of_various_lengths
"Comparing strings of different lengths can also be modeled as comparing strings of infinite length by right-padding finite strings with blank spaces, if, as usual, the blank space is the least element of the alphabet (or, if it is originally not in the alphabet, adding it as least element)."

It also seems intuitive that an empty string would be less than a non-empty string.

[MJRomeo81]

Yeah.



The red writing is what we're looking for (the characters), and the ascii value under the decimal column. e.g. 'A' is ascii code 65, whereas 'a' is ascii code 97. Null is ascii code 0.

e.g. 10A comes before 10a - and so on.