꼭두각시 정렬

1. 개요

꼭두각시 정렬은 정렬 알고리즘의 하나로, 재귀 호출을 기반으로 한다. 배열의 처음 2/3, 마지막 2/3를 정렬하고, 다시 처음 2/3를 정렬하는 방식으로 구현된다. JavaScript, Haskell 등 다양한 프로그래밍 언어로 구현될 수 있다.

2. 구현

꼭두각시 정렬 알고리즘은 재귀적인 방식으로 구현된다. 정렬 과정은 다음과 같은 단계로 이루어진다.

1. 정렬하고자 하는 배열(또는 배열의 일부)에서 첫 번째 요소와 마지막 요소를 비교한다. 만약 첫 번째 요소가 마지막 요소보다 크다면, 두 요소의 위치를 바꾼다.
2. 현재 처리 중인 배열(또는 배열의 일부)의 요소 개수가 3개 이상인지 확인한다.
3. 요소 개수가 3개 이상이라면, 배열의 길이를 3등분하여 크기 `t`를 계산한다. (정확히 나누어떨어지지 않으면 내림한다.)
4. 배열의 처음 2/3 (인덱스 `i`부터 `j-t`까지)에 대해 꼭두각시 정렬을 재귀적으로 호출한다.
5. 배열의 마지막 2/3 (인덱스 `i+t`부터 `j`까지)에 대해 꼭두각시 정렬을 재귀적으로 호출한다.
6. 배열의 처음 2/3 (인덱스 `i`부터 `j-t`까지)에 대해 꼭두각시 정렬을 다시 재귀적으로 호출한다. 이 마지막 단계를 통해 이전 단계에서 뒤쪽으로 밀려났을 수 있는 요소들이 올바른 위치를 찾아갈 수 있게 된다.
7. 요소 개수가 2개 이하이면 위의 재귀 호출 과정 없이 1번 단계만 수행하거나 아무 작업도 하지 않는다.

이러한 재귀적 호출을 통해 전체 배열이 정렬된다. 구체적인 구현 예시는 아래 하위 섹션에서 다양한 프로그래밍 언어로 확인할 수 있다.

2.1. 의사 코드

자바스크립트와 유사한 의사 코드로 표현된 꼭두각시 정렬 알고리즘은 다음과 같다.


function stoogesort(배열 L, i = 0, j = 길이(L)-1){
if L[i] > L[j] then // 만약 가장 왼쪽 요소가 가장 오른쪽 요소보다 크다면
swap(L[i],L[j]) // 두 요소를 바꾼다
if (j - i + 1) > 2 then // 만약 배열에 최소 3개의 요소가 있다면
t = floor((j - i + 1) / 3)
stoogesort(L, i, j-t) // 배열의 처음 2/3를 정렬한다
stoogesort(L, i+t, j) // 배열의 마지막 2/3를 정렬한다
stoogesort(L, i, j-t) // 배열의 처음 2/3를 다시 정렬한다
return L
}

2.2. Haskell

함수형 프로그래밍 언어인 Haskell로 구현한 꼭두각시 정렬 알고리즘은 다음과 같다.


-- 최선은 아니지만 위와 동일함

스투지 정렬 :: (Ord a) => [a] -> [a]
스투지정렬 [] = []
스투지정렬 src = innerStoogesort src 0 ((length src) - 1)

내부스투지정렬 :: (Ord a) => [a] -> Int -> Int -> [a]
내부스투지정렬 src i j
| (j - i + 1) > 2 = src'
| otherwise = src'
where
src' = swap src i j -- 매 호출마다 필요
t = floor (fromIntegral (j - i + 1) / 3.0)
src = innerStoogesort src' i (j - t)
src = innerStoogesort src (i + t) j
src' = innerStoogesort src i (j - t)

swap :: (Ord a) => [a] -> Int -> Int -> [a]
swap src i j
| a > b = replaceAt (replaceAt src j a) i b
| otherwise = src
where
a = src !! i
b = src !! j

replaceAt :: [a] -> Int -> a -> [a]
replaceAt (x:xs) index value
| index == 0 = value : xs
| otherwise = x : replaceAt xs (index - 1) value

2.3. JavaScript

wikitext

function stoogesort(L, i = 0, j = L.length - 1) {
// 배열의 가장 왼쪽 요소가 가장 오른쪽 요소보다 크면 두 요소를 교환한다.
if (L[i] > L[j]) {
const temp = L[i];
L[i] = L[j];
L[j] = temp;
}

// 배열에 요소가 3개 이상 있으면
if (j - i + 1 > 2) {
const t = Math.floor((j - i + 1) / 3); // 내림 연산을 수행한다.

// 배열의 처음 2/3를 정렬한다.
stoogesort(L, i, j - t);
// 배열의 마지막 2/3를 정렬한다.
stoogesort(L, i + t, j);
// 배열의 처음 2/3를 다시 정렬한다.
stoogesort(L, i, j - t);
}
return L;
}