셰이커 정렬(Shaker Sort)은 주어진 데이터를 정렬하기 위해 사용되는 알고리즘입니다. 흔히 '칵테일 정렬' 또는 '양방향 버블 정렬'이라고도 불리며, 일반적인 버블 정렬과 달리 배열을 양쪽 방향(정방향과 역방향)으로 번갈아 가며 탐색하면서 정렬을 수행합니다. 이러한 양방향 접근 덕분에 배열 끝에 있는 작은 값(거북이 문제, turtle problem)이 한 번의 패스만으로 앞쪽으로 이동할 수 있어, 특정 상황에서는 버블 정렬보다 유리합니다. 이 알고리즘의 최악의 경우 시간 복잡도는 O(n²)입니다.
알고리즘
시작
ShakerSort() 함수는 인자로 데이터 배열 'arr'과 값의 개수 'n'을 받습니다.
// 중첩 for 루프를 사용하여 정렬 알고리즘을 구현합니다.
바깥쪽 루프는 'i'가 0부터 n-1까지 반복하며, 내부에 두 개의 루프를 포함합니다.
첫 번째 루프는 'j'가 i+1부터 n-1까지 반복하며,
a[j] < a[j-1]이면 swap() 함수를 호출하여 두 값을 교환합니다.
그런 다음 n을 감소시킵니다.
두 번째 루프는 'k'가 m-1부터 i+1까지 반복하며,
a[k] < a[k-1]이면 swap() 함수를 호출하여 두 값을 교환합니다.
마지막으로 i를 증가시킵니다.
끝예제 코드
다음은 C++로 작성된 셰이커 정렬의 완전한 구현 예제입니다. 사용자로부터 정렬할 데이터의 개수와 각 요소를 입력받은 후, 정렬된 결과를 출력합니다.
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void ShakerSort(int a[], int m) {
int i, j, k;
for(i = 0; i < m;) {
for(j = i+1; j < m; j++) {
if(a[j] < a[j-1])
swap(&a[j], &a[j-1]);
}
m--;
for(k = m-1; k > i; k--) {
if(a[k] < a[k-1])
swap(&a[k], &a[k-1]);
}
i++;
}
}
int main() {
int n, i;
cout<<"\n정렬할 데이터 요소의 개수를 입력하세요: ";
cin>>n;
int a[n];
for(i = 0; i < n; i++) {
cout<<"요소 "<<i+1<<" 입력: ";
cin>>a[i];
}
ShakerSort(a, n);
cout<<"\n정렬된 데이터 ";
for (i = 0; i < n; i++)
cout<<"->"<<a[i];
return 0;
}실행 결과
정렬할 데이터 요소의 개수를 입력하세요: 4 요소 1 입력: 3 요소 2 입력: 1 요소 3 입력: 7 요소 4 입력: 6 정렬된 데이터 ->1->3->6->7
동작 원리 요약
위 코드에서 첫 번째 내부 루프는 배열의 앞에서 뒤로 이동하며 큰 값을 끝으로 밀어내고, 두 번째 내부 루프는 뒤에서 앞으로 이동하며 작은 값을 앞으로 당겨옵니다. 매 반복마다 정렬이 완료된 양쪽 끝 영역(m 감소, i 증가)을 제외하기 때문에 비교 범위가 점점 좁아지며, 모든 요소가 제자리에 놓이면 정렬이 종료됩니다.