파이썬으로 배우는 그놈 정렬(Gnome Sort) 알고리즘 구현하기

이 글에서는 그놈 정렬(Gnome Sort)이라는 간단한 정렬 알고리즘을 파이썬으로 구현하는 방법을 단계별로 살펴보겠습니다.

문제 정의

문제 — 주어진 배열을 그놈 정렬 알고리즘을 이용해 오름차순으로 정렬해야 합니다.

알고리즘 원리

그놈 정렬은 이름처럼 '정원 난쟁이(gnome)'가 화분을 정리하듯 배열을 순회하며 정렬하는 직관적인 방식입니다. 동작 과정은 다음과 같습니다.

1. 배열을 왼쪽에서 오른쪽으로 순회합니다.
2. 현재 요소가 이전 요소보다 크거나 같으면 한 칸 앞으로 이동합니다.
3. 현재 요소가 이전 요소보다 작으면 두 요소를 교환하고 한 칸 뒤로 이동합니다.
4. 배열의 끝에 도달할 때까지 위 과정을 반복합니다.

이 알고리즘은 삽입 정렬과 유사하지만, 인덱스를 되돌아가는 방식으로 구현되기 때문에 코드가 더욱 단순하다는 특징이 있습니다.

구현 예제

def gnomeSort(arr, n):
    index = 0
    while index < n:
        if index == 0:
            index = index + 1
        if arr[index] >= arr[index - 1]:
            index = index + 1
        else:
            arr[index], arr[index-1] = arr[index-1], arr[index]
            index = index - 1
    return arr

# main
arr = [1,4,2,3,6,5,8,7]
n = len(arr)
arr = gnomeSort(arr, n)
print("Sorted sequence is:")
for i in arr:
    print(i, end=" ")

실행 결과

Sorted sequence is:
1 2 3 4 5 6 7 8

위 코드에서 사용된 모든 변수는 지역 범위(local scope) 내에서 선언되며, index 변수가 현재 위치를 추적하면서 조건에 따라 앞뒤로 이동하는 것이 핵심입니다.

시간 복잡도

그놈 정렬의 시간 복잡도는 최선의 경우(이미 정렬된 배열) O(n), 평균 및 최악의 경우 O(n²)입니다. 공간 복잡도는 제자리(in-place) 정렬 방식이므로 O(1)로 매우 효율적입니다.

결론

이번 글에서는 그놈 정렬의 기본 개념과 동작 원리를 이해하고, 파이썬으로 이를 구현하는 전체 과정을 살펴보았습니다. 코드가 단순하여 학습용으로 적합하며, 삽입 정렬과의 차이점을 비교해 보면 정렬 알고리즘에 대한 이해를 더욱 깊게 할 수 있습니다.