Insertion Sort algorithm (1 Viewer)

[akuchan]

the enhanced algorithm in the sam davis book... i dont really understand what's
CurrentItem = 2
CurrentDataItem = Item(CurrentItem)
how exactly are they related.. is the CurrentItem like the index.. and the CurrentDataItem the value of that index? =/

but what i really dont get is ths shuffle part
If CurrentDataItem < Item(Comparison) THEN
ShuffleItem = CurrentItem
WHILE ShuffleItem > Comparison
Item(ShuffleItem) = Item(ShuffleItem - 1)
Subtract 1 from shuffleItem
ENDWHILE
Item(Comparison) = CurrentDataItem

from what i actually get from that.. if the value of the current data is smaller than the value of the comparison data, then ...shuffleitem = currentitem..

Item(ShuffleItem) = Item(ShuffleItem - 1)
Subtract 1 from shuffleItem

that part i really dont get, whats item(shuffleitem) is that the value of the shuffle item or something, can anyone explain that whole shuffle part =/

 

[akuchan]

>.> if only the software forum was half as active as the maths one lol sigh

 

[live.fast]

If you put up the whole actual algorithm, it'd be easier to follow i think. Right now, I don't know what comparison is originally declared as, or whether there's another loop (which I think there should be..) so better if you put up the whole thing i reckon.

 

[Legham]

Lmao. I think the insertion sort algorithm was the one i got stuck on the other day, and gave up on.. Haven't had another attempt yet

 

[akuchan]

lol sorry, i figured i shouldve put up the whole algorithm -.- yeah theres 3 loops altogether
BEGIN InsertionSort

NumItems = Number of items in list
CurrentItem = 2
WHILE CurrentItem <= NumItems
CurrentDataItem = Item(CurrentItem)
Comparison = 1
Finish = False
WHILE Comparison < CurrentItem AND Finish = False
IF CurrentDataItem < Item(Comparison) THEN
ShuffleItem = CurrentItem
WHILE ShuffleItem > Comparison
Item(shuffleItem) = Item(shuffleItem - 1)
Subtract 1 from ShuffleItem
ENDWHILE
Item(Comparison) = CurrentDataItem
Finish = True
ENDIF
Add 1 to comparison
ENDWHILE
Add 1 to currentItem
ENDWHILE
End InsertionSort

with any insertion sort algorithm i've seen, i can only sort of follow up to the sort then i get lost, since they're all pretty much the same
​

 

[leatham]

this is out my excel book
BEGIN MAIN PROGRAM
set First to 1
set last to 6
set positionOFNExt >= First
next=the array(positionofnext]
current = positionofnext
while (current < last) and (next >
TheArray {Current + 1])
{shuffle sorted part along}
Increment Current
theArray[current -1] = theArray[current]
endwhile
theArrsy[current] = next
decrement poistionOfNext
endwhile
end mainprogram

 

[sophie1989]

Lmao. I think the insertion sort algorithm was the one i got stuck on the other day, and gave up on.. Haven't had another attempt yet

IMM SOOOOOOOOOOOOOOOOOOOOOOOOOO TIIRREEEED

 

[akuchan]

yeh i got excel too lol, but i reckon sam davis one is easier to understand, which i still dont understand, and its much easier to remember it when you do understand it, damn shuffle part :burn:

 

[sunny]

If you have trouble seeing how these sorting algorithms work, you can first try and trace it out on paper. You can also Google the thousands of sorting applets to see how they work.

 

[akuchan]

hmm yeh tracing it out helps heaps, i know exactly how each sort is different and what they do, but with this sort i dont understand
WHILE ShuffleItem > Comparison
Item(shuffleItem) = Item(shuffleItem - 1)
Subtract 1 from ShuffleItem
ENDWHILE
whats (shuffleitem - 1)
and then.. subtract 1 from shuffleitem
its probably really easy but im just not picking up that logic

 

[live.fast]

shuffleitem is just like when you use 'index' - in other words item(shuffleitem) corresponds to an actual array value.
Now the whole point of this -

WHILE ShuffleItem > Comparison
Item(shuffleItem) = Item(shuffleItem - 1)
Subtract 1 from ShuffleItem
ENDWHILE

- well, if the algorithm has reached this part of the stage, then its currently realised that the array value (of say array(X)) that its up to, is actually smaller then say array(N) of the sorted-part of the array. so what its going to do it is that each array from array(X) downwards, takes on the value of the arrayvalue before it, i.e Array(X) takes on the value that array (X-1) carries, and array (X-1) then takes on the value that array(X-2) etc etc until it reaches array(N). In other words (if you think about it) the array values are being shoved up, or to the right, or however you'd like to think of it. But its important to know that the values ARE shuffling, and that's so that by the time you end up at the Item(comparison) [or array(N) as we've been callin it], you've got the array just above it, and itself, holding the same values. At that point, shuffleitem becomes = to comparison. and it falls out of the SHUFFLE loop. This is where this bit ends up handy:

Item(Comparison) = CurrentDataItem
Finish = True

What it does is it uses the fact that the algorithm has previously already stored the value of array(X) into CurrentDataItem. So now, Item(Comparison) (which would be array(N) ) would be replaced by what was originally array(X) [ this is the insertion bit of the sort ].

After that, it finishes, and then starts looking again for a new array(X) [i.e current data item] that is smaller then some value in the sorted part of the array - after which, it will find a new array(N), and have to go through that whole shufflearrayvalues process and finally insert array(N) with array(X)'s value.

If that's too confusing, do a test table, put down all the variables, and have different sections for each While, call them WHILE 1 and WHILE 2, and note the changes to each variable, see what happens.

Probably good to use this set of values:
Array(1) = 13
Array(2) = 9
Array(3) = 7
Aarray(4) = 12

Oh and remember, this particular array that you typed up is actually sorting the array in ASCENDING ORDER from smallest to largest - just so you know what your insertion sort is doing (at least the one from the samuel davis textbook)

 

[akuchan]

ohh ok thanks, i sort of get it, i'll have a closer look when i get back to insertion sort
guess what i noticed, we both do ancient history and software X_X" got them two test on the same day lol SIGH atleast im not alone

 

[bboundy]

good applet showing an insertion sort: http://www.wanginator.de/studium/applets/insertionsort_en.html