[정렬 알고리즘] 두 배열의 원소 교체 2. 삽입 정렬로 풀어보기

📝 삽입 정렬 (Insertion Sort)

현재 데이터를 적절한 위치에 삽입하는 정렬이다.
자신보다 왼쪽에 있는 데이터는 정렬되어있다고 가정한다.

1️⃣ 순서

var data = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
1. 1번째 데이터가 정렬되어 있다고 판단하고 2번째 데이터부터 탐색한다.
	data[0] = 7 <-> data[1] = 5
2. 이 때, 0번째 인덱스의 왼쪽 or 오른쪽 어디에 삽입될 지 그것만 판단한다.
	data[0] = 5가 삽입된다면 자연스럽게 data[1] = 7이 된다.
3. 나머지도 반복한다.
	data[2] = 9는 현재 data[1]보다 크기 때문에 그대로 있는다.
	data[3] = 0은 앞에있는 5, 7, 9 보다 작기 때문에 data[0]번째에 삽입한다.
	data[4] = 1, data[1]에 삽입한다.
	.
	.

2️⃣ 코드

var array = [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
for i in 1 ..< array.count {                    // 1. 1부터 배열 끝까지 탐색
    for j in stride(from: i, to: 0, by: -1) {   // 2. i부터 0까지 -1씩, 왼쪽 탐색
        if array[j] < array[j - 1] {            // 3. 현재 값이 왼쪽 값보다 작다면 이동
            array.swapAt(j, j - 1)
        } else {                                // 4. 왼쪽 값이 나보다 작다면 멈춤
            break
        }
    }
}

3️⃣ 정리

• 안정성 : Stable Sort
  - 비교대상의 원소가 새로운 원소보다 큰 경우에만 움직이므로 동일한 값의 위치는 변하지 않는다.
• 제자리성 : In-place
  - 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도
  - 최선 : 𝛰(𝛮)
  - 최악 : 𝛰(𝛮 ²)
  - 최악의 경우 선택 정렬과 비슷하나 거의 정렬 된 문제 라면 퀵 정렬보다 빠르다.

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건
1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예

5 3
1 2 5 4 3
5 5 6 6 5

출력 예

26

🌀 풀이

// 삽입 정렬
func insertionSort(_ array: inout [Int], _ oper: String) {
    if (oper == "<") || (oper == "") { // 오름차순
        for i in 1..<array.count {
            var j = i
            while (j > 0) && (array[j] < array[j-1]) {
                array.swapAt(j, j-1)
                j -= 1
            }
        }

    } else if oper == ">" { // 내림차순
        for i in 1..<array.count {
            var j = i
            while (j > 0) && (array[j] > array[j-1]) {
                array.swapAt(j, j-1)
                j -= 1
            }
        }
    }
}

insertionSort(&a, "<")
insertionSort(&b, ">")
print("답 : \(exchange(&a, &b, k).reduce(0, +))")

여기서도 "<"와 ">"를 이용하여 오름차순, 내림차순을 구분해주었다.
코드가 예쁘진 않지만 🥲 일단 다음 퀵 정렬로 넘어가자..! 🧐

🫥 글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다! 궁금하다면 여기를 눌러주세요.