[Do it! 알고리즘 코딩 테스트 자바] 삽입 정렬과 퀵 정렬 - 백준 11399 / 11004(8일차)

1. 삽입 정렬 (Insertion Sort)

• 개념: 미정렬 부분의 첫 원소를 정렬된 부분의 알맞은 위치에 끼워 넣으며 정렬을 확장하는 방식.
• 핵심 원리 (분기 조건): 대상 데이터가 앞의 정렬된 데이터보다 작을 때(Target < Sorted Data)만 위치 이동 이벤트 발생. 대상 데이터가 앞의 데이터보다 크거나 같다면 이벤트(반복문)에 진입하지 않고 그 자리에 머무름. 앞의 데이터들을 거꾸로 탐색하며 나보다 작은 값을 만나는 순간 즉시 탐색을 종료함.
• 시간 복잡도: 최선 O(N) (이벤트 미발생 시), 최악 및 평균 O(N^2)
• 자주 쓰는 상황: 데이터 크기가 작거나, 이미 거의 정렬되어 이동 이벤트가 적게 발생할 때.

 

2. 퀵 정렬 (Quick Sort)

• 개념: 기준점(Pivot)을 잡아 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하는 과정을 재귀적으로 반복하는 방식.
• 핵심 원리 (분기 조건): 조건에 따른 포인터 이동과 교차 시 스왑(Swap) 이벤트 발생. while(arr[start] < pivot) / while(arr[end] > pivot): 피봇과 같거나 조건에 어긋나는 값을 만날 때까지 포인터 이동 후 대기. 이때, 등호 부재가 핵심!
  • if(start <= end): 두 포인터가 멈춘 상태에서 아직 교차하지 않았다면 값을 스왑.
  • 스왑 직후 반드시 start++, end--를 통해 포인터를 강제로 전진시켜 무한 루프를 방지하고 다음 탐색을 이어감.
• 시간 복잡도: 평균 O(N log N), 최악 O(N^2)
• 자주 쓰는 상황: 무작위로 섞인 대규모 데이터를 빠르게 정렬할 때.

---

11399번: ATM (삽입 정렬 구현)

1. 주요 오개념 및 시행착오 (Pain Point)

• 배열 요소를 한 칸씩 밀어내는 작업을 별도의 반복문으로 분리해야 한다고 착각함.
• 중첩 반복문으로 인한 O(N^3) 확장을 우려하여, 삽입과 삭제가 직관적인 ArrayList의 remove(), add()를 대체재로 사용함.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 누적합 최소화를 위해 가장 작은 수부터 정렬해야 하는 그리디(Greedy) 문제임.
• 조건부 진입 로직: if (target < arr[j]) 조건일 때만 자리를 찾는 while문에 진입함. 진입 후에는 "자리를 찾는 탐색과 동시에 데이터를 뒤로 한 칸씩 덮어씌우는 작업(arr[j+1] = arr[j])"을 단일 while문 내에서 병행 처리하여 $O(N^2)$ 복잡도를 유지함.

3. 설계 통찰

• 삽입 정렬 탐색은 반드시 내 바로 앞 인덱스부터 '역방향(j--)'으로 진행되어야 함. 정렬된 구간이므로 타겟보다 작은 값을 만나는 즉시 이동을 멈추고 자리를 확정 지을 수 있기 때문임.

4. 구현상의 유의점 (Implementation Wisdom)

• ArrayList의 add(index, value)와 remove()는 내부적으로 System.arraycopy()를 실행하여 데이터를 뒤로 밀어내는 O(N)의 숨겨진 비용을 발생시킴.
• 순수 정렬 구현 시에는 메서드 호출과 복사 비용이 없는 기본 고정 배열(int[])을 사용하는 것이 최적화의 기본임.

---

11004번: K번째 수 (퀵 정렬 구현)

1. 주요 오개념 및 시행착오 (Pain Point)

• Pivot을 끝에 두는 방식(Lomuto)과 가운데 두는 방식(Hoare)이 혼재되어, 가운데 두는 방식에서 스왑 후 Pivot을 억지로 옮기려는 불필요한 로직(끝에 두는 방식에서 유효함)이 추가됨.
• 인덱스 이동 중 배열 범위를 벗어날 것을 우려하여 start_index <= N-1 등의 불필요한 방어 로직을 삽입함.
• Pivot을 '값'이 아닌 '인덱스'로 기억하여, 스왑 과정에서 기준점 자체가 뒤바뀌는 치명적 버그가 발생함.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 등호 없는 비교 조건: while(arr[start] < pivot)처럼 등호를 배제하여, Pivot과 같은 값을 만났을 때 억지로 멈춰 스왑을 유도함. 이를 통해 배열이 한쪽으로 극단적으로 쏠리는 최악의 상황(O(N^2))을 방지함.
• 스왑 후 포인터 이탈: if(start <= end) 스왑 완료 후, 제자리에 머물지 않고 start++, end--로 포인터를 이동시켜 무한 루프를 뚫고 다음 파티션으로 분할을 이어감.

3. 설계 통찰

• 가운데 Pivot 방식은 교환 과정에서 Pivot 데이터 자신도 자연스럽게 쓸려 다니며 제자리를 찾아가므로, 최종 위치에 강제로 삽입할 필요가 없음. -> 끝에 두는 것보다 효율적임
• 자동 브레이크 시스템: 배열 내부에 존재하는 '실제 값'을 Pivot으로 삼았으므로, 포인터가 탐색하다가 최소한 Pivot 본래 위치에서는 조건문이 False가 되어 무조건 정지함. 따라서 IndexOutOfBounds를 막기 위한 인덱스 범위 체크 로직이 필요하지 않음.

4. 구현상의 유의점 (Implementation Wisdom)

• Pivot 설정 시 인덱스가 아닌 값 자체(int pivot = arr[mid])를 변수에 복사해 고정해야 기준점이 흔들리지 않음. 인덱스로 하면 인덱스는 맞지만 값이 바껴 무한루프에 빠질 수 있음!!
• 반복 횟수가 극단적으로 많은 퀵 정렬 루프 내에서는 범위 체크(start_index <= N-1) 등 수학적으로 불필요한 검증 로직을 과감히 제거해야 실질적인 실행 속도 최적화가 이루어짐.