[C/C++] Swap

프로그래밍을 공부하다 보면 기본적인 문법 이후에는 자료구조와 알고리즘을 익혀야 한다. 특히 알고리즘은 가장 처음 배우는 것은 정렬(sorting) 알고리즘들이다. 정렬 알고리즘은 주어진 배열 안에 무작위한 여러 숫자들이 존재 할 때, 이 숫자가 오름차순(또는 내림차순)으로 정렬 시키는 방법에 대한 것이다. 이를 위해서는 필연적으로 배열의 순서를 바꾸기 위한 swap함수가 사용 되게 된다.

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
    return;
}

swap함수의 가장 기초적인 형태는 위와 같이 하나의 변수(위에선 a)를 선택하여 임시변수temp에 저장하고, 그 변수에는 b의 값을 저장한다. 이후 b변수에 temp변수에 저장한 a의 값을 다시 저장해 주게 된다. 위의 함수에서는 C++문법 중 참조(reference)를 사용하여 swap된 변수를 함수 밖에서도 사용할 수 있도록 하였다.
여기서 좀 더 다양한 값에 대해 swap할 수 있는 함수를 구현하고 싶다면, C++에서 사용되는 template을 사용하면 간단히 구현할 수 있다.

template<typename T>
void swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
    return;
}

원래 함수에서 int에 해당하는 자료형 부분만 template을 통해 임의의 타입으로 사용 가능하도록 변경하였다.

int main(void)
{
    int ai = 3, bi = 8;
    std::cout << "ai = " << ai << ", bi = " << bi << "\n";
    swap(ai, bi);
    std::cout << "ai = " << ai << ", bi = " << bi << "\n";

    double ad = 3, bd = 8;
    std::cout << "ad = " << ad << ", bd = " << bd << "\n";
    swap(ad, bd);
    std::cout << "ad = " << ad << ", bd = " << bd << "\n";

    Point ap = { 1, 2 }, bp = { 3, 4 };
    std::cout << "ap = <" << ap.x << ", " << ap.y << ">, bp = <" << bp.x << ", " << bp.y << ">\n";
    swap(ap, bp);
    std::cout << "ap = <" << ap.x << ", " << ap.y << ">, bp = <" << bp.x << ", " << bp.y << ">\n";
    return 0;
}

위에서 선언한 함수를 사용하여 int형, double형, Point 구조체로 간단한 테스트를 시도해 본다면, 여기서 Point는 다음과 같이 정의하였다.

typename struct tPoint {int x, y;}Point;

ai = 3, bi = 8
ai = 8, bi = 3
ad = 3, bd = 8
ad = 8, bd = 3
ap = <1, 2>, bp = <3, 4>
ap = <3, 4>, bp = <1, 2>

D:\Sangwons_Room\02_개인문서\스터디\BeakJoon\x64\Debug\beakjoon.exe(프로세스 36512개)이(가) 종료되었습니다(코드: 0개).
디버깅이 중지될 때 콘솔을 자동으로 닫으려면 [도구] -> [옵션] -> [디버깅] > [디버깅이 중지되면 자동으로 콘솔 닫기]를 사용하도록 설정합니다.
이 창을 닫으려면 아무 키나 누르세요...

 

과 같이 출력됨을 확인 할 수 있다.
대부분의 swap관련된 포스팅이나 책에서 본 내용은 대게 여기서 마무리가 되거나, #define전처리기를 통한 swap함수 구현 정도만 포함되어 있는데, 임시변수temp 없이 구현할 수는 없는가라는 문제를 보게 되어 관련된 내용을 찾아 보니 재밋는 방법으로 구현되어 있었다.

void swap(long long &a, long long &b)
{
    a = a + b;
    b = a - b;
    a = a - b;
}

