[Java] 삽입정렬(Insertion Sort) 원리 이해하기

 

 

삽입 정렬의 개념은 매우 간단하다.

 

왼쪽의 요소와 크기를 비교하여, 더 큰 값을 오른쪽으로 옮기다 보면 자연스럽게 왼쪽부터 작은 수가 나열되는 방식이다.

하지만 삽입 정렬을 구현한 for문 안에 while문이 들어간 코드를 보고 있자니, 모든 과정이 직관적으로 이해되지는 않았다.

 

그래서 직접 포스트잇에 요소를 하나씩 적어가며, 모든 과정을 계산하고 흐름을 따라가 보았다.

특히 while문에 익숙하지 않다 보니, 조건이 충족되어 실행된 이후 j–로 인해 반복문의 조건이 다시 확인되는 과정을 놓치기 쉬웠다.

j– 이후에는 조건을 다시 확인하여 반복문을 계속 실행하거나 종료를 결정해야 하는데,

나는  j–가 실행된 직후 바로 while문을 벗어나 다음 코드를 적용하는 실수를 하곤 했다.

 

또 다른 실수로는, 요소를 이동한 후 원래 자리의 값을 적용하지 말아야 함에도 불구하고, 잘못된 값을 적용하는 경우가 있었다.

 

이러한 실수들을 겪으며, 내가 while문에서 놓치고 있던 과정과 흐름을 명확히 파악할 수 있었다.

덕분에 반복문의 실행 흐름과 조건 처리에 대한 이해를 더 깊게 다질 수 있었다.

 

---

힘든 성공..

j--는 비교를 위해 현재 인덱스의 바로 왼쪽으로 이동하며,
비교 대상은 항상 i번째 요소인 key 값이다.

즉, while 문 안에서 비교가 이루어지고, 
왼쪽 값이 key보다 클 경우 해당 값을 오른쪽으로 옮긴다.

이 과정에서 key 값은 변하지 않고 고정된 상태에서 비교와 이동 작업이 반복적으로 수행된다.

 

i번째 요소의 값(key)은 while 문이 끝난 후에 비로소 자리를 잡게 된다.

이때, key가 들어가는 위치는 while 문의 조건이 더 이상 충족되지 않는 지점
(즉, key보다 작은 값이거나 인덱스가 0보다 작은 위치) 바로 오른쪽이다.

결과적으로, key는 자신보다 작은 값 바로 오른쪽에 위치하며, 
key의 오른쪽에 있는 값들은 모두 key보다 큰 값들로 정렬된다.

이 원리에 따라 삽입 정렬이 이루어진다

---

 

삽입정렬의 개념

삽입정렬(Insertion Sort)은 배열을 정렬하는 간단한 알고리즘 중 하나로,

이미 정렬된 부분과 그렇지 않은 부분을 나누고, 정렬되지 않은 요소를 하나씩 정렬된 부분으로 삽입해 나가는 방식으로 동작한다.

 

• 핵심 아이디어

배열의 첫 번째 요소는 이미 정렬되었다고 가정하고, 두 번째 요소부터 시작하여 각 요소를 적절한 위치에 삽입한다.

 

 

삽입정렬을 사용하는 이유와 적합한 상황

삽입정렬은 간단하고 직관적이지만, 큰 데이터셋에는 적합하지 않다.
하지만 작은 데이터셋이나 정렬된 데이터에서는 매우 효과적이다.

• 장점

  1. 간단한 구현: 알고리즘이 직관적이고 간단하여 배우기 쉽다.

  2. 적은 데이터에서 효율적: 데이터의 크기가 작거나, 데이터가 거의 정렬된 경우 매우 빠르다.

  3. 제자리 정렬: 추가적인 메모리를 사용하지 않고 정렬이 가능하다.

 

• 적합한 상황

  - 데이터의 크기가 작을 때.

  - 데이터가 이미 정렬되어 있거나, 거의 정렬된 상태일 때.

  - 안정적인 정렬(Stable Sort)이 필요할 때.

 

삽입정렬의 논리적 흐름과 과정

1. 배열의 두 번째 요소부터 시작한다. (인덱스 1)

2. 현재 요소를 “키(key)“로 설정한다.

3. 키의 왼쪽 요소들과 비교하면서, 키보다 큰 값이 있다면 오른쪽으로 한 칸씩 이동시킨다.

4. 비교가 끝나면 키를 적절한 위치에 삽입한다.

5. 배열 끝까지 위 과정을 반복한다.

 

• 시간 복잡도:

   • 최악의 경우(역순 배열): O(n^2) 

   • 최선의 경우(이미 정렬된 배열): O(n)

   • 평균의 경우: O(n^2)

 

