By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,691 Members | 1,123 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,691 IT Pros & Developers. It's quick & easy.

Insertion Sort using Binary Search

P: n/a
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
Share this Question
Share on Google+
2 Replies


P: n/a
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

P: n/a
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.