ALgorithm problem (1 Viewer)

[Seraph]

take a look at this insertion sort

BEGIN MAINPROGRAM
INITIALISATION
set First to first position
set Last to last position
set PositionOfNext to Last 1
ENDINITIALISATION
WHILE PositionOfNext >= First
set Next to data at PositionOfNext
set Current to PositionOfNext
WHILE (Current < Last ) AND (Next > data at (Current + 1))
increment Current
set data at (Current 1) to data at Current
ENDWHILE
set data at Current to Next
decrement PositionOfNext
ENDWHILE
END MAINPROGRAM

I dont udnerstand this , ive desk checked it and im doing something wrong

here 0 3 5 2 9
When i used these numbers it starts at Pos 4 which is 2 , now its not Greater than 9 so nothing changes there so Then the Numbers 5 and 2 are checked
5 is greater than 2
SO , the data at that position Moves on top of the data at the next position!!!
it overlaps it! , no swap was made just an overlap
how does that work???

 

[SamD]

Yes it does overlap, however this is OK because the data item being inserted has first been stored in Next. This data item is shoved into its correct position after the appropriate shuffle (or lack of shuffle) has happened in the inside loop.

In essence the variable Next is being used as the Temp variable for the swap. This allows the overlap you describe to occur without loss of data.

HTH
Sam

 

[Seraph]

I dont get it , then shouldnt there be an actual Temp Variable that stores the Number???

 

[SamD]

Next really is a temp variable, now look at these lines:

set Next to data at PositionOfNext
Do all the shuffle stuff, which will likely overwrite the data at PositionOfNext
set data at Current to Next

The result being that the data held in the array element with index PositionOfNext is now held in the array element with index Current. It doesn't matter if the original version of this data is overwritten during the shuffle as a copy was retained in the variable Next.

HTH
Sam

 

[Seraph]

nope i still dont understand this

even if the data is retained at next (which i dont see.. ) , how is it shuffled itno place without an appropriate swap algorithm?