You might consider looking up 'binary searches' and adapting that to do the insertion from the start. It is the fastest way to search a table that exists, so is also the fastest method to insert someting. I can't remember the exact definition, but in the 'worst' case, it is something like N/2+1 tests. Of course, designing a binary search and adapting it to do insertions are two different animals. ;) I have tried several times and only got it right once. (unfortunately, I lost the code for it, thus the subsequent failed attempts...) Adapted for the purpose of finding your insertion point you could do away with the need to sort the table at all, since it would then insert directly to the right place. Of course, re-running a sort each time could be done too, since the size of the table is pretty small anyway. Its just an idea.
Umm, the basic idea behind the binary is this:
Table:
0 ----
1 Adam
2 Beth
3 Keith
4 Sam
5 Xavier
Make S = 0, E = 5, T = cint(S + (E - S) / 2 + .5). If you are looking for 'Sam', then:
S=0,E=5,T=3 - test...
'Sam' > 'Keith" S=T, T=cint(3 + (5 - 3) / 2 + .5) - test...
'Sam' = 'Sam' - Exit with T=4
For insertions:
Insert="Aardvark",S=1,E=5,T=3 - test...
'Aardvark' < 'Keith' E=3,T=2 - test...
'Aardvark' < 'Beth' E=2, T=1 - test...
'Aardvark' < 'Adam' E=1, T=0 - Exit
Insert at T + 1
The only difference is that you bail if T=0. In any other case T should be 'insertion point - 1', so you would always insert to the table at T+1, once to correct place was found. I think... I wouldn't bet on it though, I have screwed this up so many times... ;) lol For searches, if you don't find it by the time T=0 or S = E, then it isn't in the table. Though with searches, you don't need to use '0' as a start, that just makes insertion easier, since otherwise you have to have a special rule that says, "if the insertion point is 2, then check the value against what is in 1, just to make sure we didn't mean 'insert at 1'." Which is I think where I continually messed up. |