C++로 구현하는 그놈 정렬(Gnome Sort) 알고리즘 완벽 가이드

이번 글에서는 그놈 정렬(Gnome Sort)의 동작 원리와 C++ 구현 방법을 자세히 살펴보겠습니다. 그놈 정렬은 비교적 간단한 구조를 가진 정렬 알고리즘으로, 삽입 정렬과 유사한 방식으로 동작합니다.

그놈 정렬의 가장 큰 장점은 리스트가 이미 정렬되어 있는 경우 선형 시간에 정렬을 마친다는 점입니다. 즉, 최선의 경우 시간 복잡도는 O(n)입니다. 하지만 평균적인 경우와 최악의 경우에는 O(n²)의 시간 복잡도를 가지므로, 대량의 데이터에는 적합하지 않을 수 있습니다.

그놈 정렬 알고리즘

그놈 정렬의 핵심 아이디어는 다음과 같습니다. 인덱스를 앞쪽으로 이동시키며 현재 요소와 이전 요소를 비교하고, 순서가 올바르면 인덱스를 증가시키고, 잘못되어 있으면 두 요소를 교환한 후 인덱스를 감소시켜 뒤로 돌아갑니다. 이 과정을 반복하면 배열 전체가 정렬됩니다.

다음은 그놈 정렬의 의사 코드입니다.

gnomeSort(arr, n)
begin
    index := 0
    while index < n do
        if index = 0 then
            index := index + 1
        end if
        if arr[index] >= arr[index - 1] then
            index := index + 1
        else
            exchange arr[index] and arr[index - 1]
            index := index - 1
        end if
    done
end

C++ 구현 예제

아래는 위 알고리즘을 C++로 실제 구현한 코드입니다.

#include<iostream>
using namespace std;

void gnomeSort(int arr[], int n){
    int index = 0;
    while(index < n){
        if(index == 0) index++;
        if(arr[index] >= arr[index - 1]){ // 현재 요소가 이전 요소보다 크거나 같으면
            index++;
        } else {
            swap(arr[index], arr[index - 1]); // 두 요소를 교환
            index--;
        }
    }
}

main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    gnomeSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

실행 결과

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

마무리

그놈 정렬은 코드가 단순하고 이해하기 쉬워 학습용으로 좋은 알고리즘입니다. 데이터가 거의 정렬된 상태라면 O(n)에 가까운 성능을 보이지만, 역순으로 정렬된 최악의 경우에는 O(n²)의 시간이 소요됩니다. 따라서 실무에서는 퀵 정렬이나 병합 정렬 같은 고급 알고리즘이 더 많이 사용되지만, 정렬 알고리즘의 기본 개념을 익히는 데는 매우 효과적인 예제입니다.