473,320 Members | 2,003 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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 6747
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Kushal | last post by:
Hello, I am trying to build a dynamic set/list of data which should be sorted as each element is inserted. The main criteria in this list is the speed, the time it takes to insert a element,...
4
by: ashu | last post by:
can anyone tell me that what is the logic of insertion sort. thank you
20
by: Patrick Guio | last post by:
Dear all, I have some problem with insertion operator together with namespace. I have a header file foo.h containing declaration of classes, typedefs and insertion operators for the typedefs in...
5
by: John N. | last post by:
Hi All, Here I have a linked list each containing a char and is double linked. Then I have a pointer to an item in that list which is the current insertion point. In this funtion, the user...
11
by: Am | last post by:
hi i came to know that microsoft improved the efficiency of quick sort by using a cutoff of 8 elements and continuing with insertion sort then, do anybody have the details about it please...
6
by: Julia | last post by:
I am trying to sort a linked list using insertion sort. I have seen a lot of ways to get around this problem but no time-efficient and space-efficient solution. This is what I have so far: ...
0
by: JosAH | last post by:
Greetings, I was asked to write a Tip Of the Week; so here goes: a lot of topics are started here in this forum (and a lot of other forums too) mentioning a problem about sorting data. ...
1
by: AhmedGY | last post by:
Hi, am trying to build an app that uses the insertion sort method to sort numbers entered in a textbox and display them sorted in a label, so i wrote this inside the sort button click event: ...
9
by: python_newbie | last post by:
I don't know this list is the right place for newbie questions. I try to implement insertion sort in pyhton. At first code there is no problem. But the second one ( i code it in the same pattern i...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.