C++로 구현하는 스투지 정렬(Stooge Sort) 프로그램

스투지 정렬(Stooge Sort)은 주어진 데이터를 정렬하는 재귀 기반 정렬 알고리즘입니다. 이 알고리즘은 배열을 서로 겹치는 두 부분, 즉 각각 전체 길이의 2/3 크기로 나눈 뒤, 첫 번째 부분 → 두 번째 부분 → 다시 첫 번째 부분 순서로 세 단계에 걸쳐 정렬을 수행합니다. 최악의 경우 시간 복잡도는 O(n^2.7095)로 효율성은 떨어지지만, 재귀와 분할 정복 개념을 이해하기 좋은 교육용 예제로 활용됩니다.

알고리즘 동작 과정

시작
   정렬할 데이터를 입력받는다.
   배열 'a'와 값의 개수 'n'을 인자로 하여 StoogeSort() 함수를 호출한다.
   재귀 방식을 사용해 정렬을 수행한다.
   배열을 앞쪽 2/3 요소(파트 I)와 뒤쪽 2/3 요소(파트 II)로 나눈다.
   첫 번째 부분, 두 번째 부분, 그리고 다시 첫 번째 부분 순으로 StoogeSort()를 호출한다.
   더 이상 분할할 수 없는 경우, a[end] < a[start]이면 시작과 끝 요소를 서로 교환한다.
   main 함수로 돌아가 정렬된 결과를 출력한다.
종료.

C++ 예제 코드

#include<iostream>
using namespace std;

void StoogeSort(int a[], int start, int end) {
   int temp;
   if(end - start + 1 > 2) {
      temp = (end - start + 1) / 3;
      StoogeSort(a, start, end - temp);      // 앞쪽 2/3 정렬
      StoogeSort(a, start + temp, end);      // 뒤쪽 2/3 정렬
      StoogeSort(a, start, end - temp);      // 다시 앞쪽 2/3 정렬
   }
   if(a[end] < a[start]) {                   // 시작과 끝 요소 비교 후 교환
      temp = a[start];
      a[start] = a[end];
      a[end] = temp;
   }
}

int main() {
   int m, i;
   cout<<"\n정렬할 데이터 개수 입력: ";
   cin>>m;
   int arr[m];
   for(i = 0; i < m; i++) {
      cout<<"요소 "<<i+1<<" 입력: ";
      cin>>arr[i];
   }
   StoogeSort(arr, 0, m - 1);
   cout<<"\n정렬된 데이터 ";
   for(i = 0; i < m; i++)
      cout<<"->"<<arr[i];
   return 0;
}

실행 결과

정렬할 데이터 개수 입력: 4
요소 1 입력: 6
요소 2 입력: 7
요소 3 입력: 3
요소 4 입력: 2
정렬된 데이터 ->2->3->6->7

위 코드는 먼저 배열 길이가 2보다 클 경우 배열을 2/3씩 겹치게 나누어 재귀적으로 정렬하고, 마지막에 시작과 끝 요소를 비교하여 필요하면 교환합니다. 모든 재귀 호출이 완료되면 배열은 오름차순으로 정렬된 상태가 됩니다.