Insertion sort (삽입 정렬)

 

❒ Description

---

삽입 정렬의 구현방법을 정리하자.

 

 

 

 

 

❒ Insertion sort 

---

1. 동작 방식

삽입 정렬은 target 값과 그 이전 요소들을 비교하면서, `target < 이전 요소` 인 경우에 swap하는 방식이다.  

 

2. 특징

• 내부 정렬 : 추가적인 배열을 사용하지 않고 원래 배열 내에서 정렬이 이루어진다.
• 안정 정렬 : 같은 값의 원소들 간의 순서가 보존된다.
• 온라인 정렬 : 정렬 과정 중 새로운 데이터를 처리할 수 있다.

 

3. 장단점

• 장점
  • 거의 정렬된 데이터에서 매우 효율적이다.
  • 적은 데이터에 적합하다.
  • 추가 메모리 사용이 없다.
• 단점
  • 비효율적 : 대규모 데이터에서는 비효율적이다.
  • 데이터가 역순의로 정렬된 경우 성능이 저하된다.

 

4. 시간 복잡도

Best	O(n)
Average	O(n²)
Worst	O(n²)

 

 

 

 

 

❒ Insertion sort 구현 

---

// int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

public int[] insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int target = nums[i];
        int beforeIdx = i - 1; // target 바로 이전 원소의 index
        while (beforeIdx >= 0 && target < nums[beforeIdx]) {
            // swap 진행
            nums[beforeIdx + 1] = nums[beforeIdx];
            nums[beforeIdx] = target;
            beforeIdx --;
        }
    }
    return nums;
}

 

※ 정렬 과정
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

i = 1 ) [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
i = 2 ) [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
i = 3 ) [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
i = 4) [0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
i = 5 ) [0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
i = 6 ) [0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
i = 7 ) [0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
i = 8 ) [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
i = 9 ) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

 

 

 

 

---