[HackerRank]Insertion Sort - Part 1

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

Insertion Sort - Part 1 | HackerRank

삽입 정렬 문제

배열의 가장 끝에 있는 원소를 대소관계를 비교하여 정렬하는 문제

 

삽입 정렬의 알고리즘은 다음과 같다.

어떤 원소를 대소 비교 하면서 그 위치가 될때 까지 for문을 돌리고 그리고 그 위치에 해당하면 for문에서 나와서 그곳에 집어 넣어 준다.

원래는 배열의 모든 원소들을 해줘야 하는데 이 문제는 가장 끝 원소만 삽입 정렬을 하면 되었다.

따라서 for문을 두번 돌리지 않고 한번만 돌려서 끝에서 두번째 원소부터 해당 원소를 비교를 하여 만약 해당원소가 위치를 찾거나 아니면 모든 원소를 다 돌았을때 해당 위치를 못 찾았을 경우, 즉 해당 원소가 가장 작을 경우에는 for문을 빠져나와 arr[i+1]에 해당원소를 넣어 준다.

i+1을 하는 이유는 다음과 같이 생각해 볼수 있다.

1. arr[i]<val

이런 경우 arr[i+1]에 넣어준다. 원래 arr[i+1]에 위치하던 원소는 arr[i+2]에도 위치하기 때문에 arr[i+1]에 val를 넣어도 문제가 없다.

2. i<0

이런 경우는 val이 가장 작은 경우이다. val이 가장 작을 경우에는 i=0에서 -1된채로 for문을 빠져나온다. 따라서 이 경우에는 arr[i+1]을 해줘야 한다.