Carleton University - School of Computer Science Honours Project
Fall 2017
C++ Eytzinger Library
Scarfone Joel
SCS News Image
This project discusses the implementation of a c++ library revolving around the idea of storing array data in an alternate layout as opposed to a sorted array for faster search speeds on large values of n; the eytzinger ordered array. With a faster search speed comes negative side effects of other operations. The focus is to look at different efficiencies and implementations of algorithms revolving around this data structure to minimize the negative side effects. Specifically we look at searching, traversal, and moving in place from sorted order to eytzinger ordered and vice versa; with an emphasis on optimizing the later two. With traversal, the end goal would be to match the speed of traversing a sorted array. Although each iteration was done in constant time, traversing the eytzinger ordered array with the current implementation is about 14 times slower than that of a sorted array. Moving from sorted order to eytzinger order can be done in linear time, with the best implementation being able to handle about 10^9 elements in around four seconds.