230327 선택정렬 연습

선택 정렬

예시 이미지, 출처 구글 검색

얘를 오름차순 정렬을 한다고 하면,

절차

 

1. 지금 내가 찾을 자리를 정한다.(맨 왼쪽을 찾는다고 가정하면)

2. 일단 가장 작은 수를 찾는다.(아무것도 하지 않고)

3. 가장 작은 수인 9를 찾았다. 그렇다면 13과 swap. 9의 위치는 고정

4. 다음 자리의 수인 46을 기준으로 오른쪽에 있는 수 중에서 가장 작은 수를 찾는다.

5. 13을 발견했으면, 대소비교 후 작은 수인 13과 swap 한다. 13의 위치는 고정.

6. 세 번째, 네 번째, 마지막 자릿수까지 동일한 방식으로 비교하고 swap하고 고정한다.

 

기존 선택정렬 개념

.

-----------------

 

그런데 수업시간에 다룬 코드 첫번째에서는

하나의 기준을 잡고 모든 걸 다 비교하는 코드다.

for(int i = 0;i<a.length;i++) {
    for(int j = 0;j<a.length;j++) {
         if(a[i] < a[j]) {
             int temp = a[j];
             a[j] = a[i];
             a[i] = temp;
         }
    }
}

 

어떤 느낌이냐면, 위 그림을 다시 가져왔을 때,

예시 이미지, 출처 구글 검색

첫 줄(첫번째 자리에 들어갈 값)

1. 13과 46 비교 => 13이 더 작아서 그대로

2. 13과 24 비교 => 13이 더 작아서 그대로

3. 13과 52 비교 => 13이 더 작아서 그대로

4. 13과 20 비교 => 13이 더 작아서 그대로

5. 13과 9 비교 => 9가 더 작으므로 swap --> 9 46 24 52 20 13 순

 

둘째 줄(두번째 자리에 들어갈 값)

1. 46과 24 비교 => 24가 더 작으므로 swap --> 9 24 46 52 20 13 순

2. 24와 52 비교 => 24가 더 작아서 그대로

3. 24와 20 비교 => 20이 더 작으므로 swap -> 9 20 46 52 24 13 순

3. 20과 13 비교 => 13이 더 작으므로 swap -> 9 13 46 52 24 20 순

 

이런식으로 일일이 하나하나 비교한다는 뜻...

약간, 비효율적인 코드라고 할 수 있음.

불필요한 swap이 일어나니까.

 

 

그런데, 구현하기는 편하다...?

이 정도 코드면 매우 간단한 편,

최댓값을 찾을 필요도 없이 일단 나보다 크면 자리를 바꾸는 거예요.

 

------------

지금  다시 원래 방법대로 해보면, 

(int[] numbers = {13, 46, 25, 52, 28, 9} 를 오름차순으로) 선택정렬한다고 했을 때

// 오름차순 정렬
// 아래 과정을 원소의 개수 만큼 만복한다.
// 지금 정렬할 자리를 지정한다.
// 지금 정렬할 자리를 기준으로 오른쪽을 보면서 가장 작은 값을 찾는다.
// 가장 작은 값과 지금 정렬할 자리를 swqp
// > 하나의 숫자가 정렬이 된다.

public class SelectSortSample {

  public static void main(String[] args) {

    int[] numbers = {13, 46, 24, 52, 20, 9};
    // 오름차순 정렬
    // 아래 과정을 원소의 개수 만큼 만복한다.
    for (int i = 0; i<numbers.length; i++) {
      // 지금 정렬할 자리를 지정한다. => i
      // 지금 정렬할 자리를 기준으로 오른쪽을 보면서 가장 작은 값을 찾는다. => for문

      int min = 100; // 최솟갑을 찾을 것이므로 최대한 큰 수를 처음에 상정
      // 값이 중요한 게 아니라, 사실 우리는 위치를 찾으려고 하는 것이므로, 위치도 중요.
      int minIndex = -1;

      for (int j = i+1; j<numbers.length; j++) {
        if (min > numbers[j]) {
          min = numbers[j]; // 값 대입
          minIndex = j; // 인덱스도 업데이트
        }
      }

      // 그런데, 여기서 하나 문제가 생김. 내가 최솟값이면 어떡해?
      // 그 경우 한번 고려해줘야 한다.
      if (minIndex == -1) {
        continue; // 건너뛴다.
      }

      // 가장 작은 값과 지금 정렬할 자리를 swqp
      // 임시변수 하나 생성하고 값 대입하고 서로 바꾸는 절차를 기억하라

      // 지금 우리는 numbers[i] <-> numbers[minIndex] 하려고 한다.
      int temp = numbers[i];
      numbers[i] = numbers[minIndex];
      numbers[minIndex] = temp; // 치환 완료됨.
      // > 하나의 숫자가 정렬이 된다,
    }

    // 츌력
    //System.out.println(Arrays.toString(numbers)); //훨씬 간단해짐.

    for (int i = 0; i< numbers.length; i++) {
      System.out.println(numbers[i]);
    }
  }

}

 

두 개를 비교해보면 강사님 코드가 훨씬 더 간단하지.

그래서 이 방법을 사용하지 않으셨을까 추측.

 

---------------

 

이제 수업시간에 다룬 조금 더 개선된 코드를 따져보자.

for(int i = 0;i<a.length-1;i++) {
     for(int j = i+1;j<a.length;j++) {
          if(a[i] > a[j]) {
              int temp = a[j];
              a[j] = a[i];
              a[i] = temp;
          }
     }
}

 

이건 i를 기준으로 오른쪽부터 찾고 있다.

처음 코드는 j가 클 때 swap을 했다면 (a[i] < a[j])

개선된 코드는 i가 클 때 swap을 한다. (a[i] < a[j])

 

이건 바로 위에서 다뤘던 선택정렬 구현 정형화된 방식과 유사함.

 

일일이 경우의 수 따져보기는, 다음 게시글에서!