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 > a[m]) {
lo = m + 1;
} else if (a < a[m]) {
hi = m;
} else
break;

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

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

 

[Barry]

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 > a[m]) {
lo = m + 1;
} else if (a < a[m]) {
hi = m;
} else
break;

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

if (m < i) {
tmp = a;
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]

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 > a[m]) {
lo = m + 1;
} else if (a < a[m]) {
hi = m;
} else
break;

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

if (m < i) {
tmp = a;
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 ??

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 > a[m]) {
lo = m + 1;
} else if (a < a[m]) {
hi = m;
} else
break;
m = (hi + lo) >> 1;
} while (lo < hi);
if (m < i) {
tmp = a;
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]

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

( hi+lo ) might overflow ??

exactly

 

[Default User]

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]

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]

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:

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.

 

[user923005]

user923005 said:


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."

 

[Jeffrey Stedfast]

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]

exactly

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

 

[CBFalconer]

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

 

[user923005]

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]

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.

 

[Peter Nilsson]

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


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);

 

[websnarf]

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);

 

[Jeffrey Stedfast]

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.