Pancake Sort
Given a list, sort it using this method: reverse(lst, i, j)
, which reverses lst from i to j.
My Solution(C++):
#include <iostream>
#include <vector>
#include <algorithm>
#define INT_MIN -10000
void reverse(std::vector<int> &lst, int i, int j){
std::vector<int>::iterator it = lst.begin();
std::reverse(lst.begin()+i, lst.begin()+j+1);
}
void pancakeSort(std::vector<int> &lst){
int n = lst.size();
int maxElemIndex;
for (int i=0; i<n; i++){
int maxElem = INT_MIN;
for (int j=0; j<n-i; j++){
if (lst[j]>maxElem){
maxElem = lst[j];
maxElemIndex = j;
}
}
reverse(lst, maxElemIndex, n-i-1);
}
}
void test(){
std::vector<int> lst = {6, 7, 9, 8, 2, 5, 3, 4, 1};
std::cout<<"\nOriginal array\n";
for (int n: lst) std::cout << n << " "; std::cout << std::endl;
pancakeSort(lst);
std::cout<<"\nSorted array\n";
for (int n: lst) std::cout << n << " "; std::cout << std::endl;
}
int main(){
test();
return 0;
}