섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 3. 삽입정렬

문제

• N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
• 정렬하는 방법은 삽입정렬입니다.

입력

• 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

• 오름차순으로 정렬된 수열을 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 삽입정렬을 사용하여 푸는 문제이다.

 

삽입정렬이란 아래와 같이 key 값과 그 앞의 모든 수를 비교하여 위치를 바꾸며 정렬하는 것을 말한다.

즉, i와 그 앞의 값들을 전부 비교해서 작은 값을 앞으로 보내는 것이다.

아래 이미지를 확인하며 수행 과정을 확인해보자.

---

먼저 삽입정렬의 1회차이다.

11과 7을 비교했을 때, 7이 11보다 작으므로 앞으로 간다. 이렇게 삽입정렬의 1회차가 끝이 난다.

2회차는 i와 j 위치를 바꿔서 i = 2, j = 1일때 확인해보면 5가 11보다 작으므로 앞으로 간다.

다음으로 i = 2, j = 0 을 비교해보면 5가 7보다 작으므로 앞으로 간다. 이렇게 2회차가 끝이 난다.

위 과정을 반복하며 정렬하는 것이 삽입정렬이다.

---

설계과정

1. 키가 되는 i는 1부터, j는 i - 1 부터 0까지 돌아야한다.

2. i와 그 앞에 있는 수들을 비교하며 작은 수를 앞으로 보낸다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int[ ] 형으로 메소드를 작성한다.

 

3. 1부터 N까지 도는 for문을 작성한다.

• 맨 처음 값은 비교할 수가 없으므로 1번째부터 돌린다.

4. 임의의 변수 tmp에 arr[ i ] 값을 저장한다.

• arr[i]가 자기 자리를 찾아 들어갈 수 있도록 임의의 변수 tmp에 저장한다.

5. i - 1 부터 0까지 1씩 줄면서 도는 for문을 작성한다.

• 삽입정렬이기 때문에 j는 i 바로 앞자리부터 맨 앞까지 돌며 i와 비교한다.

5. i번째 값보다 j번째 값이 크면 j 번째 값을 앞으로 변경한다.

• i번째 값보다 j번째 값이 크면 뒤에 있는 값이 크다는 의미이다.

5. 미리 저장했던 tmp 값을  j+1 자리에 넣음으로써 정렬한다.

• tmp는 맨 처음에 저장했던 arr[i] 값으로, 1회차에서는 1번째 값을 의미한다.
•  즉 가장 작은 값이 위치하는 인덱스에 해당 값을 넣는다는 의미이다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.