can you find the bug?

[Jeffrey Stedfast]

Going through some of my old code (currently unemployed so have a lot of
free time ;-)

In the following implementation of Binary Insertion Sort, there is at
least 1 bug (as corner case as it might be; hopefully it's also the only
bug or I might be embarrassed).

This probably won't be much of a challenge to the CLC veterans to find,
but hopefully it will present enough of a puzzle to some subset of this
newsgroup's readers to be somewhat of a challenge (and hopefully in that
challenge, an element of fun).
With all the students asking for the easy way out with their homework
assignments on this newsgroup, I suppose the way to handle this would be
(since I don't have a website any longer...), if you want to check your
answer, feel free to email me requesting the answer and I will respond
(or post here if you believe I'm not trying to get you to do my homework
for me ;-)
Jeff
void
BinaryInsertionSort (int *a, size_t n)
{
size_t hi, lo, m, i;
int tmp;
for (i = 1; i < n; i++) {
lo = 0, hi = i;
m = i >1;

do {
if (a[i] a[m]) {
lo = m + 1;
} else if (a[i] < a[m]) {
hi = m;
} else
break;

m = (hi + lo) >1;
} while (lo < hi);

if (m < i) {
tmp = a[i];
memmove (a + m + 1, a + m, sizeof (type) * (i - m));
a[m] = tmp;
}
}
}

[Barry]

"Jeffrey Stedfast" <st******@comcast.netwrote in message
news:tf******************************@comcast.com. ..

Going through some of my old code (currently unemployed so have a lot of
free time ;-)

In the following implementation of Binary Insertion Sort, there is at
least 1 bug (as corner case as it might be; hopefully it's also the only
bug or I might be embarrassed).

This probably won't be much of a challenge to the CLC veterans to find,
but hopefully it will present enough of a puzzle to some subset of this
newsgroup's readers to be somewhat of a challenge (and hopefully in that
challenge, an element of fun).
With all the students asking for the easy way out with their homework
assignments on this newsgroup, I suppose the way to handle this would be
(since I don't have a website any longer...), if you want to check your
answer, feel free to email me requesting the answer and I will respond
(or post here if you believe I'm not trying to get you to do my homework
for me ;-)
Jeff
void
BinaryInsertionSort (int *a, size_t n)
{
size_t hi, lo, m, i;
int tmp;
for (i = 1; i < n; i++) {
lo = 0, hi = i;
m = i >1;

do {
if (a[i] a[m]) {
lo = m + 1;
} else if (a[i] < a[m]) {
hi = m;
} else
break;

m = (hi + lo) >1;
} while (lo < hi);

if (m < i) {
tmp = a[i];
memmove (a + m + 1, a + m, sizeof (type) * (i - m));
a[m] = tmp;
}
}
}

Not compiling is a pretty big corner case:

error: `type' undeclared (first use in this function)

[Jeffrey Stedfast]

Barry wrote:

"Jeffrey Stedfast" <st******@comcast.netwrote in message
news:tf******************************@comcast.com. ..

>Going through some of my old code (currently unemployed so have a lot of
free time ;-)

In the following implementation of Binary Insertion Sort, there is at
least 1 bug (as corner case as it might be; hopefully it's also the only
bug or I might be embarrassed).

This probably won't be much of a challenge to the CLC veterans to find,
but hopefully it will present enough of a puzzle to some subset of this
newsgroup's readers to be somewhat of a challenge (and hopefully in that
challenge, an element of fun).
With all the students asking for the easy way out with their homework
assignments on this newsgroup, I suppose the way to handle this would be
(since I don't have a website any longer...), if you want to check your
answer, feel free to email me requesting the answer and I will respond
(or post here if you believe I'm not trying to get you to do my homework
for me ;-)
Jeff
void
BinaryInsertionSort (int *a, size_t n)
{
size_t hi, lo, m, i;
int tmp;
for (i = 1; i < n; i++) {
lo = 0, hi = i;
m = i >1;

do {
if (a[i] a[m]) {
lo = m + 1;
} else if (a[i] < a[m]) {
hi = m;
} else
break;

m = (hi + lo) >1;
} while (lo < hi);

if (m < i) {
tmp = a[i];
memmove (a + m + 1, a + m, sizeof (type) * (i - m));
a[m] = tmp;
}
}
}

Not compiling is a pretty big corner case:

error: `type' undeclared (first use in this function)

oops, sorry, change that to 'int'

[Mr.Unknown]

is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??

On Jan 28, 9:33 pm, Jeffrey Stedfast <[e-mail]:

Barry wrote:

"Jeffrey Stedfast" <[e-mail] in message
news:tf******************************@comcast.com. ..

Going through some of my old code (currently unemployed so have a lot of
free time ;-)

In the following implementation of Binary Insertion Sort, there is at
least 1 bug (as corner case as it might be; hopefully it's also the only
bug or I might be embarrassed).

This probably won't be much of a challenge to the CLC veterans to find,
but hopefully it will present enough of a puzzle to some subset of this
newsgroup's readers to be somewhat of a challenge (and hopefully in that
challenge, an element of fun).

