6-3. 단순 선택 정렬(Straight Selection Sort)

단순 선택 정렬

: 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

 

 

 

가장 작은 값의 요소인 1을 선택해 정렬 시작

 

 

1과 6을 교환

 

 

이어서 두 번재로 작은 요소인 3을 선택해 정렬

 

=> 아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택해 아직 정렬하지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복

 

 

 

 

[단순 선택 정렬의 교환 과정]

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값 (a[min])을 선택
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환
3. 이 과정을 n - 1회 반복

 

 

 

[알고리즘 개요]

for(int i = 0; i < n - 1; i++) {
	//min = a[i], ..., a[n - 1]에서 가장 작은 작은 값을 가지는 요소의 인덱스
   	//a[i]와 a[min]의 값 교환
}

 

 

 

[실습 코드]

static void selectionSort(int[] a, int n) {
        for(int i = 0; i < n - 1; i++) {
            int min = i;
            for(int j = i + 1; j < n; j++) {
                if(a[j] < a[min])
                    min = j;
            }
            swap(a, i, min);
        }
    }

 

 

 

 

 

한계

• 서로 떨어져 있는 요소를 교환하기 때문에 불안정
• 같은 값을 가진 요소가 있을 때, 두 요소의 순서가 뒤바뀜