pivoting 상세설명

 

정렬알고리즘

`pivoting` 함수는 퀵소트의 파티셔닝 개념을 스택 정렬에 적용한 것입니다. 이 함수의 주요 목적은 스택 A의 요소들을 세 그룹으로 나누는 것입니다. 상세한 설명은 다음과 같습니다:

1. 피벗 설정:
   - `p1 = stacks->max_size / 3`
   - `p2 = (stacks->max_size / 3) * 2`
   이 두 값을 기준으로 요소들을 세 그룹으로 나눕니다.

2. 분류 과정:
   - val < p1: 가장 작은 그룹. 스택 B의 아래쪽으로 이동.
   - p1 <= val < p2: 중간 그룹. 스택 B의 위쪽으로 이동.
   - val >= p2: 가장 큰 그룹. 스택 A에 남음.

3. 동작 방식:
   - 스택 A의 top 요소를 확인합니다.
   - 값이 p2보다 작으면 pb로 스택 B로 이동시킵니다.
   - 값이 p1보다 작으면 추가로 rb를 수행하여 B의 아래로 보냅니다.
   - 값이 p2 이상이면 ra를 수행하여 A의 아래로 보냅니다.
   - 이 과정을 max_size 만큼 반복합니다.

예시:
스택 A: [4, 2, 9, 1, 7, 5, 3, 8, 6] (왼쪽이 top), max_size = 9
p1 = 3, p2 = 6

과정:
1. 4 < 6: pb (B:)
2. 2 < 3: pb, rb (B: [4, 2])
3. 9 >= 6: ra (A: [2, 9, 1, 7, 5, 3, 8, 6, 4])
4. 2 < 3: pb, rb (B: [4, 2, 2])
5. 9 >= 6: ra (A: [9, 1, 7, 5, 3, 8, 6, 4, 2])
6. 9 >= 6: ra (A: [1, 7, 5, 3, 8, 6, 4, 2, 9])
7. 1 < 3: pb, rb (B: [4, 2, 2, 1])
8. 7 >= 6: ra (A: [7, 5, 3, 8, 6, 4, 2, 9, 1])
9. 7 >= 6: ra (A: [5, 3, 8, 6, 4, 2, 9, 1, 7])

최종 결과:
- 스택 A: 큰 값들 (6 이상)
- 스택 B 상단: 중간 값들 (3-5)
- 스택 B 하단: 작은 값들 (1-2)

이렇게 분류된 스택들은 이후의 정렬 과정을 더 효율적으로 만듭니다.

 

피보팅(pivoting):
피보팅을 먼저 수행하는 이유는 대략적인 정렬을 미리 하여 이후 정렬 과정을 더 효율적으로 만들기 위함입니다. 피보팅은 스택을 대략 세 그룹으로 나눕니다: 작은 값, 중간 값, 큰 값3.
예시: [4, 2, 9, 1, 7, 5, 3, 8, 6]
피보팅 후: [3, 2, 1, 4, 5, 6, 9, 8, 7] (A 스택)
pb 연산:
피보팅 후 스택 A의 상위 요소들을 스택 B로 이동시킵니다. 이는 작은 값들을 B로 옮겨 A에 남은 요소들의 정렬을 단순화합니다.
예시 계속:
A: [6, 9, 8, 7]
B: [5, 4, 1, 2, 3]
소규모 정렬:
A 스택에 남은 요소들을 정렬합니다. 2개나 3개일 경우 간단한 정렬 알고리즘을 사용합니다.
smallest_rotation:
이 함수는 A 스택의 요소들을 회전시켜 최소값이 top에 오도록 합니다. 이는 B 스택의 요소들을 다시 A로 옮길 때 정렬 상태를 유지하기 위함입니다3.
smallest_sorting:
이 함수는 최종적으로 A 스택을 완전히 정렬된 상태로 만듭니다. B 스택의 요소들이 A로 이동된 후, A 스택의 최소값을 찾아 top으로 이동시킵니다.
smallest_sorting 함수는 B 스택에서 모든 요소가 A로 이동된 후에 실행됩니다. 이 함수의 목적은 A 스택의 최소값을 top으로 이동시키는 것입니다. 이는 B에 남아있던 두 번째로 작은 값이 A로 이동된 경우를 포함하여, 모든 경우에 대해 최종적으로 A 스택을 완전히 정렬된 상태로 만들기 위함입니다