SWAP 알고리즘

2010. 2. 27. 13:47STUDY !/잡다한 지식

swap은 위치를 바꾸다. 라는 뜻이다.

두 개의 변수에 대입된 값을 바꾸는 경우에 사용되며, Xor, +, 임시공간할당을 이용한 방법이 있다.

1. 임시공간할당방식 ( temp변수 사용 )
  가장 일반적인방법으로, 값을 바꿀 A, B 두 개의 변수와 값을 임시 저장할 temp(주로 temp로 쓴다.) 변수를 사용한다.
  temp = a; // temp에 a값 기억
  a = b;      // a에 b의 값을 대입
  b = temp;  //  temp에 기억되었던 값을 b로 옮겨온다.

이렇게 하면 처음 a의 값은 b로, b의 값은 a로 입력된다.

임시 저장공간을 이용한 방법은 저장 공간이 하나가 더 필요하지만, 단순 대입연산이기 때문에 타 연산에 비해 속도가 빠르다.

함수로 만들어 사용할 때는 call by reference를 이용한다.
 ( call by value 는 값을 복사해오기 때문에 원래 매개변수로 넘어왔던 원래의 값은 변하지 않는다. )
주소를 매개변수로 넘겨주어 함수 구현부에서 주소를 찾아가 값을 바꾸기 때문에, 매개변수와는 상관없이 저장되어있던 값이 바뀌게 되는 것이다.

2. Xor
  Xor은 Xor비트 연산을 이용한다.
  a = a^b;
  b = b^a;
  a = a^b;
이와 같은 방법을 사용하면 a와 b값이 서로 뒤바뀌게 된다.
자세한 사항은 ( http://www.narsus.net/technotes/1290 ) 페이지를 참조

하지만, Xor연산의 특성(같은 값을 Xor하면 0이 출력됨) 때문에, 연산 수행전에 연산하려는 두 개의 값이 같은지 확인 하는 절차가 필요하다. (ex. 선택정렬 알고리즘의 경우 최소 값이 이미 첫 자리에 있을경우에 이 확인을 하지 않으면 결과가 0이 출력됨.)
  Xor은 임시 저장공간이 필요하지 않으나 비트연산을 수행하기때문에, 임시공간 할당방식의 swap보다는 속도가 느리다. 때문에 메모리에 제약이 있는 경우에 주로 사용한다.
 
3. +
 세번째로, 간단한 덧셈연산을 이용할 수 있다.
 a = a + b;
 b = a - b;
 a = a - b;
 a가 a+b값을 가지므로 다음 연산인 a - b의 결과는 처음 a가 가지고 있던 값이되고,
 다시 a - b를 하면, b가 가진 값이 처음 a의 값이므로 연산의 결과는 b값이 된다. 따라서 a 와 b 의 값이 바뀌게 된다.
 이 연산은 임시공간이 필요하지 않지만 Xor보다 복잡한 연산이 수행(컴퓨터 내부에서) 되기 때문에, Xor보다도 느리므로 가장 느린 알고리즘이다. 하지만 Xor과 같이 두 개의 값이 같은지 확인하는 절차는 필요하지 않다.

반응형