• 공간 복잡도: O(1) (제자리 정렬, 추가 공간 필요 없음)

 

---

삽입정렬의 자바 구현 예제

public class InsertionSort {
   public static void main(String[] args) {
      int[] array = {5, 2, 4, 6, 1, 3};
      
      System.out.println("정렬 전:");
      printArray(array);
      
      insertionSort(array);
      
      System.out.println("정렬 후: ");
      printArray(array);
   }
   public staic void insertionSort(int[] array) {
       // 두 번째 요소부터 시작
       for (int i = 1; i < array.length; i++) {
          int key = array[i]; //현재 요소를 키로 설정
          int j = i -1;
          
          // 정렬된 부분의 요소들과 키를 비교
          while (j >= 0 && array[j]> key) {
             array[j + 1] = array[j]; // 키보다 큰 값을 오른쪽으로 이동
             j--;
          }
          // 키를 적절한 위치에 삽입
          array[j + 1] = key;
       }
   }
   
   publid static void printArray(int[] array) {
      for (int num : array) {
          System.out.print(num + " ");
      }
      System.out.println();
   }
}

 

1. for (int i = 1; i < array.length; i++)

• 의미: 배열의 두 번째 요소(인덱스 1)부터 마지막 요소까지 반복을 시작한다.

• 이유: 삽입정렬은 배열의 첫 번째 요소를 이미 정렬된 상태로 간주한다.

           따라서 두 번째 요소부터 시작하여 정렬되지 않은 요소를 정렬된 부분에 삽입한다.

 

2. int key = array[i];

• 의미: 현재 요소(인덱스 i)를 “키(key)“로 설정한다.

• 이유: 키는 정렬된 부분에 삽입하려는 대상이다.

           이 키를 기준으로 왼쪽에 있는 정렬된 부분과 비교하며 삽입할 위치를 찾아야 한다.

 

3. int j = i - 1;

• 의미: 키의 바로 왼쪽에 있는 요소의 인덱스를 j에 저장한다.

• 이유: 키를 정렬된 부분과 비교하기 위해 시작점을 설정하는 과정이다. j는 정렬된 부분의 마지막 요소를 가리킨다.

 

4. while (j >= 0 && array[j] > key)

• 의미: 정렬된 부분(왼쪽)에 있는 요소들과 키를 비교하는 루프이다.

         • j >= 0: 정렬된 부분의 범위를 초과하지 않도록 조건을 설정한다.

         • array[j] > key: 정렬된 요소가 키보다 크다면, 해당 요소는 오른쪽으로 이동해야 한다.

• 이유: 삽입정렬의 핵심 동작으로, 키가 삽입될 적절한 위치를 찾는 과정이다.

 정렬된 부분의 요소 중에서 키보다 큰 값을 모두 오른쪽으로 이동시킨다.

 

5. array[j + 1] = array[j];

• 의미: 현재 요소(array[j])를 오른쪽으로 한 칸 이동한다.

• 이유: 키보다 큰 값을 오른쪽으로 밀어서 키가 들어갈 자리를 확보한다.

 

6. j--;

• 의미: 왼쪽으로 한 칸 이동하며 이전 요소를 계속 비교한다.

• 이유: 현재 요소를 처리한 후, 그보다 한 단계 더 왼쪽으로 이동해 다음 비교를 진행한다.

 

7. array[j + 1] = key;

• 의미: 키를 적절한 위치에 삽입한다.

• j + 1: 마지막으로 비교한 요소의 다음 칸이 키의 최종 위치이다.

• 이유: 키보다 작은 요소들은 이미 비교 및 이동이 완료되었으므로, 해당 위치에 키를 삽입하면 정렬된 상태가 유지된다.

---

 

while 문이란?
• while 문은 “조건이 참(true)일 때 계속 반복”하는 문법이다.
• 즉, “특정 조건이 맞으면 일을 반복하고, 조건이 틀리면 멈추는 것”이다.

int number = 3;

while (number > 0) { 
    System.out.println(number); 
    number--; 
}​

• 동작 과정
   1. 처음엔 number = 3, 조건 number > 0은 참이니까 출력하고 number--;로 숫자를 1 줄인다.
   2. 다시 조건을 확인. number = 2 → 조건 참 → 반복.
   3. 계속 반복하다가 number = 0이 되면 조건 number > 0은 거짓이니까 멈춘다.

 

삽입정렬의 while 문

 

이제 삽입정렬에 있는 while 문을 이해하자.

while (j >= 0 && array[j] > key) {
    array[j + 1] = array[j]; // 숫자를 오른쪽으로 밀어냄
    j--;                     // 왼쪽 숫자로 이동
}

왼쪽 숫자가 있고(j >= 0), 키보다 크다면(array[j] > key)”

