선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

✐ 개념

최솟값을 찾아서 앞에 위치한 값과 교체하는 방법

<단순하지만 비효율적인 방법>

1. 주어진 데이터에서 최솟값을 탐색한다.

2. 탐색한 최솟값을 인덱스 첫 번째 위치한 값과 교체한다.

3. 첫 번째 위치한 값을 제외하고 나머지 데이터에서 최솟값을 다시 탐색 후 두 번째 위치한 값과 교체한다.

4. 마지막 데이터가 정렬될 때까지 위의 방법을 반복한다.

✐ 시간 복잡도: T(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

✐ Java 코드

public static void selectionSort(int[] data) {
    int minData, temp;
 
    for(int i = 0; i < data.length-1; i++) {
        minData = i;
 
        for(int j = i+1; j < data.length; j++) {
            if(data[minData] > data[j]) {
                minData = j;
            }
        }
 
        temp = data[i];
        data[i] = data[minData];
        data[minData] = temp;
    }
}

✐ 코드 해석

✓ data = { 2, 9, 5, 4, 8, 1 }

           위와 같이 크기가 6인 배열의 예시가 있다.

✓ minData는 최솟값의 위치를 저장하기 위한 변수이다.

✓ temp는 변경할 위치의 데이터를 임시로 저장하기 위한 변수이다.

▪︎ 첫 번째 탐색

▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 1

▫︎ (7번 라인) if(data[0] > data[1]) 결과 값이 (2 < 9)이므로 조건 불일치

▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 2

▫︎ (7번 라인) if(data[0] > data[2]) 결과 값이 (2 < 5)이므로 조건 불일치

▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 3

▫︎ (7번 라인) if(data[0] > data[3]) 결과 값이 (2 < 4)이므로 조건 불일치

▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 4

▫︎ (7번 라인) if(data[0] > data[4]) 결과 값이 (2 < 8)이므로 조건 불일치

▫︎ (4번 라인) i = 0

▫︎ (5번 라인) minData = 0

▫︎ (6번 라인) j = 5

▫︎ (7번 라인) if(data[0] > data[5]) 결과 값이 (2 > 1)이므로 조건 일치

▫︎ (8번 라인) minData = 5

▫︎ (13번 ~ 15번 라인) { 2, 9, 5, 4, 8, 1 } ☛ swap ☛ { 1, 9, 5, 4, 8, 2 }

▪︎ 두 번째 탐색

▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 1

▫︎ (6번 라인) j = 2

▫︎ (7번 라인) if(data[1] > data[2]) 결과 값이 (9 > 5)이므로 조건 일치

▫︎ (8번 라인) minData = 2

▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 2

▫︎ (6번 라인) j = 3

▫︎ (7번 라인) if(data[2] > data[3]) 결과 값이 (5 > 4)이므로 조건 일치

▫︎ (8번 라인) minData = 3

▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 4

▫︎ (7번 라인) if(data[3] > data[4]) 결과 값이 (4 < 8)이므로 조건 불일치

▫︎ (4번 라인) i = 1

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 5

▫︎ (7번 라인) if(data[3] > data[5]) 결과 값이 (4 > 2)이므로 조건 일치

▫︎ (8번 라인) minData = 5

▫︎ (13번 ~ 15번 라인) { 1, 9, 5, 4, 8, 2 } ☛ swap ☛ { 1, 2, 5, 4, 8, 9 }

▪︎ 세 번째 탐색

▫︎ (4번 라인) i = 2

▫︎ (5번 라인) minData = 2

▫︎ (6번 라인) j = 3

▫︎ (7번 라인) if(data[2] > data[3]) 결과 값이 (5 > 4)이므로 조건 일치

▫︎ (8번 라인) minData = 3

▫︎ (4번 라인) i = 2

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 4

▫︎ (7번 라인) if(data[3] > data[4]) 결과 값이 (4 < 8)이므로 조건 불일치

▫︎ (4번 라인) i = 2

▫︎ (5번 라인) minData = 3

▫︎ (6번 라인) j = 5

▫︎ (7번 라인) if(data[3] > data[5]) 결과 값이 (4 < 9)이므로 조건 불일치

▫︎ (13번 ~ 15번 라인) { 1, 2, 5, 4, 8, 9 } ☛ swap ☛ { 1, 2, 4, 5, 8, 9 }

▪︎ 네 번째 탐색

▫︎ 첫 번째 ~ 세 번째 탐색과 동일하게 진행 (정렬이 완료되어서 설명 생략)

▪︎ 다섯 번째 탐색

▫︎ 첫 번째 ~ 세 번째 탐색과 동일하게 진행 (정렬이 완료되어서 설명 생략)

✐ 코드 결과

모든 탐색과 정렬이 끝난 후 최종적으로 출력되는 결과 값은 { 1, 2, 4, 5, 8, 9 }이다.

선택한 배열의 위치를 제외한 나머지 배열에서 최솟값을 찾은 후 오름차순으로 정렬하는 방법이다.

(정렬된 배열의 위치는 탐색에서 제외)

✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!

(확인 후 수정하도록 하겠습니다~^^)

✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!

(지식을 공유해주세요~^^)