[알고리즘] 정렬(3) - 선택 정렬

선택 정렬(Selection Sort)

 

정렬 방식

• 리스트의 범위 안에서 최솟값을 찾아 맨 앞으로 보내면서 정렬하는 방식이다.

정렬 과정

• 해당 예제에서는 오름차순으로 한다.
• 리스트의 정해진 범위 안에서 최솟값을 찾는다.
  • 처음에는 리스트 전체를 탐색하고, 이후 패스마다 앞부분(이미 정렬된 부분)을 제외하고 탐색 범위를 줄인다.
• 찾은 최솟값을 현재 범위의 첫 번째 값과 교체한다.
• 탐색 범위를 하나씩 줄이며 이 과정을 반복한다.

 

 

 

선택 정렬 성능

최악의 경우

맨 앞부분부터 최솟값을 채워나가는데, 각 루프마다 최솟값을 찾기 위해 (위치가 확정되지 않은 요소들 수)-1만큼 비교를 수행한다.

$$ (n-1)+(n-2)+...+2+1 = n(n-1)/2 => O(n^2) $$

$$ ∵ 시간 복잡도: O(n^2) $$

 

최선의 경우

최선의 경우도 최솟값들을 찾기 위해 최악의 경우와 같이 (위치가 확정되지 않은 요소들 수)-1만큼 비교를 수행한다.

$$ (n-1)+(n-2)+...+2+1 = n(n-1)/2 => O(n^2) $$

$$ ∵ 시간 복잡도: O(n^2) $$

 

결국 선택 정렬은 최솟값을 계속 찾기 위해 리스트 요소들을 순회하기 때문에 어떤 경우에도 비교횟수는 변하지 않는다.

그래서 시간 복잡도는 O(n^2)로 고정된다.

 

코드 - [언어: C]

#include <stdio.h>

int main() {
    
    int data[] = {8,5,2,6,9,3,1,4,0,7};
    int length = sizeof(data) / sizeof(data[0]);
    int min_idx = -1;
    int temp;
    
    // 선택 정렬
    for(int i = 0; i < length-1; i++){
        min_idx= i;
        // 최솟값 찾기
        for(int j =i+1; j < length; j++){
            if(data[min_idx] > data[j]){
                min_idx = j;
            }
        }
        // swap
        temp = data[i];
        data[i] = data[min_idx];
        data[min_idx] = temp;
    }
	
    // 정렬된 데이터 출력
    for(int i = 0 ; i < length; i++){
        printf("%d ", data[i]);
    }
    printf("\n");

    
    return 0;
}

 

 

그림 참고

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