[알고리즘] 선택정렬

package test_java;
 
import java.io.IOException;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        
        int[] arr= {4,2,5,6,1,3};
        selectSort(arr);
        
        for(int result : arr) {
            System.out.println(result);
        }
 
    }
    
        public static int[] selectSort(int[] arr) {
            
            for(int i=0 ; i<arr.length; i++) {
                for(int j=i+1; j<arr.length; j++) {
                    if(arr[i]>arr[j]) {
                        int temp = arr[i];
                        arr[i]=arr[j];
                        arr[j]=temp;
                    }
                }
            }
            return arr;
        }
    
}// CLASS END

예시 4 2 5 6 1 3

1) 4에서부터 가장 작은 수를 찾는다 

2) 4랑 1이랑 바꾼다 (1 2 5 6 4 3)

3) 2에서 다시시작한다, 없음으로 패쓰

4) 5에서 시작한다. 5랑 3이랑 바꾼다  (1 2 3 6 4 5)

....반복

1 2 3 4 6 5

1 2 3 4 5 6

*선택 정렬의 장점

- 데이터의 양이 적을 때 성능이 좋음

- 작은 값을 선택하기 위해서 비교는 여러번 수행되지만 교환횟수는 적음

*선택 정렬의 단점

- 100개 이상의 자료가 넘어가면 속도가 급격히 떨어져서 안좋음.

*복잡도 = O(n^2)

*비교 횟수

두 개의 for 루프의 실행 횟수

외부 루프: (n-1)번

내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번

T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)