Selection sort(선택 정렬)

선택 정렬

    - 앞에서부터 어떤 값을 넣을지 선택하는 알고리즘

 

 

 

동작

    - 주어진 리스트 중에서 최소값/최대값을 선택

    - 선택한 값을 정렬되지 않은 앞의 갑과 교체

    - 위 과정 반복

 

        * 예시

            + 1번 : 탐색하여 최소값 1를 찾고, 첫 번째 값과 교환

            + 2번 : 탐색하여 최소값 2를 찾고, 두 번째 값과 교환

            + 3번 : 탐색하여 최소값 3을 찾고, 세 번째 값과 교환

            + 이하 과정 동일

 

 

 

구현

void selectionSort(int *list, int n){
    
    // 최소값 인덱스, 임시 변수  
    int idx_min, tmp;
    
    for(int i=0; i<n-1; i++){
        
        idx_min = i;
        
        // i 이후 부터 값을 비교하면서 
        // 최소값을 찾으면 idx_min의 위치 바꿔주기  
        for(int j=i+1; j<n; j++){
            if(list[j] < list[idx_min])
                idx_min = j
        }
        
        // 최소값의 인덱스와 위치 바꾸기  
        tmp = list[idx_min];
        list[idx_min] = list[i];
        list[i] = tmp;
        
    }
}

 

 

 

비교

    - 버블 정렬 : 버블 정렬보다 평균적으로 빠름

        * 버플 정렬은 인접한 요소들과 항상 swap하지만 선택 정렬은 최소값/최대값과 swap하기 때문

 

    - 삽입 정렬

        * 선택 정렬과 마찬가지로 K번째 요소가 정렬된 순서대로 놓인다는 공통점

        * 선택 정렬은 K+1 요소를 찾기 위해서 나머지 모든 요소를 탐색하지만, 삽입 정렬은 K+1 요소만 탐색하기 때문에 삽입 정렬이 더 빠름

 

 

 

특징

    - 불안정 정렬

        * 안정한 정렬 : [8][4][5][7][8][2]라는 배열이 있을 때, [2][4][5][7][8][8]로 정렬되어 8의 위치가 그대로 유지

        * 불안정한 정렬 : [2][4][5][7][8][8]로 정렬되어 8의 위치가 뒤바뀜

        * 안정한 정렬을 선호하는 이유 : 온라인 쇼핑 목록에서 정렬할 때를 생각해 보자. 첫 번째로 최저가 순으로 나열하고, 두 번째로 리뷰 순으로 나열한다고 하자. 안정한 정렬일 경우에는 최저가에서 리뷰 순으로 나열된다. 불안정한 정렬일 경우에 두 번째인 리뷰 순으로 나열하는 순간 첫 번째로 해놓은 최저가 순 정렬은 무용지물이 된다.

 

    - 시간복잡도 : O(N^2)

 

 

 

참조

    - 위키피디아

    - 블로그 1

    - 블로그 2