Jump to content
  • Advertisement


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


Binary insertion sort

This topic is 6156 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
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.sort(); //operator < must be defined to class item

template <class T> listInsert (std::list<T> &mylist, T item)

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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!