Archived

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

Alec999

Binary insertion sort

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