With all the students asking for the easy way out with their homework
assignments on this newsgroup, I suppose the way to handle this would be
(since I don't have a website any longer...), if you want to check your
answer, feel free to email me requesting the answer and I will respond
(or post here if you believe I'm not trying to get you to do my homework
for me ;-)

Jeff

void
BinaryInsertionSort (int *a, size_t n)
{
size_t hi, lo, m, i;
int tmp;

for (i = 1; i < n; i++) {
lo = 0, hi = i;
m = i >1;

do {
if (a[i] a[m]) {
lo = m + 1;
} else if (a[i] < a[m]) {
hi = m;
} else
break;

m = (hi + lo) >1;
} while (lo < hi);

if (m < i) {
tmp = a[i];
memmove (a + m + 1, a + m, sizeof (type) * (i - m));
a[m] = tmp;
}
}
}

Not compiling is a pretty big corner case:

error: `type' undeclared (first use in this function)oops, sorry, change that to 'int'- Hide quoted text -- Show quoted text -

[Jeffrey Stedfast]

Mr.Unknown wrote:

is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??

exactly :)

[Default User]

Mr.Unknown wrote:

>
is it about m = (hi + lo) >1;

Please don't top-post. Your replies belong following or interspersed
with properly trimmed quotes. See the majority of other posts in the
newsgroup, or:
<http://www.caliburn.nl/topposting.html>

[Kenny McCormack]

In article <52*************@mid.individual.net>,
Default User <de***********@yahoo.comwrote:

>Mr.Unknown wrote:

>>
is it about m = (hi + lo) >1;

Please don't top-post. Your replies belong following or interspersed
with properly trimmed quotes. See the majority of other posts in the
newsgroup, or:
<http://www.caliburn.nl/topposting.html>

Get a life!

[user923005]

On Jan 29, 10:06 am, Jeffrey Stedfast <[e-mail]:

Mr.Unknown wrote:

is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??exactly :)

If you are using insertion sort on a list so large that size_t is in
danger of overflow, you had better go out for a cup of coffee.
You can use a donkey and go to South America and pick, roast and grind
it yourself.
In short, insertion sort is for small sets.

Testing for the largest (tested/allowed/possible) input would be a
good idea, no matter what sort of algorithm you choose.

IMO-YMMV.

[Richard Heathfield]

user923005 said:

<snip>

If you are using insertion sort on a list so large that size_t is in
danger of overflow, you had better go out for a cup of coffee.

Indeed, since size_t (being an unsigned integer type) is *never* in danger
of overflow.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[user923005]

On Jan 29, 2:08 pm, Richard Heathfield <[e-mail]:

user923005 said:

<snip>

If you are using insertion sort on a list so large that size_t is in
danger of overflow, you had better go out for a cup of coffee.Indeed, since size_t (being an unsigned integer type) is *never* in danger

of overflow.

Allow me to rephrase that:
"If you are using insertion sort on a list so large that size_t is in
danger of modulo reduction, you had better go out for a cup of
coffee."

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Jeffrey Stedfast]

user923005 wrote:

>
On Jan 29, 2:08 pm, Richard Heathfield <[e-mail]:

>user923005 said:

<snip>

>>If you are using insertion sort on a list so large that size_t is in
danger of overflow, you had better go out for a cup of coffee.Indeed, since size_t (being an unsigned integer type) is *never* in danger

of overflow.

Allow me to rephrase that:
"If you are using insertion sort on a list so large that size_t is in
danger of modulo reduction, you had better go out for a cup of
coffee."

....on today's hardware.

anyways, yes, it is unlikely anyone would feed a large enough dataset to
an insertion sort, but it's still a bug that's easy to fix.

Jeff

[pete]

Jeffrey Stedfast wrote:

>
Mr.Unknown wrote:

is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??

exactly :)

m = hi / 2 + lo / 2 + (hi & lo & 1);

--
pete

[user923005]

On Jan 29, 4:19 pm, pete <[e-mail]:

Jeffrey Stedfast wrote:

Mr.Unknown wrote:

is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??

exactly :)

m = hi / 2 + lo / 2 + (hi & lo & 1);

Or you can retain the shift paradigm by
m = hi >1 + lo >1 + (hi & lo & 1);

Of course, a sensible compiler might do that for you.
Since this is C.L.C:
"Assumes 2's complement! {for the &1 bit}"
;-)

[Ben Pfaff]

"user923005" <dc*****@connx.comwrites:

On Jan 29, 4:19 pm, pete <[e-mail]:

>Jeffrey Stedfast wrote:

Mr.Unknown wrote:
is it about m = (hi + lo) >1;
( hi+lo ) might overflow ??

m = hi / 2 + lo / 2 + (hi & lo & 1);

Or you can retain the shift paradigm by
m = hi >1 + lo >1 + (hi & lo & 1);

That expression is going to have very surprising results, given
C's precedence rules.

Of course, a sensible compiler might do that for you.
Since this is C.L.C:
"Assumes 2's complement! {for the &1 bit}"

All the variables in question have unsigned type, so that's an
unnecessary assumption.
--
Just another C hacker.

[CBFalconer]

pete wrote:

Jeffrey Stedfast wrote:

>Mr.Unknown wrote:

>>is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??

exactly :)

m = hi / 2 + lo / 2 + (hi & lo & 1);

which rounds down. You also have available:

roundup: m = hi/2 + lo/2 + ((hi | lo) & 1);
roundvarh: m = hi/2 + lo/2 + (hi & 1);
roundvarl: m = hi/2 + lo/2 + (lo & 1);

The roundvar* will avoid the bias of roundup and roundown.

Just to point out variants on your useful formation. These are
only valid on 2's complement or unsigned variables.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

[Peter Nilsson]

On Jan 30, 1:33 pm, Ben Pfaff <[e-mail]:

"user923005" <[e-mail]:

On Jan 29, 4:19 pm, pete <[e-mail]:

Jeffrey Stedfast wrote:
Mr.Unknown wrote:
is it about m = (hi + lo) >1;
( hi+lo ) might overflow ??

m = hi / 2 + lo / 2 + (hi & lo & 1);

Or you can retain the shift paradigm by
m = hi >1 + lo >1 + (hi & lo & 1);

That expression is going to have very surprising results, given
C's precedence rules.

Of course, a sensible compiler might do that for you.
Since this is C.L.C:
"Assumes 2's complement! {for the &1 bit}"

All the variables in question have unsigned type, so that's an
unnecessary assumption.

If you want robustness with respect to signed indexes, number
representation, C90 division, and rounding towards lo (which
many binary search implementations quietly assume), you can
do...

m = ((lo < 0) ^ (hi < 0))
? (lo + hi) / 2 - ((lo + hi) % 2 < 0)
: lo + (hi - lo) / 2;

Of course, if you know that hi and lo are non-negative, then
you can simplify this to the intuitive:

m = lo + (hi - lo) / 2;

Or, if you absolutely insist...

m = lo + ((hi - lo) >1);

--
Peter

[websnarf]

On Jan 29, 4:19 pm, pete <[e-mail]:

Jeffrey Stedfast wrote:

Mr.Unknown wrote:

is it about m = (hi + lo) >1;

( hi+lo ) might overflow ??

exactly :)

m = hi / 2 + lo / 2 + (hi & lo & 1);

There is a well known alternative in the microprocessor world:

(x + y) = 2*(x & y) + (x ^ y)

So,

m = ((lo ^ hi) >1) + (lo & hi);

--
Paul Hsieh
http://www.pobox.com/~qed/

[Jeffrey Stedfast]

Peter Nilsson wrote:

On Jan 30, 1:33 pm, Ben Pfaff <[e-mail]:

>"user923005" <[e-mail]:

>>On Jan 29, 4:19 pm, pete <[e-mail]:
Jeffrey Stedfast wrote:
Mr.Unknown wrote:
>is it about m = (hi + lo) >1;
>( hi+lo ) might overflow ??
m = hi / 2 + lo / 2 + (hi & lo & 1);
Or you can retain the shift paradigm by
m = hi >1 + lo >1 + (hi & lo & 1);

That expression is going to have very surprising results, given
C's precedence rules.

>>Of course, a sensible compiler might do that for you.
Since this is C.L.C:
"Assumes 2's complement! {for the &1 bit}"

All the variables in question have unsigned type, so that's an
unnecessary assumption.

If you want robustness with respect to signed indexes, number
representation, C90 division, and rounding towards lo (which
many binary search implementations quietly assume), you can
do...

m = ((lo < 0) ^ (hi < 0))
? (lo + hi) / 2 - ((lo + hi) % 2 < 0)
: lo + (hi - lo) / 2;

Of course, if you know that hi and lo are non-negative, then
you can simplify this to the intuitive:

m = lo + (hi - lo) / 2;

Or, if you absolutely insist...

m = lo + ((hi - lo) >1);

this is actually how I fixed it, overall the simplest fix I could think of.

>
--
Peter