교환(Swap)의 원리 파악하기
양손에 있는 과일 2개를 교환하려면 어떻게 해야 할까?
상식적으로 양손에 과일을 쥔 채로는 과일을 교환할 수 없다. 바닥에 하나의 과일을 내려놓고 바꿔 잡으면 된다.
많은 정렬 알고리즘에서 쓰이는 swap의 원리이다.
swap 알고리즘을 코드로 어떻게 표현해야 할까?
1. 임시변수 사용
#include <iostream>
using namespace std;
int main()
{
int a = 5;
int b = 2;
cout << a << " " << b << endl;
int temp = a;
a = b;
b = temp;
cout << a << " " << b << endl;
return 0;
}바닥에 내려놓는 원리를 temp라는 임시변수에 넣어둔다고 생각하면 된다.
이러한 swap방식은 매우 자주 사용되기 때문에 함수를 만들어서 사용하는 것이 좋다.
함수를 만들 때 call by reference(참조자 방식)를 이용하는 게 가장 효율적이다.
#include <iostream>
using namespace std;
//call by address
void swapPtr(int* a, int* b) //포인터 활용 swap
{
int temp = *a;
*a = *b;
*b = temp;
}
//call by reference
//참조 활용 swap <- 가장 가독성 좋고 추천되는 방식이다
void swapRef(int &a, int &b) //받는 쪽에서 자동으로 주소값에 접근함
{
int temp = a;
a = b;
b = temp;
}
int main()
{
int a = 3;
int b = 2;
cout << a << " " << b << endl;
swapPtr(&a, &b);
cout << a << " " << b << endl;
swapRef(a, b);
cout << a << " " << b << endl;
return 0;
}c++은 기본적으로 라이브러리에서 swap함수를 내장하고 있다.
따라서 swap(a, b); 만 사용해서 위 함수를 사용할 수 있다.
그런데 temp와 같은 임시변수를 사용하지 않고는 Swap을 구현할 수 없을까? 🤔
할 수 있다!!
2. XOR 연산 사용
배타적 논리합 XOR(^)을 활용하여 구현할 수 있다.
임시변수 없이 swap을 진행하기 때문에 과거 프로세서의 최적화(piplining) 능력이 부족했을 때 대안으로 자주 사용되었다.
그러나 최근 CPU에서는 임시변수를 사용하는 방법이 프로세서의 병렬적 수행을 하기 더 쉽다고 한다.
따라서 이 알고리즘은 메모리를 최소화해야 하는 개발 환경에서 유용하게 사용된다. ex) 임베디드 개발
#include <iostream>
using namespace std;
int main()
{
int a = 5;
int b = 1;
cout << a << " " << b << endl;
a = a ^ b;
b = b ^ a;
a = a ^ b;
cout << a << " " << b << endl;
return 0;
}a = a ^ b를 한 뒤에 작동을 보면
아벨 군 정의에 의하면 자기 자신을 XOR 연산을 하면 0이다. b ^ b는 0, a ^ a = 0
위 원리에 의해 비트 간 XOR 연산을 2회 반복하면 원래대로 돌아간다.
따라서 b= b ^ a ^ b = a, a = a ^ b ^ a = b 가 되므로 swap이 수행된다.
3. 산술연산 사용
a = a + b
b = a - b
a = a - ba = a + b를 한 뒤에 작동을 보면
b = a + b - a = a, a = a + b - a = b로 swap이 된다.
그러나 덧셈, 뺄셈은 XOR 연산에 비해 느린 연산, 실제 프로그래밍 시 오버플로우 발생 가능성도 높아 잘 사용하지 않는다.
