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
BinaryInsertion Sort (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******@comca st.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
BinaryInsertion Sort (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******@comca st.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
BinaryInsertio nSort (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 <stedf...@comca st.netwrote:

Barry wrote:

"Jeffrey Stedfast" <stedf...@comca st.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
BinaryInsertion Sort (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.individua l.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 <stedf...@comca st.netwrote:

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].i nvalidwrote:

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.