swap 알고리즘

개요

💡두 변수의 값의 교체

알고리즘에서 swap은 두 변수의 값들을 서로 교체하는 과정이다. swap은 여러 알고리즘에서 기본 연산으로 사용된다. 예를 들어 정렬 알고리즘에서는 요소를 올바른 위치로 이동시키기 위해 swap 연산을 사용한다.

 

기본개념

1) 임시변수를 사용하는 경우

temp = a
a = b
b = temp

2) XOR 연산을 하는 경우

a = a ^ b
b = a ^ b
a = a ^ b

3) 덧셈, 뺄셈을 하는 경우

a = a + b
b = a - b
a = a - b

 

Swap의 구현

1) 포인터를 사용하는 경우

void swap(int *i, int *j){
	int temp = *i;
	*i = *j;
	*j = temp;
}

2) 레퍼런스를 사용하는 경우

void swap(int &i, int &j){
	int temp = i;
	i = j;
	j = temp;
}

 

정리

정렬 등의 알고리즘에서는 swap을 기본 연산으로 활용한다. swap 연산은 내부로직을 구현할 때 임시변수, XOR 연산, 덧셈과 뺄셈을 활용하는 방법이 있다. C++에서는 포인터 또는 레퍼런스를 활용해서 함수로 정의하여 swap 연산을 구현할 수 있다. 하지만 C++에서는 swap 함수를 별도로 제공해주기 때문에 정렬 알고리즘에서 구현할 때는 해당 표준 함수를 사용하자.

std::swap(int a, int b);