Notebook

This is a variation of selection sort, it bring the largest pancake not yet sorted to the top with one flip; take it down to its final position with one more flip; and repeat this process for the remaining pancakes. The algorithm has been discussed in following wiki link: Pancake Sorting The algorithm is visually represented in following link: Pancake Sorting(Visualization) The idea of this sorting is similar to Selection Sort, here taking maximum items one by one and started placing those from last and at the same time reducing the vector size one by one. To place bigger items in order from last using flips two move to their respective positions. Here is the implementation using std::rotate() and std::reverse(). The output: 

This is an effort to implement insertion sort in C++ way using Standard Template Library. The below implementation is for vector of any type. Two STL libraries algorithm has been used. 1. std::lower_bound 2. std::rotate The implementation cross compiler compatible, tested on GNU C++ (5.4.0) and Microsoft C++ (2010). //g++  5.4.0 #include < iostream > #include < algorithm > #include < vector > template< typename T > void insertionSort(std::vector< T > &vec) { typedef typename std::vector< T >::value_type vt; typename std::vector< vt >::iterator itBegin = vec.begin(); typename std::vector< vt >::iterator itEnd = vec.end(); for(typename std::vector< vt >::iterator it = itBegin; it != itEnd; ++it) { typename std::vector ::iterator ins = std::lower_bound(itBegin, it, *it); std::rotate(ins, it, std::next(it)); } } int main() {     int arr[] = {34, 20, 99, 10, 23}; std::vector< int > v(s