그놈 정렬(Gnome Sort)은 한 번에 하나의 요소를 처리하며 해당 요소를 올바른 위치로 이동시키는 방식으로 동작하는 정렬 알고리즘입니다. 동작 원리가 단순하여 이해하기 쉽고, 삽입 정렬과 유사한 특징을 가지고 있습니다. 아래 예제를 통해 자바에서 그놈 정렬을 구현하는 방법을 살펴보겠습니다.
예제 코드
import java.util.Arrays;
public class Demo{
static void gnome_sort(int my_arr[], int n){
int index = 0;
while (index < n){
if (index == 0)
index++;
if (my_arr[index] >= my_arr[index - 1])
index++;
else{
int temp = 0;
temp = my_arr[index];
my_arr[index] = my_arr[index - 1];
my_arr[index - 1] = temp;
index--;
}
}
return;
}
public static void main(String[] args){
int my_arr[] = { 34, 67, 89, 11, 0 , -21 };
gnome_sort(my_arr, my_arr.length);
System.out.println("그놈 정렬 수행 후 배열의 결과는 다음과 같습니다");
System.out.println(Arrays.toString(my_arr));
}
}실행 결과
그놈 정렬 수행 후 배열의 결과는 다음과 같습니다 [-21, 0, 11, 34, 67, 89]
코드 동작 원리
gnome_sort 함수의 동작 과정:
Demo라는 이름의 클래스 안에는 'gnome_sort'라는 정적(static) 메서드가 정의되어 있습니다. 먼저 'index' 변수를 0으로 초기화한 뒤, while 반복문을 통해 배열 전체를 순회합니다. 동작 흐름은 다음과 같습니다.
- index 값이 배열의 길이보다 작은 동안 반복문이 실행됩니다.
- index가 0이라면 1을 증가시켜 비교 대상을 확보합니다.
- 현재 위치의 요소(my_arr[index])가 바로 앞 요소(my_arr[index - 1])보다 크거나 같다면 이미 올바른 순서이므로 index를 1 증가시켜 다음 요소로 넘어갑니다.
- 반대로 순서가 잘못된 경우, 임시 변수 'temp'를 사용해 두 요소의 값을 서로 교환(swap)하고, index를 1 감소시켜 이전 위치로 되돌아갑니다. 이렇게 하면 방금 교환한 요소가 더 앞쪽 요소와도 올바른 순서인지 계속 검사할 수 있습니다.
main 메서드 설명
main 메서드에서는 { 34, 67, 89, 11, 0, -21 }과 같이 여러 값으로 구성된 배열을 선언합니다. 그런 다음 이 배열과 배열의 길이를 인자로 전달하며 'gnome_sort' 함수를 호출합니다. 정렬이 완료되면 Arrays.toString() 메서드를 사용해 배열의 내용을 문자열 형태로 변환하여 콘솔에 출력합니다.
실행 결과를 보면 음수를 포함한 무작위 배열이 [-21, 0, 11, 34, 67, 89]처럼 오름차순으로 깔끔하게 정렬된 것을 확인할 수 있습니다. 그놈 정렬은 최악의 경우 시간 복잡도가 O(n²)이지만, 코드가 간결하고 추가 메모리가 거의 필요 없다는 장점이 있어 학습용 알고리즘으로 적합합니다.