[Algorithm] Selection Sort

Unstable Sort

---

정렬 방식

- 정렬되지 않은 요소들에 대해서 일단 가장 좌측을 최솟값의 index라고 생각

9

17

1

2

12

6

 

▶ Round 1 (index 0)

인덱스	0	1	2	3	4	5
요소	9	17	1	3	12	6
정렬 여부	X	X	X	X	X	X

- 정한 index 다음 요소들로부터 진짜 최솟값 index를 찾아내기 (계속해서 index를 update해준다)

인덱스	0	1	2	3	4	5
요소	9	17	1	3	12	6
정렬 여부	X	X	X	X	X	X

- 진짜 최솟값의 index는 "2"니까 index(2)의 값과 index(0)의 값을 서로 교체

인덱스	0	1	2	3	4	5
요소	1	17	9	3	12	6
정렬 여부	O	X	X	X	X	X

- 이러면 0번째 요소는 정렬 완료

 

▶ Round 2 (index 1)

인덱스	0	1	2	3	4	5
요소	1	17	9	3	12	6
정렬 여부	O	X	X	X	X	X

---

인덱스	0	1	2	3	4	5
요소	1	3	9	17	12	6
정렬 여부	O	O	X	X	X	X

>> 0 ~ 1번째 요소들 정렬 완료

 

▶ Round 3 (index 2)

인덱스	0	1	2	3	4	5
요소	1	3	9	17	12	6
정렬 여부	O	O	X	X	X	X

---

인덱스	0	1	2	3	4	5
요소	1	3	6	17	12	9
정렬 여부	O	O	O	X	X	X

>> 0 ~ 2번째 요소들 정렬 완료

 

▶ Round 4 (index 3)

인덱스	0	1	2	3	4	5
요소	1	3	6	17	12	9
정렬 여부	O	O	O	X	X	X

---

인덱스	0	1	2	3	4	5
요소	1	3	6	9	12	17
정렬 여부	O	O	O	O	X	X

>> 0 ~ 3번째 요소들 정렬 완료

 

▶ Round 5 (index 4)

인덱스	0	1	2	3	4	5
요소	1	3	6	9	12	17
정렬 여부	O	O	O	O	X	X

---

인덱스	0	1	2	3	4	5
요소	1	3	6	9	12	17
정렬 여부	O	O	O	O	O	X

>> 0 ~ 4번째 요소들 정렬 완료

 

▶ Round 6 (index 5)

인덱스	0	1	2	3	4	5
요소	1	3	6	9	12	17
정렬 여부	O	O	O	O	O	X

---

인덱스	0	1	2	3	4	5
요소	1	3	6	9	12	17
정렬 여부	O	O	O	O	O	O

>> 0 ~ 5번째 요소들 정렬 완료

>> 최종적으로 정렬이 완료되었다

 

---

Selection Sort 특징

결국, 앞에서부터 차례대로 최솟값이 들어갈 index를 설정해놓고, 진짜 최솟값을 찾은다음에 해당 인덱스에 최솟값을 넣어준다. 그러면, 해당 index에는 정렬되지 않은 요소들 중 최솟값이 들어가게 되고, 정렬이 완료된 후에는 처음 ~ 해당 index까지는 정렬이 완료된 요소들로 이루어진다

---

Java Code

static void selection_sort(int [] list, int N){
    int indexMin = 0; // 각 루프마다 최종 최솟값의 index

    for(int i = 0; i < N - 1; i++){
        indexMin = i; // 일단 정렬되지 않은 요소들에 대해서 가장 좌측 index를 최솟값의 index라고 임의 설정

        for(int j = i + 1; j < N; j++){
            // 설정한 index의 이후 요소들로부터 진짜 최솟값을 찾아내기
            if(list[j] < list[indexMin]){
                indexMin = j;
            }
        }
        // 진짜 최솟값의 index를 찾아내면 가장 좌측과 Swap
        int tmp = list[i];
        list[i] = list[indexMin];
        list[indexMin] = tmp;
    }
}

 

시간복잡도 분석 (상수는 추상적으로 C로 간주 & Worst Case 기준)

1) 일단 가장 안쪽 for문부터 분석

for(int j = i + 1; j < N; j++){
    // 설정한 index의 이후 요소들로부터 진짜 최솟값을 찾아내기
    if(list[j] < list[indexMin]){
        indexMin = j;
    }
}

- for문내에서 연산 개수 : C개 (상수)

- for문 루프 횟수 : (n-1) - (i+1) + 1 = n-i-1번 ("-1" 상수는 결국 생략)

>> C₁(n-i)

 

2) 바깥쪽 for문 분석

for(int i = 0; i < N - 1; i++){
    indexMin = i; // 일단 정렬되지 않은 요소들에 대해서 가장 좌측 index를 최솟값의 index라고 임의 설정

    for(int j = i + 1; j < N; j++){
        // 설정한 index의 이후 요소들로부터 진짜 최솟값을 찾아내기
        if(list[j] < list[indexMin]){
            indexMin = j;
        }
    }
    // 진짜 최솟값의 index를 찾아내면 가장 좌측과 Swap
    int tmp = list[i];
    list[i] = list[indexMin];
    list[indexMin] = tmp;
}

- for문내에서 연산 개수 : C₁(n-i) + C₂

 

3) 최종 시간복잡도

---

Example Code

package Sort;

/*
1) 일단 최솟값을 넣을 위치는 정해져있다 (맨 앞에서부터 맨마지막 - 1)
2) 여기에서 해당 위치의 값과 그 이후의 값들과 비교해서 더 작은 값이 있으면 exchange
 */

// Swap 방식

public class Selection_Sort_11 {
    public static void main(String[] args) {
        int [] list = new int[30]; // 정렬할 배열 A

        for(int i=0; i<list.length; i++)
            list[i] = (int)(Math.random()*201); // 0~200

        // 정렬 전 A 출력
        System.out.print("정렬 전 list []");
        for(int i=0; i<list.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(list[i] + "\t");
        }
        System.out.println("\n");

        selection_sort(list, list.length);

        // 정렬 후 A 출력
        System.out.print("정렬 후 list []");
        for(int i=0; i<list.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(list[i] + "\t");
        }
        System.out.println("\n");
    }

    static void selection_sort(int [] list, int N){
        int indexMin = 0; // 각 루프마다 최종 최솟값의 index

        for(int i = 0; i < N - 1; i++){
            indexMin = i; // 일단 정렬되지 않은 요소들에 대해서 가장 좌측 index를 최솟값의 index라고 임의 설정

            for(int j = i + 1; j < N; j++){
                // 설정한 index의 이후 요소들로부터 진짜 최솟값을 찾아내기
                if(list[j] < list[indexMin]){
                    indexMin = j;
                }
            }
            // 진짜 최솟값의 index를 찾아내면 가장 좌측과 Swap
            int tmp = list[i];
            list[i] = list[indexMin];
            list[indexMin] = tmp;
        }
    }
}