C++로 구현하는 그놈 정렬(Gnome Sort) 프로그램

그놈 정렬(Gnome Sort)이란?

그놈 정렬은 삽입 정렬(Insertion Sort)과 유사한 정렬 알고리즘입니다. 다만, 각 원소를 올바른 위치로 이동시킬 때 인접한 원소끼리 반복적으로 교환(swap)하는 방식을 사용한다는 점에서 버블 정렬(Bubble Sort)과 비슷합니다. 알고리즘의 동작 방식이 화분을 하나씩 옮기며 정리하는 정원 난쟁이(garden gnome)의 움직임과 닮았다고 해서 이런 이름이 붙었습니다.

Input: 53421
Output: 12345

동작 원리

그놈 정렬은 단순한 루프만으로 구현할 수 있으며, 로직은 다음과 같습니다.

• 현재 위치가 배열의 시작이거나, 이전 원소가 현재 원소보다 작거나 같으면 인덱스를 1 증가시킵니다.
• 그렇지 않으면(순서가 잘못되었다면) 두 원소를 서로 교환하고 인덱스를 1 감소시켜 앞쪽을 다시 검사합니다.
• 인덱스가 배열의 끝에 도달할 때까지 이 과정을 반복하면 정렬이 완료됩니다.

시간 복잡도는 최악의 경우 O(n²)이며, 이미 정렬된 배열에 대해서는 O(n)으로 매우 효율적으로 동작합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int main() {
    int temp;
    int arr[] = { 5, 3, 4, 2, 1 };
    int n = 5;
    int i;
    i = 0;
    while (i < n) {
        if (i == 0 || arr[i - 1] <= arr[i])
            i++;
        else {
            temp = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = temp;
            i = i - 1;
        }
    }
    for (i = 0; i < n; i++) {
        cout << arr[i] << "\t";
    }
}

실행 결과

1    2    3    4    5

위 코드는 {5, 3, 4, 2, 1} 배열을 그놈 정렬 알고리즘으로 오름차순 정렬한 후, 탭 문자로 구분하여 결과를 출력합니다.