Inserting text into scrolling field

[Newbie4]

Here are the results for 1,000,000 randomly generated 6 character words:

1. Using a Binary Search and inserting the word into the correct position 19 - 164 - 240 millisecs
2. Stepping through the list until its place is found and inserting the word 7 - 187 - 273 millisecs
3. Re-sorting the list every time after adding a word to the end of the list 399 - 384 - 409 millisecs

I did many tests and the results are similar. The results reported above are for inserting the words "bbbbbb" , "llllll" and "zzzzzz" which represent - best, medium, and worst cases

The binary search is across the board faster. It will always be faster. This version I wrote is actually a slow one. It is a function which normally involves a lot of extra overhead. it is also a recursive one that calls itself. So there is a lot of stack overhead and keeping track of each call. And yet, this is still faster!!
The Stepping thru is dependent on the location. The closer to the top, the faster it will be
The re-sorting is the slowest and never the fastest

You are welcome to look at my code and test it yourself. It would be interesting to see the timing differences if an array was used instead of a text field for the list..
-------------------------
Test Method:
1. Create a text entry field for the list of words called "scrollingField"
2. Create a text entry field for the timer called "t"
3. Create 3 buttons for each of the methods and attach the following code to them:

Generating the List:
global newlist
on mouseUp
put empty into newlist
put empty into field "t"
put "abcdefghijklmnopqrstuvwxyz" into abc
repeat with i = 1 to 1000000
put empty into newword
repeat with j = 1 to 6
put char random(26) of abc after newword
end repeat
put newword & cr after newlist
end repeat
sort newlist
put newlist into field "scrollingField"
end mouseUp

--------------------------------------------
Binary Search:
global newword, newList
on mouseUp
ask "word"
put it into newword
put the number of lines in newList into tLines
put the milliseconds into tStart
put binSrc(newword,1,1000000) into tLoc
if tLoc is empty then
put the milliseconds - tStart into field "t"
exit mouseUp
end if
if tLoc < tLines then
put (newword & cr) before line tLoc of newList
else
put (newword & cr) after line (tLoc-1) of newList
end if
put the milliseconds - tStart into field "t"
put newlist into field "scrollingField"
end mouseUp

function binSrc newWord,tmin,tmax
put trunc((tmin + tmax) / 2) into tmid
if (tmin > tmax) then
##answer "not found"
return tmin
end if
if (line tmid of newList = newWord) then
return empty
else
if (line tmid of newList > newWord) then
return binSrc (newWord, tmin, tmid-1)
else
return binSrc (newWord, tmid+1, tmax  )    
end if
end if
end binSrc

-----------------------
Step Thru, then insert:

global newList
on mouseUp
ask "word?"
put it into newword
put 0 into ctr
put the number of lines of newList into tmax
put the milliseconds into tStart 
repeat for each line x in newList
add 1 to ctr
if x > newword then
exit repeat
end if
end repeat
if ctr = tmax then
put newword & return after newList
else
put newword & return before line ctr in newList
end if
put the milliseconds - tStart into field "t"
put newlist into field "scrollingField"
end mouseUp

-----------
Re-sorting the list everytime:

global newList
on mouseUp
ask "word"
put it into newword
put the milliseconds into tStart
put newword after newList
sort lines of newList
put the milliseconds - tStart into field "t"
put newlist into field "scrollingField"
end mouseUp

--------
That's it, have fun

[jacque]

Thanks for taking the time Newbie4, I'll play with it over the weekend. Nice work.