# 삽입 정렬
## 삽입 정렬(insertion sort)
삽입 정렬은 배열의 각 데이터를 기준으로 좌측 지점을 탐색하여 데이터를 정렬 가능한 위치에 삽입하는 방식으로 정렬을 수행한다. 다음 순서에 따라 정렬을 수행한다.
1. 기준 위치의 데이터를 백업한다.
2. 기준 위치보다 좌측의 데이터와 비교하여 삽입 지점을 갱신한다.
3. 더이상 데이터가 없거나 기준 위치의 데이터보다 작은 데이터를 만날 경우 탐색을 중지하고 데이터를 해당 지점에 삽입한다.
4. 기준 위치를 다음 칸으로 변경한다.
5. 1번으로 이동한다.
### 샘플 데이터
정렬을 위해 사용할 데이터는 다음과 같다.
```java
int[] data = new int[]{30, 50, 20, 10, 40};
```
삽입 정렬은 모든 데이터를 한 번씩 기준으로 진행하므로 샘플 데이터의 길이만큼 5회차로 진행한다.
### 1회차
* 기준점 : data\[0] 좌측에 데이터가 존재하지 않기 때문에 수행할 내용이 없다.
### 2회차
* 기준점 : data\[1] data\[1] 지점의 50을 백업하고 좌측인 data\[0]과 비교하지만 앞의 데이터가 더 작기 때문에 위치 변경은 수행하지 않는다.
### 3회차
* 기준점 : data\[2] data\[2] 지점의 20을 백업하고 좌측인 data\[1], data\[0]과 비교하여 data\[0] 지점으로 삽입한다.
### 4회차
* 기준점 : data\[3] data\[3] 지점의 10을 백업하고 좌측인 data\[2], data\[1], data\[0]과 비교하여 data\[0] 지점으로 삽입한다.
### 5회차
* 기준점 : data\[4] data\[4] 지점의 40을 박업하고 좌측인 data\[3], data\[2], data\[1], data\[0]과 비교해야 하지만 data\[2]가 30이므로 data\[3] 지점에 삽입한다.
### 전체
```java
int[] data = new int[] {30, 50, 20, 10, 40};
//정렬
for(int k=0; k < data.length; k++) {
int index = k;
int backup = data[k];
for(int i=k-1; i >= 0; i--) {
if(backup < data[i]) {
index = i;
data[i+1] = data[i];
}
else {
break;
}
}
data[index] = backup;
}
//출력
for(int i=0; i < data.length; i++) {
System.out.println(data[i]);
}
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://docs.sysout.co.kr/base-language/java/beginner/array/sort/insertion.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.