[알고리즘 이론] 정렬 Sort - 2-3. 비교 기반 알고리즘 (삽입 정렬)

정렬 Sort
1. 기본 개념
2. 비교 기반 알고리즘

   1) 선택 정렬
   2) 버블 정렬
   3) 삽입 정렬
   4) 셸 정렬

---

💡예시에 대한 가정
- 입력 크기 n
- 입력 배열 A[0…. n-1]
- 입력 데이터 : 양의 정수
- 정렬 방식 : 오름차순 (1, 2, 3, 4,…)

 

2-3) 삽입 정렬 (Insertion sort)

• 주어진 데이터를 하나씩 뽑은 후,
  이미 나열된 데이터들이 항상 정렬된 상태를 갖도록 바른 위치를 찾아 뽑은 데이터를 삽입해서 나열하는 방식
• 정렬 부분 A[0…k-1] 과 미정렬 부분 A[k…n-1] 으로 구분해서 처리
• 정렬 과정
  1. 미정렬 부분 A[k…n-1]에서 1번째 데이터를 뽑아
  2. 정렬 부분 A[0…k-1]에서 올바른 자리에 삽입

입력 데이터 A [10, 30, 40, 20, 70, 50, 60]

 

1️⃣. 입력데이터를 정렬부분과 미정렬 부분으로 나눈다.

 

2️⃣. 미정렬 부분의 첫번째 데이터 20을 뽑는다.

3️⃣.  뽑힌 데이터 20을 정렬부분의 가장 오른쪽 (=정렬 부분의 가장 큰 값, 20과 가장 인접한 쪽)부터 비교하여 진입한다.

 

4️⃣.  비교할 데이터가 20보다 작으면 교환하지 않고 단계를 종료한다.

 

5️⃣.  2️⃣ ~ 4️⃣ 과정을 반복한다.

 

 

 

 

 

 

 

3. 특징

• 성능 : O(n²)
• 제자리 정렬 알고리즘 : 입력 배열 A 이외 상수개(i, j, val) 의 저장 공간만 필요
• 안정적 정렬 알고리즘
• 입력 데이터의 원래 순서에 민감
  • 역순의 경우에는 O( n²)
  • 제 순서대로 거의 정렬되었으면 O(n)

 

 

[JS code]

function insertionSort(A) {
    const n = A.length; 

    for (let i = 1; i < n; i++) { // 1, …, (n-1)까지 (n-1)번 반복. A[0] 정렬 부분이므로 건너뜀
    
        let val = A[i]; // 미정렬 부분 첫 번째 데이터를 선택. val에 대입
        
        for (let j = i; j > 0 && A[j - 1] > val; j--) { // 정렬된 부분에서 비교를 시작합
        
            A[j] = A[j - 1]; // 정렬 부분의 A[j-1]이 val보다 크면 뒤로 한 칸 이동
        }
        
        A[j] = val; // 찾아진 위치에 선택된 데이터를 삽입
    }

    return A;
}