아주 단순해 보이는 세줄이지만, 내용은 정말 신기하였다(이런걸 생각해낸 사람들은 어떤 사람일까 싶기도 하고..) 아주 간단한 내용이지만, 간략하게 예시를 들어 살펴보자.
각 변수 a, b에는 1과 3이라는 숫자가 들어 있다고 생각해보자. 그러면 함수의 첫번째 줄 a = a + b;를 통해서 a = 4가 되게 된다. 그러면 b = a - b는 b = 4 - 1 = 3이 되어 원래 a변수의 값인 3이 b변수에 저장되게 된다. 이후 내용도 마찬가지로 a = a - b는 a = 4 - 3 = 1이 되면서 b변수의 원래 값이었던 1은 a변수에 저장되게 된다. 이 내용이 신기한 이유는, 단순 산술 연산 만을 통해서 변수를 뒤바꾼다는 점도 있지만, 이를 통해 다양한 변수, 심지어 구조체와 같이 더 복잡한 형태에도 함수 변경 없이 똑같이 사용이 가능하다는 점이 있다.

int main(void)
{
    long long ai = 3, bi = 8;
    std::cout << "ai = " << ai << ", bi = " << bi << "\n";
    swap_wo_temp(ai, bi);
    std::cout << "ai = " << ai << ", bi = " << bi << "\n";

    double ad = 3, bd = 8;
    double* pt_ad = &ad, * pt_bd = &bd;
    std::cout << "ad = " << *pt_ad << ", bd = " << *pt_bd << "\n";
    long long ad_addr = (long long)pt_ad, bd_addr = (long long)pt_bd;
    swap_wo_temp(ad_addr, bd_addr);
    pt_ad = (double*)ad_addr;
    pt_bd = (double*)bd_addr;
    std::cout << "ad = " << *pt_ad << ", bd = " << *pt_bd << "\n";

    Point ap = { 1, 2 }, bp = { 3, 4 };
    Point* pt_ap = &ap, * pt_bp = &bp;
    long long ap_addr = (long long)(pt_ap), bp_addr = (long long)(pt_bp);
    std::cout << "ap = <" << pt_ap->x << ", " << pt_ap->y << ">, bp = <" << pt_bp->x << ", " << pt_bp->y << ">\n";
    swap_wo_temp(ap_addr, bp_addr);
    pt_ap = (Point*)ap_addr;
    pt_bp = (Point*)bp_addr;
    std::cout << "ap = <" << pt_ap->x << ", " << pt_ap->y << ">, bp = <" << pt_bp->x << ", " << pt_bp->y << ">\n";

    return 0;
}

약간은 복잡해 보이는 테스트지만, 첫번째 테스트는 long long타입의 변수를 직접 변경하는 방식이라면, 두 번째 double과 세번째 Point의 경우는 각 변수의 주소를 바꿔주는 방식을 채택한 것이다. 변수의 주소값 역시 결국에는 어떤 숫자형 값으로 변경해서 볼 수 있고, 주소만 바꿔준다면 결과적으로는 각 변수에서 보는 값이 변경된 것 과 같다. 여기서 주의해야 할 점은 double과 Point를 swap할 때, 포인터를 swap하지 않고 변수를 직접 swap하고자 하면 변수의 주소값에 담긴 결과가 변경되면서 의도와는 다르게 동작 할 수 있다. 결과는 아래와 같이 정상적으로 값이 swap되어 출력된다.

ai = 3, bi = 8
ai = 8, bi = 3
ad = 3, bd = 8
ad = 8, bd = 3
ap = <1, 2>, bp = <3, 4>
ap = <3, 4>, bp = <1, 2>

D:\Sangwons_Room\02_개인문서\스터디\BeakJoon\x64\Debug\beakjoon.exe(프로세스 34980개)이(가) 종료되었습니다(코드: 0개).
디버깅이 중지될 때 콘솔을 자동으로 닫으려면 [도구] -> [옵션] -> [디버깅] > [디버깅이 중지되면 자동으로 콘솔 닫기]를 사용하도록 설정합니다.
이 창을 닫으려면 아무 키나 누르세요...

이렇게 주소값을 swap해주는 방식이 과연 얼마나 효용가치가 있을지는 잘 모르겠다. 특히, 각 변수의 값이 순차적으로 저장되는 배열과 같은 형태에서는 사용할 수 없다고 생각된다. 하지만, 직접 값을 복사하지 않고 포인터만 swap하고 싶다면 이런 방법 역시 시도해볼 만한 방법이지 않을까라고 생각이 든다.

위에서 사용된 코드는 github링크에 업로드 해 놓았습니다.