Java의 삽입 정렬(Insertion Sort)은 리스트의 각 항목을 하나씩 검사하며 정렬하는 알고리즘입니다. 현재 항목이 바로 앞의 항목보다 작으면 두 항목의 위치를 교환하고, 그렇지 않으면 그대로 둔 채 다음 항목으로 넘어갑니다.
컴퓨터는 반복문(loop)을 활용해 리스트의 모든 항목을 탐색하고 순서를 재배치하는 데 매우 효율적입니다.
프로그래밍에서는 리스트를 정렬하기 위한 몇 가지 표준적인 방법이 있는데, 이를 정렬 알고리즘(sort algorithm)이라고 부릅니다. 정렬 알고리즘은 리스트의 모든 항목을 읽어 들인 후, 미리 정해진 규칙에 따라 항목들을 정렬합니다. 그중 가장 널리 사용되는 알고리즘 중 하나가 바로 삽입 정렬입니다.
이 글에서는 Java로 삽입 정렬 알고리즘을 구현하는 방법을 단계별로 살펴보고, 예제를 통해 알고리즘의 동작 원리를 자세히 설명해 드리겠습니다.
Java 삽입 정렬이란?
삽입 정렬은 카드 게임에서 손에 든 카드를 정렬하는 방식과 매우 유사합니다. 리스트의 각 항목을 확인하고, 왼쪽에 있는 항목과 비교하여 필요하면 위치를 교환합니다. 교환 여부는 해당 항목이 앞선 항목들보다 큰지 작은지에 따라 결정됩니다.
잠시 카드 게임을 하고 있다고 상상해 보세요. 손에 든 카드를 정렬할 때 우리는 어떻게 할까요?
왼쪽부터 시작해 두 번째 카드가 정렬되어 있는지 확인합니다. 두 번째 카드가 첫 번째 카드보다 크면 제자리에 두고, 그렇지 않으면 한 칸 앞으로 이동시킵니다.
이 과정을 손에 든 모든 카드에 대해 반복하면, 결국 모든 카드가 올바른 순서로 정렬됩니다.
삽입 정렬은 언제 사용해야 할까?
삽입 정렬은 정렬해야 할 요소가 많지 않거나, 이미 대부분 정렬된 데이터에 가장 효과적입니다.
대량의 데이터를 정렬할 때는 병합 정렬(merge sort)처럼 더 효율적인 알고리즘이 존재하기 때문에, 항상 삽입 정렬을 기본 선택지로 삼을 필요는 없습니다. 다만 삽입 정렬은 버블 정렬(bubble sort)이나 선택 정렬(selection sort)보다는 효율적입니다.
또한 삽입 정렬은 구조가 단순한 정렬 알고리즘이기 때문에 프로그래밍 입문자가 학습하기에 매우 적합합니다.
삽입 정렬 동작 과정 살펴보기
카드 덱을 떠올리는 것보다 실제 프로그래밍 예제를 통해 이해하는 것이 더 직관적일 수 있습니다. 다음 리스트를 살펴보겠습니다.
| 8 | 6 | 3 | 9 |
삽입 정렬에서는 첫 번째 요소가 이미 정렬되어 있다고 가정합니다.
다음 단계는 리스트의 두 번째 항목을 첫 번째 항목과 비교하는 것입니다. 첫 번째 항목이 더 크다면, 두 번째 항목을 첫 번째 항목 앞으로 이동시킵니다.
이 예제에서 6은 8보다 작습니다. 따라서 6은 한 칸 뒤(앞쪽)로 이동하고, 8은 한 칸 뒤로 밀려납니다.
| 6 | 8 | 3 | 9 |
이제 세 번째 요소를 왼쪽 요소들과 비교합니다. 3이 8보다 작나요? 그렇습니다. 따라서 8을 오른쪽으로 한 칸 이동시킵니다.
| 6 | 3 | 8 | 9 |
3이 6보다 작나요? 역시 그렇습니다. 따라서 6도 이동시킵니다.
| 3 | 6 | 8 | 9 |
마지막으로, 리스트의 네 번째 항목(마지막 항목)이 앞의 모든 항목보다 큰지 비교합니다. 이 경우 9는 앞에 있는 8, 6, 3보다 모두 크므로 제자리에 그대로 둡니다.
지금까지 사용한 알고리즘의 절차를 정리하면 다음과 같습니다.
- 첫 번째 요소는 정렬되어 있다고 간주한다.
- 두 번째 항목을 왼쪽 항목과 비교한다.
- 현재 항목이 왼쪽 값보다 크면 제자리에 유지하고, 그렇지 않으면 왼쪽 값보다 작은 값을 만날 때까지 계속 왼쪽으로 이동시킨다.
- 모든 항목이 정렬될 때까지 위 과정을 반복한다.
이제 정렬된 배열이 완성되었습니다. 삽입 정렬은 한 번에 하나의 항목씩 처리한다는 점을 기억하세요. 그럼 Java로 이 알고리즘을 구현하는 방법을 알아보겠습니다.
Java로 삽입 정렬 구현하기
정렬 함수가 실행될 때마다 비교 중인 두 값 중 더 큰 값이 오른쪽으로 한 칸씩 이동합니다.
이론적으로는 이해했지만, 실제로 Java에서 어떻게 구현할까요? 학생 성적 리스트를 삽입 정렬로 정렬하는 클래스를 작성해 보겠습니다.
1단계: Arrays 라이브러리 준비
먼저 Java 프로그램에 Arrays 라이브러리를 임포트합니다. 이 라이브러리는 정렬이 완료된 후 리스트를 콘솔에 출력할 때 사용합니다.
import java.util.Arrays;
2단계: 정렬 메서드 선언
리스트를 순회하며 데이터를 오름차순으로 정렬하는 메서드를 선언합니다.
class SortGrades {
public static void insertionSort(int [] numbersToSort) {
int itemCount = numbersToSort.length;
for (int value = 1; value < itemCount; value++) {
int key = numbersToSort[value];
int last = value - 1;
while (last >= 0 && key < numbersToSort[last]) {
numbersToSort[last + 1] = numbersToSort[last];
--last;
}
numbersToSort[last + 1] = key;
}
}
}
먼저 입력 배열의 항목 개수를 구합니다. 이를 통해 리스트의 모든 항목을 순회하는 반복문을 만들 수 있습니다. for 반복문은 리스트가 정렬될 때까지 실행됩니다.
for 반복문 내부에는 key와 last라는 두 변수가 선언되어 있습니다.
key 변수는 현재 정렬 중인 항목을 추적하고, last 변수는 해당 항목 왼쪽에 정렬이 필요한 항목들의 인덱스를 추적합니다.
프로그램은 while 반복문 안에서 key의 값을 왼쪽의 각 요소와 비교하며, 더 작은 요소를 찾을 때까지 비교를 진행합니다.
3단계: main 메서드 정의
지금 상태로 코드를 실행하면 아무 일도 일어나지 않습니다. 아직 main 메서드를 정의하지 않았기 때문입니다. int 배열(숫자 배열)을 정의하는 main 메서드를 작성하고, 앞서 선언한 insertionSort() 메서드를 호출해 숫자를 정렬해 보겠습니다. 아래 코드를 insertionSort 메서드 선언 뒤에 추가하세요.
public static void main(String args[]) {
int[] numbers = { 8, 6, 3, 9 };
InsertionSort sortNumbers = new InsertionSort();
sortNumbers.insertionSort(numbers);
String arrayToString = Arrays.toString(numbers);
System.out.println("Sorted list: " + arrayToString);
}
main 메서드에서는 정렬할 숫자 리스트를 선언했습니다. 그리고 InsertionSort() 클래스의 인스턴스인 sortNumbers를 생성하고, 이를 통해 숫자 리스트를 오름차순으로 정렬합니다. 이 메서드는 별도의 배열을 새로 만들지 않고 기존 "numbers" 배열 내부의 값을 직접 변경합니다.
마지막으로 Arrays.toString() 메서드를 사용해 numbers 배열을 문자열로 변환한 뒤, 정렬된 리스트를 콘솔에 출력합니다.
시간 복잡도 분석
삽입 정렬의 평균 시간 복잡도는 O(n²)입니다. 이는 요소들이 무작위로 섞여 있을 때 나타나는 성능입니다.
최선의 경우, 즉 배열이 이미 정렬되어 있다면 시간 복잡도는 O(n)입니다. 이 경우 삽입 정렬의 내부 반복문이 전혀 실행되지 않기 때문입니다.
최악의 경우에는 O(n²)의 성능을 보입니다. 배열이 오름차순 또는 내림차순으로 정렬되어 있고, 이를 반대 방향으로 정렬해야 하는 상황이 여기에 해당합니다. 이 경우 모든 요소를 나머지 모든 요소와 비교해야 하기 때문입니다.
마무리
삽입 정렬은 데이터를 정렬하는 효율적인 방법 중 하나입니다. 삽입 정렬은 리스트의 두 번째 값부터 비교를 시작하며, 현재 값이 왼쪽 값보다 크면 리스트는 그대로 유지됩니다. 그렇지 않다면 왼쪽의 값이 자신보다 작아질 때까지 해당 값을 계속 이동시킵니다.
이제 여러분도 Java로 직접 삽입 정렬 알고리즘을 작성할 준비가 되었습니다. Java 학습을 더 깊이 있게 진행하고 싶다면 관련 학습 가이드를 참고해 보세요.