algorithm
팬케이크 정렬
수색…
팬케이크 정렬 기본 정보
팬케이크 정렬 (Pancake Sort) 은 주걱의 임의의 지점에 삽입 할 수 있고 그 위에있는 모든 팬케이크를 뒤집을 때 사용할 수있는 크기 순으로 팬케이크의 무질서한 스택을 정렬하는 수학적 문제에 대한 구어체 용어입니다. 팬 케잌 번호는 주어진 팬 케익 수에 필요한 최소 반전 횟수입니다.
가능한 한 적은 수의 비교로 정렬을 시도하는 기존의 정렬 알고리즘과는 달리 가능한 한 적은 역전으로 시퀀스를 정렬하는 것이 목표입니다.
아이디어는 선택 정렬과 비슷한 작업을 수행하는 것입니다. 우리는 최후에 하나씩 최대 요소를 배치하고 현재 배열의 크기를 1 줄입니다.
문제 분석 :
- 팬케이크를 가장 작은 것 (위)에서 가장 큰 것 (아래) 순서로 주문해야하며, 시작 스택은 순서에 관계없이 정렬 될 수 있습니다.
- 전체 스택을 뒤집기 만 수행 할 수 있습니다.
- 특정 팬케이크를 스택의 맨 아래로 넘기려면 먼저 맨 위까지 뒤집어야합니다 (다시 맨 아래로 뒤집습니다).
- 각 팬케이크를 주문하려면 맨 위까지 한 번 올리고 한 번 뒤집 어서 마지막 위치로 내리십시오.
직관적 인 알고리즘 :
가장 큰 순서의 팬케이크를 찾아서 맨 아래로 뒤집습니다 (먼저 스택 맨 위로 가져와야 할 수도 있음).
스택이 주문 될 때까지 1 단계를 반복하십시오.
2 단계 알고리즘이 작동합니다.
팬케이크 정렬 알고리즘의 예 :
보조 공간 : O(1)
시간 복잡도 : O(n^2)
C # 구현
public class PancakeSort
{
private static void SortPancake(int[] input, int n)
{
for (var bottom = n - 1; bottom > 0; bottom--)
{
var index = bottom;
var maxIndex = input[bottom];
int i;
for (i = bottom - 1; i >= 0; i--)
{
if (input[i] > maxIndex)
{
maxIndex = input[i];
index = i;
}
}
if (index == bottom) continue;
var temp = new int[n];
var j = 0;
for (i = bottom; i > index; i--,j++)
{
temp[j] = input[i];
}
for (i = 0; i < index; i++, j++)
{
temp[j] = input[i];
}
if (temp.Length > j) temp[j] = input[index];
for (i = 0; i <= bottom; i++)
{
input[i] = temp[i];
}
}
}
public static int[] Main(int[] input)
{
SortPancake(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow