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개의 공간이
저글링처럼 돌아간다.j = p[i];
p[i] = p[k];
p[k] = j;
.....
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 )]