[알고리즘]삽입정렬(Insert Sort)

쉽게 설명하자면 새로운 카드를 가져와 손 안의 카드를 정렬하는 방법과 유사하다.

삽입정렬(Insertion Sort)는 2번째 원소부터 시작해 그 앞(왼쪽)의 원소들과 비교하여 원소를 뒤로 옮기고 지정된 자리에 자료를 "삽입" 하여 정렬하는 알고리즘이다.

#Process (Ascending 오름차순 기준)
1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

삽입정렬이 유리한 상황

• 거의 정렬된 데이터를 처리할 때.
• 작은 배열에서 정렬할 때.
• 실시간으로 데이터가 추가될 때 (예: 목록에 새 요소가 추가될 때마다 정렬이 필요할 경우).

---

.
.
.
다음은 데이터가 추가 됨 응용하여 내림차순으로 푼 예시다.

BOJ 25305번

2022 연세대학교 미래캠퍼스 슬기로운 코딩생활에 $N$명의 학생들이 응시했다.

이들 중 점수가 가장 높은 $k$명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.

커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다.

import java.util.Scanner;

public class Main3 {
	public static void main(String[] args) {
		
	Scanner sc = new Scanner(System.in);
	
	int N = sc.nextInt();
	int k = sc.nextInt();
	int[] score = new int[N];
	
	//입력
	for(int i = 0; i< N; i ++){
		score[i] = sc.nextInt();	
	}
	
	for(int i = 1; i < N; i++) {
		System.out.println(score[i] + " ");
		}
 		
	//내림차순으로 정렬 
	for(int i = 1; i< N; i++) {
		int temp = score[i];
		int pre = i-1;
		
		//정렬된 부분과 비교 하여 temp를 적절한 위치에 삽입
		while(pre >= 0 && score[pre] < temp) {
			score[pre + 1] = score[pre];
			pre--;
			
		}
			score[pre+1] = temp;
	}
		
	 System.out.println(score[k - 1]);
	
	 sc.close();
	
	}		
	
}

---

해당 문제에서 삽입정렬을 쓰는 이유?

삽입 정렬은 정렬 과정 중에서도 현재까지 정렬된 상태를 유지하기 때문에, 원하는 k번째 요소(커트라인)를 정렬이 끝나기 전이라도 알 수 있다.

예를 들어, 상위 k개의 요소가 정렬되었으면, 그때 바로 k번째 요소를 확인할 수 있습니다. 이는 전체 정렬이 완료되기 전에 결과를 얻을 수 있다는 점에서 해당문제에서 효율적인 방식이라고 볼 수 있다.
즉, 정렬 중에 원하는 결과가 나오면 바로 얻을 수 있는 장점.