SamD - maybe an error ??? (1 Viewer)

[iptteacherssuck]

in page125 of ur book, I think the sorting algorithm is wrong in the middle section where you shift the array by one..

one would think...

store the array's current value to a temp variable
then
shift everything by one..overwriting the current value
then assign current value to the comparison value..

instead u,

store the array's current INDEX to a temp variaable then
shift
then you try to assign back the current value to comparison value using

item [current] whih has been overwrited by the shift...

do you nkow what i mean ??

 

[SamD]

I sort of get what you mean, however I think you are misreading the algorithm on page 125.

In brief: (well not so brief now I look at what I've written!)

- There are three nested loops.
- the outside loop is used essentially to get the next unsorted data item, I store it in CurrentDataItem, which I guess in your terms is a temporary variable.
- The next loop is used to progressively examine each data item in the sorted part of the array (the front of the array in this algorithm). This loop needs to iterate the same number of times as there are items in the sorted part of the array. This is what Comparison < CurrentItem together with incrementing Comparison does. The flag called Finish is used to stop the loop when the correct position is found. Note that we are looking for the correct position by starting at the front of the sorted list and moving to its end. If the correct position for the CurrentDataItem is at the end of the sorted part then we need not insert it as it is already there.
- The selection within the second loop is true when the CurrentDataItem needs to be inserted within the sorted list rather than after it. In this case we enter the third loop.
- The third loop moves the items above and including the required position up one place. We start at the end of the sorted list, which firstly overwrites the item being examined (but we've still got it held in CurrentDataItem). The process continues until we've moved the item with index Comparison up one.
- At the end of this shuffling up process we shove the CurrentDataItem into its correct spot in the array, namely Item(Comparison). We've finished with this data item so we set the Finish flag to True and move onto the next data item to sort.

Does this help? Or does it just further confuse the issue?

Have you tried doing a deskcheck with an array of say 10 items?

 

[iptteacherssuck]

hehe

yeah i don't think it works

 

[SamD]

looks correct to me!

can you be more specific?

 

[iptteacherssuck]

here it is...

I think the problem is in the middle section where u make space for item...

this is my middle part in c#

	int currentIndex = currentPosition;
						int currentValue = arrayInt [ currentPosition];
						while (currentIndex >= comparison +1)
						{
							arrayInt[currentIndex] = arrayInt[currentIndex-1];
							currentIndex --;
						}
						arrayInt[comparison] = currentValue;
						finished=true;

It looks like you missed out

int currentValue = arrayInt [ currentPosition];

in your algorithm. you only store the index of the current posision not the value itself..and so when u try to put the value of the current pos tot he comparison position by using iten(currentItem)..the data is actually lost ...cuz it has been overwritten by the shifting...


I hope this make sense..

because i virtually converted ur algorithm into c#, and it didn't work...

anyway..thanks for the reply..You probably taught me more in this forum by expalining the stuff to me than my ipt teacher taught me in 2 yrs....

good work.. .I m just reading ur book.. (sample chp) ...its pretty good..beats fowlers for sure..they don't even have insertion sort..

 

[SamD]

I think you must have missed the line in my original algorithm that appears immediately after the first WHILE:

CurrentDataItem = Item(CurrentItem)

This is where I store the current item to be inserted. As a result the actual data is held in CurrentDataItem and the index of where this data was is CurrentItem.

 

[iptteacherssuck]

hmmm
weird

i can't find that line anywhere

 

[SamD]

I think you must have missed the line in my original algorithm that appears immediately after the first WHILE:

CurrentDataItem = Item(CurrentItem)

This is where I store the current item to be inserted. As a result the actual data is held in CurrentDataItem and the index of where this data was is CurrentItem.

There are various other differences I can see between my algorithm and your code. Nevertheless if you've got it going then I reckon your doing better than 90% of the state!!!!

 

[iptteacherssuck]

Sam,

Its DEFINATELY not in the sample chp ive got..

maybe a misprint? cuz after the first while i have

comparison=1
finish=false

then goes in to another while loop
the if statement
then you store

shuffleitem = currentitem <- which is index value not the value itself

then another while loop

 

[SamD]

I just worked out what it is!!!!

You're too scabby to buy the real book and you've downloaded an unedited sample chapter from the web .

I thought either you or I were going mad for a minute there!!!

 

[iptteacherssuck]

ah yes..

i did mention that b4 tho

I was TRYING TO buy ur book but couldn't find it at dymocks..and u told me u only sell it online...like 1 week ago..

i wasn't sure if the book would arrive quickly enuf..so i decided not to buy it (

 

[SamD]

I'm getting old! (well older at least!!!)

How do u expect me to remember that!!!! lol

send me an email to pedc@pedc.com.au and I'll email you a corrected chapter 4. I remember now, so if you want chapter 9 as well then let me know.

 

[iptteacherssuck]

hehe

yeah sam that will be great!

thanks for that.. I've sent you an email so it will very nice of u if u could send me couple of chapters (EDITED)

thanx

 

[liz]

Hey in the linear search on page 117 in the pseudocode it says
set count to 0
Yet shouldn't you set it to 1 or dosen't it really matter??

 

[SamD]

Depends on the application. It's probably more common for arrays to be indexed from 0 rather than from 1.

 

[saladsurgery]

and while we're here:

all the random number generators (in the multiple choice q's) are screwy... out by one at the higher end of numbers generated, i think...

or am i dumb?

 

[SamD]

Yes you are correct. In the first print of the text my editor decided he understood all about random numbers and changed my original. Unfortunately he made many of them incorrect.

This has been corrected in the second and subsequent print runs of the text and is noted in the Teacher Resource Kit and the multi answers on the web.

Sorry for the stuff up and well done finding it!!!