제자리 알고리즘

컴퓨터 과학에서 제자리(in-place) 알고리즘은 자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘이다. 그러나 보통 추가적인 변수를 위해 약간의 추가 저장 공간은 허용된다. 일반적으로 알고리즘이 실행되면서 입력 값이 출력 값으로 덮어써지는데 입력 요소를 출력 요소로 교체하거나 요소의 위치를 바꾸는 방식으로 업데이트한다.

제자리라는 말은 조금씩 다른 의미를 가질 수 있는데, 가장 엄격하게는 함수 호출 및 포인터까지 포함하여 고정된 양의 추가 공간만 가지는 것을 의미한다. 그러나 단순히 길이 n 인 배열에 대한 인덱스를 갖는 데만도 O(log n) 비트가 필요하기 때문에 이 의미는 매우 제한적으로 사용된다. 좀 더 넓은 의미로는, 입력을 조작하기 위한 추가 공간을 사용하지 않지만 일부 계산을 위해 고정되지 않은 작은 추가 공간이 필요할 수 있음을 의미한다. 일반적으로 이 공간은 O(log n)이지만 때로는 O(n)까지도 허용된다. 공간 복잡도 역시 인덱스 길이를 사용된 공간의 일부로 계산할지 여부에 따라 여러 의미로 사용될 수 있다. 많은 경우 공간 복잡도는 인덱스의 길이는 무시하고 필요한 인덱스 또는 포인터의 개수를 이용한다. 하지만 이 문서에서는 포인터 길이까지 계산하는 총 공간 복잡성(DSPACE)을 사용한다. 따라서 인덱스 및 포인터의 길이를 무시하는 분석에 비해 여기서의 필요 공간 계산 결과에는 추가 log n의 계수가 추가되어 있다.

알고리즘은 출력 내용을 공간 사용 계산에 포함 할 수도 있고 하지 않을 수도 있다. 제자리 알고리즘은 일반적으로 입력을 출력으로 덮어쓰기 때문에 추가 공간이 필요하지 않다. 출력을 쓰기 전용 메모리나 스트림에 쓸 때 알고리즘의 작업 공간만 고려하는 것이 더 적절할 수 있다. 로그 공간 축소와 같은 이론적인 응용 프로그램에서는 항상 출력 공간을 무시하는 것이 더 일반적이다(이 경우 출력이 쓰기 전용이라는 것이 더 중요하다).

예

n개 항목을 가지는 배열 a가 주어졌을 때 동일한 항목이 역순으로 들어있는 배열을 만들고 원래 배열은 버리는 방법을 생각해보자. 이를 수행하는 간단한 방법은 동일한 크기의 새 배열을 만들고 적절한 순서에 따라 a에서 각 항목을 복사하는 방식이다.

 function 뒤집기(a[0..n - 1])
     b[0..n - 1] 할당
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     return b

안타깝게도 이 방법은 배열 a와 b를 동시에 사용할 수 있도록 하기 위해 O(n)의 추가 공간이 필요하다. 또한 메모리 공간을 할당하고 및 할당을 해제하는 것은 보통 느린 작업이다. 배열 a가 필요하지 않기 때문에 보조 변수 i와 tmp라는 고정된(2) 개수의 공간만 있으면 되는 아래의 제자리 알고리즘을 사용하여 배열 a를 자신의 뒤집혀진 값으로 덮어쓸 수 있다.

 function 제자리에서뒤집기(a[0..n-1])
     for i from 0 to floor((n-2)/2)
         tmp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := tmp

또 다른 예로 버블 정렬, 빗 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 셸 정렬 등을 비롯한 많은 정렬 알고리즘이 배열을 제자리에서 정렬된 순서로 재배열한다. 이러한 알고리즘에는 몇 개의 포인터만 필요하므로 공간 복잡도는 O(log n)이다.

퀵 정렬은 정렬할 데이터에 대해 제자리에서 작동한다. 그러나 퀵 정렬은 분할 정복 전략에서 하위 배열을 추적하기 위해 O(log n)만큼의 스택 공간 포인터가 필요하다. 결과적으로 퀵 정렬에는 O(log² n)의 추가 공간이 필요하다. 엄밀히는 이 고정되지 않은 공간때문에 퀵 정렬을 제자리 알고리즘 범주에서 제외하지만 O(log n)의 추가 포인터만 필요한 퀵 정렬 및 기타 알고리즘은 일반적으로 제자리 알고리즘으로 간주된다.

대부분의 선택 알고리즘도 제자리 알고리즘이지만 일부 알고리즘은 일정한 크기인 최종 결과값을 찾는 과정에서 입력 배열을 상당히 재배열한다.

자르기 및 뒤집기와 같은 일부 텍스트 조작 알고리즘은 제자리에서 수행될 수 있다.

같이 보기

• 제자리 및 비제자리 정렬 알고리즘 표