왼쪽에 있는 더 큰 숫자를 오른쪽으로 밀고 j--;로 왼쪽으로 이동한다.

 

왜 j--;를 사용하는가?

j--;는 비교할 숫자를 바꾸기 위한 역할을 한다.

  • j는  비교 중인 숫자의 위치(인덱스)를 가리킨다.

  • j--;는 “다음으로 왼쪽 숫자를 비교하겠다”는 뜻이다.

 

 

 

 

---

1단계 : i = 1, key = 2

이 과정을 그림으로 설명

1. 초기 배열

   • 배열: [5, 2, 4, 6, 1, 3]

   • i = 1 (두 번째 요소부터 시작)

   • key = 2 (현재 정렬하려는 숫자)

   • j = 0 (비교 대상: key의 바로 왼쪽)

배열: [5, 2, 4, 6, 1, 3]
         ^
        j=0 (비교 시작)​

  i = 1이므로 key = 2.

  j = 0, array[j] = 5와 key를 비교한다.

2. 5 > 2 → 오른쪽으로 밀기:

배열: [5, 5, 4, 6, 1, 3]
         ^
        j=0​

5>2때문에 5를 오른쪽으로 이동.

 

3. j--;로 이동 (왼쪽으로 한 칸):

배열: [5, 5, 4, 6, 1, 3]
      ^
     j=-1 (더 비교할 숫자 없음)​

j--로 j = -1이 된다.

4. 키 삽입:

배열: [2, 5, 4, 6, 1, 3]​

j = -1이므로 더 이상 비교할 숫자가 없다.
 key = 2를 j + 1 = 0 위치에 삽입한다.

 

2단계: i = 2, key = 4

1. 비교 시작
• 배열: [2, 5, 4, 6, 1, 3]
• 설명:
   i = 2이므로 key = 4.
   j = 1, array[j] = 5와 key를 비교한다.

2 . 5 > 4 → 오른쪽으로 밀기
• 배열: [2, 5, 5, 6, 1, 3]
• 설명:
  array[j] = 5가 key = 4보다 크기 때문에 5를 오른쪽으로 이동.
   j--로 j = 0이 된다.

3. 2 < 4 → 비교 멈춤
• 배열: [2, 4, 5, 6, 1, 3]
• 설명:
  array[j] = 2는 key = 4보다 작으므로 비교를 멈춘다.
  key = 4를 j + 1 = 1 위치에 삽입한다.

 

 

3단계: i = 3, key = 6

1. 비교 시작
• 배열: [2, 4, 5, 6, 1, 3]
• 설명:
   i = 3이므로 key = 6.
   j = 2, array[j] = 5와 key를 비교한다.

2. 5 < 6 → 비교 멈춤
• 배열: [2, 4, 5, 6, 1, 3]
• 설명:
• array[j] = 5는 key = 6보다 작으므로 비교를 멈춘다.
• key = 6은 이미 올바른 자리에 있다.

 

 

4단계: i = 4, key = 1

1. 비교 시작
• 배열: [2, 4, 5, 6, 1, 3]
• 설명:
   i = 4이므로 key = 1.
   j = 3, array[j] = 6와 key를 비교한다.

2. 숫자 이동 과정
• 6 > 1 → [2, 4, 5, 6, 6, 3] → j = 2
• 5 > 1 → [2, 4, 5, 5, 6, 3] → j = 1
• 4 > 1 → [2, 4, 4, 5, 6, 3] → j = 0
• 2 > 1 → [2, 2, 4, 5, 6, 3] → j = -1

3. Key를 삽입
• 배열: [1, 2, 4, 5, 6, 3]
• 설명:
   j = -1이므로 더 이상 비교할 숫자가 없다.
   key = 1을 j + 1 = 0 위치에 삽입한다.

 

 

5단계: i = 5, key = 3

1. 비교 시작
• 배열: [1, 2, 4, 5, 6, 3]
• 설명:
  i = 5이므로 key = 3.
  j = 4, array[j] = 6와 key를 비교한다.

2. 숫자 이동 과정
• 6 > 3 → [1, 2, 4, 5, 6, 6] → j = 3
• 5 > 3 → [1, 2, 4, 5, 5, 6] → j = 2
• 4 > 3 → [1, 2, 4, 4, 5, 6] → j = 1

3. Key를 삽입
• 배열: [1, 2, 3, 4, 5, 6]
• 설명:
• array[j] = 2는 key = 3보다 작으므로 비교를 멈춘다.
• key = 3을 j + 1 = 2 위치에 삽입한다.

 

 

최종 결과

• 배열이 정렬된 상태: [1, 2, 3, 4, 5, 6]