tag:blogger.com,1999:blog-203063759820106893.post6085390657348886941..comments2023-03-25T08:30:26.602-04:00Comments on A Moment of Zen: Binary Insertion SortJeffrey Stedfasthttp://www.blogger.com/profile/12271561115384429651noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-203063759820106893.post-53695145839889434422013-06-24T16:31:22.708-04:002013-06-24T16:31:22.708-04:00One thing to keep in mind when porting to javascri...One thing to keep in mind when porting to javascript is that you have to use Math.floor to truncate the floats when division occurs<br /><br />function binaryInsertionSort (a)<br />{<br /> var i, m;<br /> var hi, lo, tmp;<br /> var n = a.length;<br /><br /> for (i = 1; i < n; i++) {<br /> lo = 0, hi = i;<br /> m = Math.floor(i / 2);<br /><br /> do {<br /> if (a[i] > a[m]) {<br /> lo = m + 1;<br /> } else if (a[i] < a[m]) {<br /> hi = m;<br /> } else<br /> break;<br /><br /> m = Math.floor(lo + ((hi - lo) / 2));<br /> } while (lo < hi);<br /> <br /> if (m < i) {<br /> tmp = a[i];<br /> for (j = i - 1; j >= m; j--)<br /> a[j + 1] = a[j];<br /> a[m] = tmp;<br /> }<br /> }<br /> <br /> return a;<br />}Eric Bowdenhttps://www.blogger.com/profile/10061943337009677325noreply@blogger.comtag:blogger.com,1999:blog-203063759820106893.post-86831786399056803362012-12-07T21:48:24.624-05:002012-12-07T21:48:24.624-05:00Terribly sorry to dredge up such an old post, but ...Terribly sorry to dredge up such an old post, but I ported this to javascript today (replacing memmove with the for loop, as per the comments), and it reduced a 10 second sort (using javascript's .sort() method) to easily under a second. Amazing! Props and thanks! I hope you don't mind. I provided a link to this post in the code.Erichttps://www.blogger.com/profile/00678357994045101892noreply@blogger.comtag:blogger.com,1999:blog-203063759820106893.post-53826414005243476232012-10-09T01:57:23.523-04:002012-10-09T01:57:23.523-04:00If binary search works only on sorted arrays , the...If binary search works only on sorted arrays , then how can it be implemented on sorting arrays ?Jaskaranhttps://www.blogger.com/profile/01010514911958155216noreply@blogger.comtag:blogger.com,1999:blog-203063759820106893.post-71918573140428330102011-01-19T13:22:00.100-05:002011-01-19T13:22:00.100-05:00Hi Etalian,
1) The register keyword is just a hin...Hi Etalian,<br /><br />1) The register keyword is just a hint to the compiler to map the variable to a CPU register. It's just an optimization that is not necessary at all.<br /><br />2) sizeof (int) is used to measure how many bytes are in an int on your platform. On really old computers it might be 2. Most computers these days are 4 (if you are on a 32bit OS) or 8 (8 if you are on a 64bit OS).<br /><br />Since you can't really use memmove() in Java, you'll have to use the for-loop from one of the previous implementations. Simply replace the memmove() line with:<br /><br />for (j = i - 1; j >= ins; j--)<br /> a[j + 1] = a[j];Jeffrey Stedfasthttps://www.blogger.com/profile/12271561115384429651noreply@blogger.comtag:blogger.com,1999:blog-203063759820106893.post-60320917358921502832011-01-19T11:06:19.053-05:002011-01-19T11:06:19.053-05:00I'm trying to use your last piece of code to w...I'm trying to use your last piece of code to write my own binary insertion sort; however I'm hitting some snags--new to coding. I'm using Java within Eclipse.<br /><br />1)What do you use "register" for <br />and <br /><br />2)what is sizeOf(int)?--the compiler just yells at me if I leave it that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-203063759820106893.post-39519795533880162542007-03-09T01:42:00.000-05:002007-03-09T01:42:00.000-05:00My apologies, that is due to the behavior of CInt(...My apologies, that is due to the behavior of CInt() in VB, where CInt(4.5) = 4 and CInt(5.5) = 6 because the rounding depends on the integer part been odd (floor) or even (ceiling).<BR/><BR/>Don't use VB.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-203063759820106893.post-44143477991860018332007-03-09T01:25:00.000-05:002007-03-09T01:25:00.000-05:00If the language rounds n.5 as n instead of (n + 1)...If the language rounds n.5 as n instead of (n + 1), then calling the function like below will cause stack overflow because it will be stuck when low = 4 and high = 5.<BR/><BR/>BinarySearch (a, 0, 9, 6);<BR/><BR/>Otherwise, its very concise and told me the importance of grasping the basics. Thanks.Anonymousnoreply@blogger.com