[HackerRank]Insertion Sort - Part 2

https://www.hackerrank.com/challenges/insertionsort2/problem

Insertion Sort - Part 2 | HackerRank

part1에 이은 삽입정렬 문제이다.

part1 : https://hse06028.tistory.com/33

 

이번에는 모든 원소들에 대하여 삽입 정렬을 하면 된다.

알고리즘은 part1과 같다.

 

part1과 다른 점이 하나 있다면 모든 원소들에 대하여 정렬을 하면 된다는 것이다.

for문이 두개가 돌아간다.

가장 바깥의 for문은 삽입을 할 원소를 정한다. 

i=1부터 시작을 했는데 그 이유는 그 원소의 앞 원소들과 대소 비교를 진행해야 한다. 만약 i=0이면 대소비교를 할 수 없게 된다. 따라서 i=1부터 시작하는 것이다.

해당 원소를 val이라고 지정을 하고 두번째 for문이 돌아간다.

안쪽에 있는 for문은 part1과 같이 동작을 한다.(이 부분 설명은 생략)

그리고 arr[i+1]에 val를 넣어주면된다.(왜 i+1인지도 part1에서 설명했으니 생략)