자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 삽입 정렬

 

https://hyejin.tistory.com/1241

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 버블 정

-> 이전 문제 풀이 

 

 

 

3. 삽입 정렬 

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 삽입정렬입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

출력

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

 

예시 입력 1 

6
11 7 5 6 10 9

 

예시 출력 1

5 6 7 9 10 11

 

 

문제 풀이 1

public int[] solution(int n, int[] arr)
{
   for (int i = 1; i < n; i++)
   {
      int key = i;
      for (int j = i-1; j >= 0; j--)
      {
         if (arr[key] < arr[j]) {
            int tmp = arr[key];
            arr[key] = arr[j];
            arr[j] = tmp;
         }
         key--;
      }
   }
   
   return arr;
}

 

👩‍💻 : 우선 삽입 정렬이란 i가 1부터 시작하고, j는 i-1 부터 0까지 돌면서 정렬하는 것이다. 

나는 key 라는 변수를 하나 만들고 key에 현재 i 의 값을 담았다. 

그 후 두번째 for문 안에서 arr[key]와 arr[j]의 값을 비교해서 arr[j]가 arr[key]보다 작으면 그 값을 교환해줬고, key 의 값을 1씩 감소시켰다. 

정렬해준 다음 arr 를 리턴했다. 

 

 

 

 

문제 풀이 2

public int[] solution2(int n, int[] arr)
{
   for (int i = 1; i < n; i++)
   {
      int tmp = arr[i], j;
      for ( j = i - 1; j >= 0; j--)
      {
         if (arr[j] > tmp)
         {
            arr[j + 1] = arr[j];
         }
         else
         {
            break;
         }
      }
      arr[j + 1] = tmp;
   }
   
   return arr;
}

 

👾 :  강사님은 i가 1일때, j는 i-1 즉 0 까지 돌면서 tmp 라는 변수를 하나 만들고 tmp에는 arr[i] 의 값을 넣어두고, arr[i]와 arr[j]의 값을 비교한다. 이때 arr[j]가 tmp 보다 작으면 arr[j+1] 에 arr[j]의 값을 넣고 (자리 바꿈) 만약 arr[j]가 tmp보다 크면 break 해줬다. break 하면 두번째 반복문을 나와서 arr[j+1]에 tmp 값을 넣으면 된다. 

(두번째 반복문을 끝낸 arr[j+1] = tmp는 j가 -1 일때로 -1 + 1  즉, arr[0]에 tmp 값을 넣는 다는 것이다. )