Pancake sort

팬케이크 정렬은 고전적이고 우스꽝스런 정렬 알고리즘 중 하나다.
뒤집으면서 정렬을 해나가는게 팬케이크 뒤집는거같다고 이름이 이렇게 붙었다.

시간복잡도는 O(N^2)이라 별로 쓸모는 없다.

selection sort와 원리는 비슷하다.

1. 시작:맨끝 범위에서 탄 팬케이크(가장 큰 값)를 찾는다.
2. 시작 범위부터 탄 부분까지를 뒤집는다. 이 때 탄 부분이 자연히 맨 앞으로 간다.
3. 탄 부분에서 맨 끝까지를 범위로 잡아서 또 뒤집는다. 탄 부분이 자연히 맨 뒤로 간다.
4. 시작:맨끝-1 범위에서 탄 팬 케이크를 찾는다.
5. ... 이 과정을 반복하면 가장 큰 값부터 맨 끝에 차곡차곡 쌓이며 끝내는 정렬된 결과가 완성된다.

막 엄청 빠른것도 아니고 뒤집는 연산이 너무 많아서 비효율적인 편이다. 굳이 쓰려들 필요는 없다.

아래는 Rust로 작성된 구현례다.
https://github.com/myyrakle/buldak/blob/main/src/lib/pancake.rs

https://www.geeksforgeeks.org/pancake-sorting/
https://en.wikipedia.org/wiki/Pancake_sorting