469,160 Members | 2,075 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,160 developers. It's quick & easy.

Insertion Sort using Binary Search

N.
Insertion sort is O(N^2), but I figure I can get it in to O(N log2 N)
if the inside loop of the insertion sort is replaced with a binary
search. However, I'm having some implimentation problems...

void insertsort(int a[], int n)
{
int i, j, index;
for (i=0; i < n; i++)
{
index = a[i];
j=1;
while ((j > 0) && (a[j-1] > index))
{
a[j] = a[j-1];
j = j - 1;
}
a[j] = index;
}
}

The way I figure it, instead of having the inner loop iterate back
through the already sorted array (which takes N-1 in worst-case),
couldn't binary search be used to find the position that the next int
is put in, hence taking the inner loop from some function of N to some
function in log N? Anyone have any details on how to do this?
Jul 22 '05 #1
2 6431
On 26 Jan 2004 13:09:13 -0800, ba*****@hotmail.com (N.) wrote:
Insertion sort is O(N^2), but I figure I can get it in to O(N log2 N)
if the inside loop of the insertion sort is replaced with a binary
search.
<ot>
Each insertion is O(n) and you have O(n) insertions, giving O(n^2).
</ot>

void insertsort(int a[], int n)
{
int i, j, index;
for (i=0; i < n; i++)
First, this loop goes one times too much.

Second, as a matter of good style, use '++i' not 'i++'.
{
index = a[i];
'index' is a very poor name for a value at a given index.
j=1;
while ((j > 0) && (a[j-1] > index))
What's that "j > 0" doing in there?

Why don't you use a 'for'-loop?

{
a[j] = a[j-1];
Here you copy elements upwards in the array. The first element is
going to get duplicated umpteen times.
j = j - 1;
Here you decrement 'j' which you started off at 1. Why?
} a[j] = index;
}
}


Jul 22 '05 #2
N. wrote:
...
The way I figure it, instead of having the inner loop iterate back
through the already sorted array (which takes N-1 in worst-case),
couldn't binary search be used to find the position that the next int
is put in, hence taking the inner loop from some function of N to some
function in log N? Anyone have any details on how to do this?


It is not really about the search. It is about the insertion that follows.

While using binary search in place of direct iteration will improve the
performance of the implementation, the complexity will still remain at
O(N^2) level since the insertion itself requires O(N) time.

--
Best regards,
Andrey Tarasevich

Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Kushal | last post: by
4 posts views Thread by ashu | last post: by
20 posts views Thread by Patrick Guio | last post: by
5 posts views Thread by John N. | last post: by
11 posts views Thread by Am | last post: by
6 posts views Thread by Julia | last post: by
reply views Thread by JosAH | last post: by
9 posts views Thread by python_newbie | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.