Archived

This topic is now archived and is closed to further replies.

Binary insertion sort

This topic is 5870 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How to do it in c/c++? This is Pascal code: procedure BinaryInsertion; var i, j, l, r, m: index; x: item; begin for i := 2 to n do begin x := a; l := 1; r := i - 1; while l <= r do begin m := (l+r) div 2; if x.key < a[m].key then r := m - 1 else l := m + 1; end; for j := i - 1 downto l do a[j+1] := a[j]; a[l]:=x; end end; Alec999

Share this post


Link to post
Share on other sites
It should be very easy to convert code from pascal to c, just change begin to { end to }

for i=start to finish
to
for (int i=start; i

and changle all the := to =
You have to change the function heading also.

Of course if you just want a sorted list its much easier to be lazy and do it the STL way:

list mylist;
...

mylist.push_back(myitem);
mylist.sort(); //operator < must be defined to class item

          
template <class T> listInsert (std::list<T> &mylist, T item)
{
mylist.push_back(item);
mylist.sort();
}



Edited by - invective on November 14, 2001 2:48:07 PM

Share this post


Link to post
Share on other sites
Except you should never, ever, ever sort lists. std::list has a sort member function just because it's impossible to do using std::sort, but it's not recommended. It's the slowest, most painful thing in the world (O(N^2), I believe).

If you want a sorted container, e.g. one that is always sorted, use a std::set or std::multiset.

If you want to sort something once or twice, use a std::vector.

(of course, I don't think the original poster knows about STL and I wouldn't expect him to understand the reasons behind my suggestions, but I couldn't let a "list::sort" be used for an example to a C++ newbie with good conscience.)

Edited by - Stoffel on November 15, 2001 1:23:42 PM

Share this post


Link to post
Share on other sites