Binary insertion sort
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
It should be very easy to convert code from pascal to c, just change begin to { end to }
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:
Edited by - invective on November 14, 2001 2:48:07 PM
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
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement