섹션6. Sort - 3. 삽입 정렬

📌 문제 설명

N개의 숫자가 입력되면 삽입 정렬 알고리즘을 이용하여 오름차순으로 정렬한 결과를 출력하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 번째 줄: 자연수 N (1 ≤ N ≤ 100)
• 두 번째 줄: N개의 정수 (정수형 범위)

출력

• 오름차순으로 정렬된 수열 출력

---

🔸 예제 입력 & 출력

예제 입력 1

6  
11 7 5 6 10 9

 

예제 출력 1

5 6 7 9 10 11

 

---

💡 해결 방법

• 삽입 정렬은 두 번째 원소부터 시작해서
  앞쪽의 정렬된 부분에 현재 원소를 삽입하는 방식으로 정렬합니다.
• 현재 값보다 큰 값들은 한 칸씩 뒤로 밀어주고, 적절한 위치에 삽입합니다.

---

💻 코드 구현 (Java)

package partSort;

import java.util.Scanner;

public class Problem3 {
	public int[] solution(int n, int[] arr) {
		for(int i=1; i<n; i++) {
			int tmp = arr[i], j;
			for(j=i-1; j>=0; j--) {
				if(arr[j]>tmp) arr[j+1]=arr[j]; // 큰 값은 뒤로 이동
				else break; // 적절한 위치 찾았으면 중단
			}
			arr[j+1] = tmp; // 삽입 위치에 tmp 저장
		}
		return arr;
	}
	
	public static void main(String[] args) {
		Problem3 T = new Problem3();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		for(int x: T.solution(n, arr)) System.out.print(x+" ");
		kb.close();
	}
}

📖 코드 설명

1️⃣ 현재 삽입할 값 선택

for(int i=1; i<n; i++) { 
	int tmp = arr[i], j;

• 두 번째 원소(i=1)부터 시작해 정렬을 진행합니다.
• tmp에 현재 정렬 대상 값을 저장합니다.

---

2️⃣ 삽입 위치 찾기: 정렬된 부분과 비교

for(j=i-1; j>=0; j--) {
    if(arr[j]>tmp) arr[j+1]=arr[j];
    else break;
}

• 현재 위치보다 앞에 있는 요소들과 비교합니다.
• tmp보다 큰 값들은 한 칸 뒤로 이동시킵니다.
• 작거나 같은 값을 만나면 break로 중단하고 삽입 위치 확정.

---

3️⃣ 삽입 위치에 값 저장

arr[j+1] = tmp;

• 반복문을 빠져나온 후 tmp를 정확한 위치 j+1에 삽입합니다.
• 이로써 앞쪽은 정렬된 상태로 유지됩니다.

---

⏳ 시간 복잡도 분석

• 최악/평균: O(N²) (모든 요소가 뒤로 밀릴 수 있음)
• 최선(이미 정렬된 경우): O(N) (한 번도 이동하지 않음 → break)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런