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

 

 

https://hyejin.tistory.com/1239

자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 응급실

-> 이전 문제 풀이 

 

 

 

1. 선택 정렬 

설명

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

정렬하는 방법은 선택정렬입니다.

 

입력

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

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

 

출력

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

 

예시 입력 1 

6
13 5 11 7 23 15

 

예시 출력 1

5 7 11 13 15 23

 

 

문제 풀이 1

public int[] solution(int n, int[] arr)
{
   for (int i = 0; i < n; i++)
   {
      int idx = 0;
      int min = Integer.MAX_VALUE;
      for (int j = i ; j < n; j++)
      {
         if (arr[j] < min) {
            min = arr[j];
            idx = j;
         }
      }
      int tmp = arr[i];
      arr[i] = min;
      arr[idx] = tmp;
   }
   
   return arr;
}

👩‍💻 : 우선 선택 정렬은 이중 for문을 돌면서 i 값은 고정시키고 그 다음 j 가 배열을 돌면서 arr[i] 과 arr[j] 비교해서 더 작은 값의 인덱스 값을 idx 에 저장한다. 

그 다음에 tmp 변수를 하나 두고, arr[i] 값과 arr[idx] 값을 서로 교환해주면 오름차순으로 정렬된다 ! 

나는 min이라는 변수도 두어서 최솟값을 min에 넣어줬는데... idx 값만 있어도 되는걸 이제 알았다 ㅋ 

 

 

 

문제 풀이 2

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

 

👾 : 강사님은 이중 for문을 돌 때, i 값은 0 부터 n-1전 까지만 돌게 했다. 왜냐하면 i 가 굳이  n 까지 갈 필요가 없기 때문 !! (j가 돌면서 n 까지 가고 값을 비교 후 바꿀 것이기 때문) 

 

그리고 j는 i + 1 부터 n 까지 돌는데 이때 idx 값은 i 값을 저장해둔다. 

그 다음 arr[j] 와 arr[idx] 값 중  더 작은 값을 idx 에 인덱스 값을 저장하고, 

두번째 반복문을 다 돌고나서 , tmp 변수를 두어 arr[i]와 arr[idx] 값을 서로 바꿔주면 

 

오름차순 정렬로 된다 !