2. 선택정렬

이번 시간에도 신나는 동영상부터 

출처 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택정렬의 핵심은 (나혼자 이해하기로) 최소값을 '선택'해서 다른 값들과 비교하고, 

현재 선택한 최소값이 비교값보다 크다면 그 비교값을 다시 최소값으로 선택하는 것

영상에서 일어나는 일을 좀 더 소스 친화적으로 풀어보자면 

[첫번째 루프]

[두번째 루프]

[세번째 루프]

이런 식으로 진행이 된다.

이걸 자바 소스로 풀어내면

public class SelectionSort {
 
    public SelectionSort(){}
    
    public String sort(int[] target){
        String after = "";
        int min, temp;
        
        for(int i = 0; i < target.length; i++){
            min = i;
            
            for(int j = i+1; j < target.length; j++){
                if(target[j] < target[min])
                    min = j;    
            }
            
            temp = target[i];
            target[i] = target[min];
            target[min] = temp;
            
        }
        
        for(int i = 0; i < target.length; i++){
            after += target[i] + "\t";
        }
        
        return after;
    } 
    
}

버블정렬과 다른 점이라면 내부 for문에서 비교하면서 바로 값끼리 교환하지 않고

내부 for문을 빠져 나와서 다음 루프를 돌기 전에 새로 선택된 최소값의 위치와 현재 선택된 원소의 위치를 교환해준다는 것

따라서 복잡도는 버블정렬과 같이 O(n^2)가 나오지만 실제로는 버블정렬보다는 쪼금 더 효율적이라고 할 수 있다.