2007-03-13

insertion sort

 http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm  insertion sortを、C++的に実装した。
namespace hito { template < typename BidirectionalIterator > void insertion_sort( BidirectionalIterator first, BidirectionalIterator last ) { BidirectionalIterator pos = first ; for ( ++pos ; pos != last ; ++pos ) { typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ; BidirectionalIterator iter = pos, sorted_iter = pos ; for (--iter ; iter != first && key < *iter ; --iter, --sorted_iter) { *sorted_iter = *iter ; } if ( key < *iter ) // check first element { *sorted_iter = *iter ; --sorted_iter ; } *sorted_iter = key ; } } template < typename BidirectionalIterator, typename BinaryPredicate > void insertion_sort( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate op ) { BidirectionalIterator pos = first ; for ( ++pos ; pos != last ; ++pos ) { typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ; BidirectionalIterator iter = pos, sorted_iter = pos ; for (--iter ; iter != first && op(key, *iter) ; --iter, --sorted_iter) { *sorted_iter = *iter ; } if ( op(key, *iter) ) // check first element { *sorted_iter = *iter ; --sorted_iter ; } *sorted_iter = key ; } } } // namespace hito
 しかし、これはちょっと汚い。reverse_iteratorを使ってみると、こうなる。
namespace hito { template < typename BidirectionalIterator > void insertion_sort( BidirectionalIterator first, BidirectionalIterator last ) { BidirectionalIterator pos = first ; std::reverse_iterator<BidirectionalIterator> const rend(first) ; for ( ++pos ; pos != last ; ++pos ) { typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ; std::reverse_iterator<BidirectionalIterator> riter(pos), rsorted_iter(pos) ; for ( --rsorted_iter ; riter != rend && key < *riter ; ++riter, ++rsorted_iter) { *rsorted_iter = *riter ; } *rsorted_iter = key ; } } template < typename BidirectionalIterator, typename BinaryPredicate > void insertion_sort( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate op ) { BidirectionalIterator pos = first ; std::reverse_iterator<BidirectionalIterator> const rend(first) ; for ( ++pos ; pos != last ; ++pos ) { typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ; std::reverse_iterator<BidirectionalIterator> riter(pos), rsorted_iter(pos) ; for ( --rsorted_iter ; riter != rend && op(key, *riter) ; ++riter, ++rsorted_iter) { *rsorted_iter = *riter ; } *rsorted_iter = key ; } } } // namespace hito

No comments:

Post a Comment

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.