![](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FrbC2i%2FbtrevZNuo9Q%2FjpHXjwNQkdcr2952HNBjA0%2Fimg.png)
알고리즘 | 삽입정렬(Insertion Sort) | 코드 설명
·
자료구조 + 알고리즘
삽입정렬이란? 어떤 숫자 배열이 Input으로 들어왔을 때, 뒤죽박죽인 그 수열을 오름차순으로 정렬해나가는 과정을 거칩니다. 결국 Output은 "오름차순 수열"로 "정렬"됩니다. 이때, 삽입정렬에서는 정렬시에 다음과 같은 방식을 따릅니다 "이미 정렬된 앞 원소들"과 "기준이 되는 수인 key"를 대소비교합니다. 그리고 key인 수를 "이미 정렬된 앞 수열"의 적절한 자리에 삽입합니다. 이때, 이미 정렬되어있는 앞 원소들과 key를 차례차례 대소비교해가며 삽입의 위치를 정합니다. 이러한 정렬 방식을 삽입정렬이라고 합니다. 예를 들어 3 8 5 2 1이라는 수열이 있다고 합시다. 왼쪽에서 오른쪽 방향으로 차례차례 수의 크기를 비교해나가며 정렬을 쭉 하게 됩니다. 어떤 수를 그 앞자리에 있는 수와 하나하나 ..