Day09 선택정렬 예제 경우의 수 따지기

수업시간에 다룬 예제 첫번째

코드

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;
         }
    }
}
// 바깥쪽 반복문은 기준점이 될 하나의 숫자
// 안쪽 반복문은 하나의 숫자와 다른 모든 값을 반복하기 위해서 존재

예시

int[ ] a = new int[5]

a[0] = 6

a[1] = 8 

a[2] = 2 

a[3] = 4

a[4] = 5

라고 가정

 

결과값을 미리 밝히자면,

첫 번째 케이스 선택정렬 반복횟수에 따른 정렬 결과

 

동작 원리

* 바깥에 있는 고정 위치의 수 기준으로 안쪽이 다 돌고,

* 그 기준에 대한 비교가 끝났으면, 바깥쪽 수를 하나 증가시켜서 다 돌고(순서를 증가시키는 것)

 

일일이 다 적어보는 경우의 수

i = 0일 때

j = 0 이면 6 / 6 이므로 그대로

j = 1 이면 6 / 8 이므로 swap / 8 6 2 4 5

j = 2 이면 8 / 2 이므로 그대로

j = 3 이면 8 / 4 이므로 그대로

j = 4 이면 8 / 5 이므로 그대로

=> 1번째 반복 완료 후

a[0] : 8 / a[1] : 6 / a[2] : 2 / a[3] : 4 / a[4] : 5

 

i = 1일 때

j = 0 이면 6 / 8 이므로 swap / 6 8 2 4 5j = 1 이면 8 / 8 이므로 그대로

j = 2 이면 8 / 2 이므로 그대로

j = 3 이면 8 / 4 이므로 그대로 

j = 4 이면 8 / 5 이므로 그대로

=> 2번째 반복 완료 후

a[0] : 6 / a[1] : 8 / a[2] : 2 / a[3] : 4 / a[4] : 5

 

i = 2일 때

j = 0 이면 2 / 6 이므로 swap / 2 8 6 4 5 

j = 1 이면 6 / 8 이므로 swap / 2 6 8 4 5 

j = 2 이면 8 / 8 이므로 그대로

j = 3 이면 8 / 4 이므로 그대로

j = 4 이면 8 / 5 이므로 그대로

=> 3번째 반복 완료 후

a[0] : 2 / a[1] : 6 / a[2] : 8 / a[3] : 4 / a[4] : 5

 

i = 3일 때

j = 0 이면 4 / 2 이므로 그대로 

j = 1 이면 4 / 6 이므로 swap / 2 4 8 6 5

j = 2 이면 6 / 8 이므로 swap / 2 4 6 8 5

j = 3 이면 8 / 8 이므로 그대로

j = 4 이면 8 / 5 이므로 그대로

=> 4번째 반복 완료 후

a[0] : 2 / a[1] : 4 / a[2] : 6 / a[3] : 8 / a[4] : 5

 

i = 4일 때

j = 0 이면 5 / 2 이므로 그대로

j = 1 이면 5 / 4 이므로 그대로

j = 2 이면 5 / 6 이므로 swap / 2 4 5 8 6

j = 3 이면 6 / 8 이므로 swap / 2 4 5 6 8

j = 4 이면 8 / 8 이므로 그대로

=> 5번째 반복 완료 후

a[0] : 2 / a[1] : 4 / a[2] : 5 / a[3] : 6 / a[4] : 8

 

따라서

결과값 a[0] : 2 / a[1] : 4 / a[2] : 5 / a[3] : 6 / a[4] : 8

{2, 4, 5, 6, 8} 출력

 

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

수업시간에 다룬 예제 두번째

코드

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;
          }
     }
}

 

int[ ] a = new int[5]

a[0] = 9

a[1] = 7 

a[2] = 6 

a[3] = 3

a[4] = 1

라고 가정

 

이 역시 결과값을 미리 밝히자면

두 번째 케이스 선택정렬 반복횟수에 따른 정렬 결과

 

i = 0일 때

j = 0 이면 (자기랑 자기 같은 값이므로 굳이 보지 않겠다!)

j = 1 이면 9 / 7 이므로 swap 7 9 6 3 1 

j = 2 이면 7 / 6 이므로 swap 6 9 7 3 1

j = 3 이면 6 / 3 이므로 swap 3 9 7 6 1

j = 4 이면 3 / 1 이므로 swap 1 9 7 6 3

=> 1번째 반복 완료 후

a[0] : 1 / a[1] : 9 / a[2] : 7 / a[3] : 6 / a[4] : 3

 

i = 1일 때

j = 0 이면

j = 1 이면 (왼쪽은 이미 최솟값이므로 오른쪽에 있는 값만 보겠다!)

j = 2 이면 9 / 7 이므로 swap 1 7 9 6 3

j = 3 이면 7 / 6 이므로 swap 1 6 9 7 3

j = 4 이면 6 / 3 이므로 swap 1 3 9 7 6

=> 2번째 반복 완료 후

a[0] : 1 / a[1] : 3 / a[2] : 9 / a[3] : 7 / a[4] : 6

 

i = 2일 때

j = 0 이면 

j = 1 이면 

j = 2 이면

j = 3 이면 9 / 7 이므로 swap 1 3 7 9 6

j = 4 이면 7 / 6 이므로 swap 1 3 6 9 7

=> 3번째 반복 완료 후

a[0] : 1 / a[1] : 3 / a[2] : 6 / a[3] : 9 / a[4] : 7

 

i = 3일 때

j = 0 이면 

j = 1 이면 

j = 2 이면 

j = 3 이면 

j = 4 이면 9 / 7 이므로 1 3 6 9 7

=> 4번째 반복 완료 후

a[0] : 1 / a[1] : 3 / a[2] : 6 / a[3] : 9 / a[4] : 7

 

따라서

결과값 a[0] : 1 / a[1] : 3 / a[2] : 6 / a[3] : 9 / a[4] : 7

{1, 3, 6, 9, 7} 출력

 

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

두 개의 반복문 중 어떤 것이 더 효율적인 코드인지 보고싶다면,

count 횟수를 선언해서 출력해보면 된다.

public class SelectSort {

  public static void main(String[] args) {

    int[] a = new int[100_000];
    int cnt1 = 0; // 반복횟수 비교를 위해 일부러 선언

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

    int cnt2 = 0; // 반복횟수 비교를 위해 일부러 선언 22
    for (int i = 0; i < a.length - 1; i++) {
      for (int j = i + 1; j < a.length; j++) {
        cnt2++;
        if (a[i] > a[j]) {
          int temp = a[j];
          a[j] = a[i];
          a[i] = temp;
        }
      }
    }

    System.out.println("순진하게 구현했을 때(cnt1) : " + cnt1);
    System.out.println("============");
    System.out.println("불필요한 비교를 뺐을 때(cnt2) : " + cnt2);
  }

}

 

실행 결과

압도적으로 두 번째 개선된 코드가 더 효율적임을 알 수 있다.

 

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

또 다른 유의사항

두 코드를 비교했을 때,

바뀐 부분이 또 있다.

바로... 여기

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

 

바깥에 있는 for문 돌 때마다, 최솟값을 하나씩 찾았겠지.

그 말은 다섯개 중에 네 개의 최솟값을 찾으면, 나머지 하나는 자동으로 정렬이 된다는 뜻

 

그래서 두 번째 코드에서 경우의 수 따질 때, 반복 횟수가 첫 번째 코드보다 하나 적은 4회인 것.

(예를 들면, i=4인 경우라고 차면, i=4 값과 j=4 값은 자기 자신이므로 굳이 비교할 필요가 없잖아.)