[알고리즘] 선택정렬(Selection Sort)

이번 시간에는 정렬시리즈의 첫 주제 "선택정렬"을 공부해 보겠습니다. 딱딱하게 설명하기 보다는 이야기하는 방식으로 선택정렬을 설명해 보겠습니다 !

 

선택정렬은 최소값을 앞으로 땡겨서 정렬하는 방법입니다. 최소값을 앞으로 떙기다뇨? 무슨 말인가요. 이는 "선택"이라는 말을 잘 생각해보면 답이 나옵니다.

 

예를 들어서, 초등학교때 운동장에서 키순으로 학생들을 줄세울때 선생님이 영수를 보고, "영수야 너가 철수보다 키가 크니깐 자리 바꿔라", "영호야 너 호진이보다 키 크니깐 호진이하고 자리 바꿔라" 이런식으로 한 사람을 기준으로 나머지 친구들을 비교하면서 자리를 바꾸는 방식이 선택정렬 입니다. 즉, 현재 기준보다 작거나, 큰 값을 "선택"해서 값을 바꾼다는 말이죠.

 

그러면 이제 1,6,4,7,2,8,10이라는 숫자를 오름차순으로 정렬을 해보겠습니다. 

먼저 1이 기준입니다. 1을 제외하고 나머지 숫자중에서 1보다 작은 놈들을 찾는거죠.

1과 6을 비교합니다. 1이 더 작네요. 6은 패스 !        

1과 4를 비교합니다. 1이 더 작네요. 4는 패스 !

........

10까지 비교했는데 1이 제일 작네요. 1은 고정입니다.

 

 

다음 기준은 6입니다. 

6과 4를 비교합니다. 4가 더 작네요. 그렇다면 min값은 4가 됩니다(현재 4가 제일 작습니다)

4와 7을 비교합니다. 7이 더 크네요. 7은 패스 !

4와 2를 비교합니다. 2가 더 작네요. 그렇다면 min 값은 2가 됩니다(현재 2가 제일 작습니다)

.....

10까지 비교해도 2보다 작은 값을 없네요.

그렇다면 기준값(6)과 min값(2)를 바꿔줍니다. 그럼 다음과 같이 정렬이 되겠네요 !

 

 

이와 같은 방식으로 현재 기준에서 나머지 값들을 하나씩 비교한 다음에 나보다 작은 값이 있으면 그 값과 나의 값을 바꾸는 것입니다. 

위에서 설명한 것처럼, 선생님이 학생들을 세워놓고 영수를 기준으로 나머지 학생들에서 가장 키가 작은 친구를 영수와 교체함으로써 키 순으로 정렬하는것과 같은 원리입니다.

 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       int[] ary = {1,5,6,2,7,8,10,21};
       
       int minIndex;
       
        for(int a=0;a<ary.length-1;a++){
          minIndex=a;
          for(int b=a+1;b<ary.length;b++){
            if(ary[minIndex]>ary[b]){
              minIndex=b;
            }
          }
          
          int temp;
          temp=ary[a];
          ary[a]=ary[minIndex];
          ary[minIndex]=temp;
        }
       
       for(int r:ary){
         System.out.println(r);
       }
    }
}

총 2중 for문으로 선택정렬을 구현하는데, 바깥 for문은 기준값을 결정하고 안쪽 for문은 기준값과 비교할 나머지 숫자들 입니다.

그리고 maxIndex라는 변수가 나오는데, 이는 기준값보다 작은 값이 나왔을 때 그 값의 index를 저장하는 변수입니다. 

 

왜 index를 변수하냐면, 나중에 더 작은 값이 나올 수 있기 때문입니다. 그래서 기준값보다 더 작은 숫자가 나오게 되면 먼저 maxIndex에 저장하고(이 값은 ary[maxIndex]의 값보다 더 작은 값이 나오면 바뀔 수 있습니다) 안쪽 for문이 끝나면 즉, 한번 다 찾아봤으면 자리를 바꿔줍니다. 이떄는 임시변수 temp를 사용합니다.

 

특히 주의할 점은, 바깥쪽 for문의 a의 범위와 안쪽 for문 b의 시작점 입니다.

1,5,6,2,7,8,10,21에서 바깥쪽 for문의 a 값은 1,5,6,2,7,8,10의 값을 가질 수 있습니다. 그리고 안쪽 for문의 b값은 5,6,2,7,8,10,21값을 가질 수 있습니다.

a의 경우 배열의 마지막 인덱스-1값과 마지막 인덱스 값을 비교하기 위해서 입니다. 마지막 값과 마지막 값을 비교하는 것은 의미가 없겠죠 ?

b의 경우 기준값 다음에 있는 값부터 시작하는데, 이는 당연합니다. 나를 제외하고 나머지 값들을 비교해야 하니깐요(여기서 나머지 값들은 기준값 기준으로 오른쪽 값들을 의미합니다)

 

그렇다면 선택정렬의 시간복잡도는 어떻게 될까요 ?

먼저 기준값을 찾는데 O(n)번이 걸립니다. 그리고 이 기준값을 기준으로 최솟값은 n번 찾아야 하기 떄문에 결국에 O(n^2)의 시간이 걸리게 됩니다.