스투지 정렬(Stooge Sort)은 재귀 호출을 기반으로 동작하는 정렬 알고리즘입니다. 구현 방식이 매우 단순하지만 시간 복잡도가 약 O(n^2.71)로 비효율적이기 때문에 실무보다는 재귀와 분할 개념을 학습하기 위한 교육용 예제로 주로 활용됩니다.
예제 코드
import java.io.*;
public class Demo {
static void stooge_sort(int my_arr[], int l_val, int h_val){
if (l_val >= h_val)
return;
if (my_arr[l_val] > my_arr[h_val]){
int temp = my_arr[l_val];
my_arr[l_val] = my_arr[h_val];
my_arr[h_val] = temp;
}
if (h_val - l_val + 1 > 2){
int temp = (h_val - l_val + 1) / 3;
stooge_sort(my_arr, l_val, h_val - temp);
stooge_sort(my_arr, l_val + temp, h_val);
stooge_sort(my_arr, l_val, h_val - temp);
}
}
public static void main(String args[]){
int my_arr[] = {12, 34, 67, 91, 11, 0, 89, 102, 39};
int n = my_arr.length;
stooge_sort(my_arr, 0, n - 1);
System.out.println("The array after performing stooge sort is ");
for (int i = 0; i < n; i++)
System.out.print(my_arr[i] + " ");
}
}
실행 결과
The array after performing stooge sort is 0 11 12 34 39 67 89 91 102
코드 동작 원리
Demo 클래스 내부에는 stooge_sort 함수가 정의되어 있으며, 이 함수는 정렬 대상 배열과 함께 구간의 시작 인덱스(l_val), 끝 인덱스(h_val)를 매개변수로 전달받습니다.
먼저 시작 인덱스가 끝 인덱스보다 크거나 같으면 해당 구간에는 정렬할 요소가 없으므로 함수가 즉시 종료됩니다. 이후 배열의 첫 번째 값이 마지막 값보다 크다면 두 값을 단순히 교환(swap)합니다.
구간의 길이가 3보다 클 경우에는 구간을 3등분한 뒤, 앞쪽 2/3 구간 → 뒤쪽 2/3 구간 → 다시 앞쪽 2/3 구간 순서로 총 세 번의 재귀 호출이 이루어집니다. 이러한 과정을 통해 배열 전체가 점진적으로 정렬됩니다.
main 함수에서는 정렬할 배열을 선언하고 그 길이를 변수 n에 저장합니다. 이어서 배열과 시작·끝 인덱스를 인자로 넘겨 stooge_sort를 호출하고, 정렬이 완료된 배열을 반복문으로 순회하며 콘솔에 출력합니다.
참고 사항
스투지 정렬의 시간 복잡도는 O(n^(log 3 / log 1.5)), 즉 약 O(n^2.71)로 버블 정렬(O(n²))보다도 느린 편입니다. 따라서 실제 프로젝트에서 사용하기에는 부적합하며, 재귀 호출 구조와 분할 정복 아이디어를 익히는 데 유용한 학습용 알고리즘이라고 할 수 있습니다.