#### Archived

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.

## 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 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 listInsert (std::list &mylist, T item){mylist.push_back(item);mylist.sort();}

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

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

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 12
• 21
• 9
• 31
• 16
• ### Forum Statistics

• Total Topics
632618
• Total Posts
3007466
• ### Who's Online (See full list)

There are no registered users currently online

×