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[j1] > index))
{
a[j] = a[j1];
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 N1 in worstcase),
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? 2 6751
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[j1] > index))
What's that "j > 0" doing in there?
Why don't you use a 'for'loop?
{ a[j] = a[j1];
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; } }
N. wrote: ... The way I figure it, instead of having the inner loop iterate back through the already sorted array (which takes N1 in worstcase), 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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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,...

by: ashu 
last post by:
can anyone tell me that what is the logic of insertion sort.
thank you

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

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

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

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 timeefficient and
spaceefficient solution. This is what I have so far:
...

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

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

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

by: CloudSolutions 
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...

by: Faith0G 
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

by: isladogs 
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...

by: ryjfgjl 
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...

by: Charles Arthur 
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone

by: aa123db 
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...

by: ryjfgjl 
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and timeconsuming...

by: nemocccc 
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?

by: Hystou 
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
 