Velocity Reviews > C++ > Exponential tree implementation

Exponential tree implementation

Alec Taylor
Guest
Posts: n/a

 04-17-2012
I have become obsessed with improving the bounds for integer sorting after reading; Arne Andersson's 1995 paper: "Faster Deterministic Sorting and Searching in Linear Space"[1], Mikkel Thorup's 1998 paper: "Faster deterministic sorting and priority queues in linear space"[2], Yijie Han's 2002paper: "Deterministic sorting in O(n log log n) time and linear space"[3] and Han & Thorup's 2002 paper: "Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space"[4].

Unfortunately when I got down to implementing the "Exponential search tree"data-structure of Andersson I ran into some trouble.

I think I mis-implemented the insert function.

Where did I go wrong? - http://ideone.com/F1T1f

Thanks for all suggestions,

Alec Taylor

[1]: http://citeseerx.ist.psu.edu/viewdoc...10.1.1.55.7109
[2]: http://dl.acm.org/citation.cfm?id=314844
[3]: http://dl.acm.org/citation.cfm?id=975984
[4]: http://dl.acm.org/citation.cfm?id=645413.652131

Alec Taylor
Guest
Posts: n/a

 04-17-2012
Arghh, ended up making a very n00bish mistake;

On Tuesday, April 17, 2012 5:24:38 PM UTC+10, Alec Taylor wrote:
> I have become obsessed with improving the bounds for integer sorting after reading; Arne Andersson's 1995 paper: "Faster Deterministic Sorting and Searching in Linear Space"[1], Mikkel Thorup's 1998 paper: "Faster deterministic sorting and priority queues in linear space"[2], Yijie Han's 2002 paper: "Deterministic sorting in O(n log log n) time and linear space"[3] and Han & Thorup's 2002 paper: "Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space"[4].
>
> Unfortunately when I got down to implementing the "Exponential search tree" data-structure of Andersson I ran into some trouble.
>
> I think I mis-implemented the insert function.
>
> Where did I go wrong? - http://ideone.com/F1T1f
>
> Thanks for all suggestions,
>
> Alec Taylor
>
> [1]: http://citeseerx.ist.psu.edu/viewdoc...10.1.1.55.7109
> [2]: http://dl.acm.org/citation.cfm?id=314844
> [3]: http://dl.acm.org/citation.cfm?id=975984
> [4]: http://dl.acm.org/citation.cfm?id=645413.652131

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Neal Becker Python 5 09-22-2005 01:14 PM diegoandrade@gmail.com C++ 1 02-11-2005 03:18 AM Timothy Fitz Python 4 11-19-2004 02:28 AM Eric Lawrence [MSFT] ASP .Net 3 03-02-2004 10:26 AM Stub C Programming 3 11-12-2003 01:51 PM