An analysis of two in-place array rotation algorithms

被引：3

作者：

Skene, CK ^{[1
]}

机构：

[1] Michigan Technol Univ, Dept Comp Sci, Houghton, MI 49931 USA

来源：

COMPUTER JOURNAL | 1997年 / 40卷 / 09期

关键词：

Applications; (APP); -; Theoretical; (THR); Experimental; (EXP);

D O I：

10.1093/comjnl/40.9.541

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a complexity analysis of two STL in-place rotation algorithms. If an array of n elements is rotated to the right Delta positions, the first STL version, which uses forward iterators, uses n-gcd(n, Delta) swaps, while the second version, which uses random access iterators, uses only n+gcd(n, Delta) array element movements. This paper also proves the optimality of the second version. A performance comparison is included.

引用

页码：541 / 546

页数：6