PROFILBARU.COM

컴퓨터 프로그래밍에서 교체 연산(swap) 또는 스왑 알고리즘(swap algorithm)은 두 변수에 들어 있는 값을 서로 맞바꾸는 연산 또는 이러한 연산을 사용하는 알고리즘이다.

예를 들어 만약 변수 a와 b에 각각 2와 3이라는 정수 값이 들어 있을 때,

swap (a, b)

라는 명령을 실행하면 두 변수의 값은 각각 3과 2로 변한다.

교체 연산은 많은 알고리즘들에서 사용된다. 대표적으로 많은 정렬 알고리즘은 값들의 순서를 바꾸기 위해 교체 연산을 사용한다.

여러 프로그래밍 언어는 교체 연산을 위한 명령을 지원하며, 일부 언어는 언어의 일부가 아닌 표준 라이브러리를 통해 이 기능을 지원한다. (예를 들어 C++의 std::swap) 자바와 같이 변수에 대한 교체 연산을 언어의 일부로도 지원하지 않으며, 참조와 같은 언어 기능이 없어서 함수를 통해 구현할 수 없는 경우도 존재한다.

교체 연산의 구현

임시 변수

교체 연산은 원래의 두 변수 이외에 제 3의 변수(임시 변수)를 도입하여 구현할 수 있다. 의사코드로는 다음과 같을 것이다.

temp ← a
a ← b
b ← temp

이 때 임시 변수에 저장되는 값이 a인가 b인가는 실제 작동에 영향을 미치지 않는다.

이 방법은 가장 쉽게 생각할 수 있으며, 대부분의 경우 가장 효율적이다. 하지만 변수가 차지하는 공간이 크고 대입할 때 그 공간의 복사가 일어난다면 이 방법은 최선이 아닐 수 있다. 생성자와 소멸자를 지원하는 많은 객체 지향 프로그래밍 언어의 경우 대입된 변수가 생성되거나 소멸될 때 필요한 비용이 무시할 수 없는 경우도 있다.

XOR을 이용한 구현

교체 연산은 세 개의 배타적 논리합(XOR) 연산으로 구현할 수도 있다. 이 연산은 보통 정수와 같은 간단한 자료형을 교체할 때 사용하지만, 이론적으로는 임의 길이의 두 비트열을 맞바꿀 때 사용할 수 있다. 의사코드로는 다음과 같다.

a ← a XOR b
b ← a XOR b
a ← a XOR b

배타적 논리합을 사용한 교체는 별도의 변수를 사용하지 않으며, 명령어에 대한 최적화를 크게 수행하지 않는 프로세서에서는 임시 변수를 쓰는 것보다 빠르게 수행된다. 하지만 파이프라인 등과 같은 프로세서 기술의 발달로 이 장점은 더 이상 부각되지 않는다. 또한 두 변수가 같은 메모리 공간을 가리킬 경우 이 알고리즘이 작동하지 않는다는 문제도 있다.

산술 연산을 이용한 구현

배타적 논리합을 사용한 구현의 변형으로, 교체 연산을 덧셈과 뺄셈을 사용하여 다음과 같이 구현할 수도 있다.

a ← a + b
b ← a - b
a ← a - b

이 방법은 배타적 논리합을 사용하는 방법에 비해 비싼 연산(덧셈과 뺄셈)을 사용하기 때문에 더 느리며, 보통 사용되지 않는다. 알고리즘 내의 문제는 없지만 실제 프로그래밍에서는 오버플로우가 일어날 수 있기 때문에 사용 하지 않는 것이 좋다.

컨테이너의 교체

C++의 STL과 같은 라이브러리에서는 가변 배열(std::vector), 연관 배열(std::map)과 같은 컨테이너들을 위한 특별한 std::swap 함수를 제공한다. 일반적으로 이러한 컨테이너들의 대입에는 메모리 복사와 같이 큰 비용이 필요한데, 실제로 이들 컨테이너들은 내부적으로 포인터나 참조를 사용하여 구현되므로 가리키는 내용만을 바꿈으로써 보다 적은 비용으로 교체가 가능하다. 이러한 특수화(specialization)는 C++의 언어적인 특징으로부터 기인하며, 다른 라이브러리도 이와 같은 방법으로 std::swap을 중복 적재할 수 있다.

프로세서 차원의 지원

교체 연산이 많은 알고리즘에서 사용되기 때문에, 현대의 많은 프로세서들은 교체 연산을 처리하기 위한 명령어를 지원한다. 예를 들어 IA-32에는 두 레지스터나 메모리 주소를 받아 그 값을 맞바꾸는 XCHG 명령이 존재하며, 심지어 두 값을 먼저 비교한 뒤 그 결과에 따라 선택적으로 교체 연산을 행하는 CMPXCHG 명령도 존재한다. 이들 명령은 소프트웨어적인 처리보다 좀 더 프로세서의 구조에 특화되어 있으므로 빠르게 수행되지만, 일부 프로세서는 이 과정을 원자적 명령으로 처리하는 경우도 있기 때문에 생각만큼 빠르지는 않다. (예를 들어 앞에서 언급한 XCHG 명령은 원자성을 강제하는 LOCK 접두어를 암시한다.)

병렬 컴퓨팅이 가능할 경우 교체 연산을 좀 더 효과적으로 수행하는 것이 가능하다. 예를 들어서 두 프로세서가 두 변수의 값을 레지스터에 저장한 뒤, 그 결과를 원래와 반대로 저장하면 두 개의 명령을 수행하는 시간 안에 교체 연산이 가능하다. 그러나 일반적으로 이 과정을 적용하기 위해서는 두 프로세서 사이에 상당한 동기화 과정이 필요하기 때문에 이를 문자적으로 적용하는 것은 힘들며, 한 프로세서 상에서 여러 개의 적재·저장 유닛이 존재하는 경우에는 최적화를 위해 사용하기도 한다.

일부 컴파일러나 인터프리터는 임시 변수를 사용한 교체와 같이 자주 사용되는 코드를 자동으로 감지해 적절한 기계어로 변환해 주기도 한다.