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