프로그래밍 SWAP(교환) 알고리즘에 대한 고찰(c, python)

프로그래밍의 가장 기본이되는 알고리즘인 swap알고리즘에 대해 알아보겠습니다.

swap알고리즘은 말 그대로 두 변수에 있는 수를 교환하는 방법입니다.

 

SWAP을 구현하는 방법에 대해 알아봅시다.

●(공통)이 swap을 구현하는 가장 일반적인 방법은, 이용하는 방법입니다.

C언어에서의 swap

●(Python) 이 임시변수 없이 다음과 같은 코드로 swap을 구현할 수 있습니다.

x, y = y, x

●(공통)비트연산자인 XOR을 이용하여 임시변수를 사용하지 않고 swap을 구현할 수 있습니다.

원리

숫자 a, b가 있다고 하였을 때, a^b^a의 결과는 b입니다.

이유

교환법칙을 적용한다면 자기 자신(a^a)을 xor하게되고 이것의 결과는 0이 되기 때문입니다. (a^b^a == a^a^b == b)

예시) 110 ^ 001 ^ 110

  == 110 ^ 110 ^ 001

  == 000 ^ 001

  == 001

XOR : 피 연산자의 해당 비트가 다른 경우에만 1

출처 : 위키백과

구현

1. x에는 숫자인(상수) n1이, y에는 숫자인(상수) n2가 들어가 있다고 가정하여봅시다.

#define n1 2 //예시입니다. 어느 숫자가 들어와도 됩니다.
#define n2 3 //예시입니다. 어느 숫자가 들어와도 됩니다.
...
x = n1; y = n2;

2. 이제 원리에서 살펴보았듯이,

 (x^y)^x는 y가 되고, (x^y)^y는 x가 됩니다.

 

y = x^y^x;
x = x^y^y;

간단화(C언어)

C언어에서 대입연산자(복합대입연산자 포함)의 연산 결과는 대입된 수입니다.(r-value, =기준으로 오른쪽 값)

따라서 이를 간단히 정리해볼 수 있습니다.

이해를 돕기위해 변수{변수의 실제값}의 형식으로 작성해보겠습니다.

swap전, x는 숫자 상수 n1을, y는 n2를 가지고 있었습니다.

결과로, x에는 n2값이, y에는 n1값이 들어가 있음을 확인할 수 있습니다.

위 수식을 풀어쓴다면 다음과 같을 것입니다.

#define n1 2
#define n2 3
...
x{n1^n2} = x^y;
y{n1} = x{n1^n2}^y{n2}; // n1^n2^n2 = n1
x{n2} = x{n1^n2}^y{n1}; // n1^n2^n1 = n2

이를 C언어 메크로 함수로 표현하면 다음과 같습니다.

#define swap(x,y) (x!=y) && (x ^= y ^= x ^= y)

 

 

 

참고 

https://ko.wikipedia.org/wiki/%EB%B9%84%ED%8A%B8_%EC%97%B0%EC%82%B0

비트 연산 - 위키백과, 우리 모두의 백과사전

https://codeforwin.org/2019/01/swap-two-numbers-using-macros.html

C program to swap two numbers using macro - Codeforwin