티스토리 뷰

Algorithm

선택 정렬 (Selection Sort)

WHITEPAEK 2018.12.04 22:14

선택 정렬 (Selection Sort)

 개념
최솟값을 찾아서 앞에 위치한 값과 교체하는 방법
<단순하지만 비효율적인 방법>
1. 주어진 데이터에서 최솟값을 탐색한다.
2. 탐색한 최솟값을 인덱스 첫 번째 위치한 값과 교체한다.
3. 첫 번째 위치한 값을 제외하고 나머지 데이터에서 최솟값을 다시 탐색 후 두 번째 위치한 값과 교체한다.
4. 마지막 데이터가 정렬될 때까지 위의 방법을 반복한다.

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

 Java 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
}
cs


 코드 해석

✓ 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  { 12, 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번 라인) { 12, 5, 4, 8, 9 } ☛ swap  { 1, 2, 4, 5, 8, 9 }


▪︎ 네 번째 탐색

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


▪︎ 다섯 번째 탐색

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


 코드 결과

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

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

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






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

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


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

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

'Algorithm' 카테고리의 다른 글

버블 정렬 (Bubble Sort)  (0) 2018.12.06
선택 정렬 (Selection Sort)  (0) 2018.12.04
이진 탐색 (Binary Search)  (0) 2018.12.01
순차 탐색 (Liner Search)  (0) 2018.11.29
재귀 함수 (Recursion Function)  (0) 2018.11.29
알고리즘 분석 (Algorithm analysis)  (0) 2018.11.29
댓글
댓글쓰기 폼
«   2019/07   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
Total
161,459
Today
24
Yesterday
473