[이것이 코딩 테스트다 with Python] 22강 삽입 정렬

https://www.youtube.com/watch?v=DRkL5EBZ7KY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=22

 

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다

---

삽입 정렬 동작 예시

• [Step 0] 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로
  들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다

• [Step 1] 이어서 '9'가 어떤 위치로 들어갈지 판단한다

• [Step 2] 이어서 '0'이 어떤 위치로 들어갈지 판단한다

• [Step 3] 이어서 '3'이 어떤 위치로 들어갈지 판단한다

• 이러한 과정을 반복하면 다음과 같이 정렬이 완료된다

---

삽입 정렬 소스코드 (Python)

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

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

실행 결과

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

---

삽입 정렬 소스코드 (Java)

import java.util.*;

public class Main {

    public static void main(String[] args) {

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

        for (int i = 1; i < n; i++) {
            // 인덱스 i부터 1까지 감소하며 반복하는 문법
            for (int j = i; j > 0; j--) {
                // 한 칸씩 왼쪽으로 이동
                if (arr[j] < arr[j - 1]) {
                    // 스와프(Swap)
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
                // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                else break;
            }
        }

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

실행 결과

0 1 2 3 4 5 6 7 8 9

---

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N²) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다
  • 최선의 경우 O(N) 의 시간 복잡도를 가진다
  • 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까?