스왑 알고리즘

1. 개요[편집]

---

스와프(또는 스왑) 알고리즘(swap algorithm)은 정렬 알고리즘(sort algorithm),분할정복 알고리즘(分割征服algorithm)등에서 분할(Divide)과 재배열(re-arrangement)의 주요한 기능인 스왑핑(swaping)을 구현하는 것을 가리킨다.

2. 스왑 알고리즘[편집]

---

2.1. 예 1 [편집]

---

.....

j = p[i];

p[i] = p[k];

p[k] = j;

.....

단 2개의 저장공간의 순서를 바꾸는 스왑 알고리즘(swap algorithm)의 스왑핑(swaping)은 추가적인 1개의 임시(temporary) 저장공간이 더 필요하다. 이렇게 3개의 공간이 저글링처럼 돌아간다.
A(1),B(2)를 서로 바뀌기 위해서는 A의 값 1을 C(□)에 먼저 옮겨서 저장한후 B의 2를 A(2)에 넣고 B에 C(1)을 넣는 식이다. 이렇게 하기 위해 C(□)가 임시 저장공간으로 중간과정에서 추가로 요구된다.

2.2. 예 2 [편집]

---

[math( 1234 )]를 [math( 2341 )]로 재벼열하는 경우
[math( 1 \rightarrow \square , 4 \rightarrow 1 , 3\rightarrow 4 , 2\rightarrow 3 , \square \rightarrow 2 )]
단 1개의 추가 임시 저장공간[math( \left( \square \right) )]만이 필요하다.
이 경우 슌환루프가 한번만 있다.
그러나
[math( 1234 )]를 [math( 2143 )]로 재벼열하는 경우처럼 [math( 1 \rightarrow 2 , 2 \rightarrow 1 )]과 같은 순환고리(cycle loop)가 1개 더 생겨날수록 임시 저장공간 역시 1개씩 더 추가해야한다.
[math( 1 \rightarrow \square , 2 \rightarrow 1 ,\square \rightarrow 2, 3\rightarrow \square , 4 \rightarrow 3 , \square \rightarrow 4 )]

3. 관련 문서[편집]

---

• 정렬 알고리즘
• 힙 알고리즘