[알고리즘] 선택 정렬 (Selection Sort) - JAVA / 자바

선택 정렬(Selection Sort)

 - 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

 

 - 수행 방법

    1. 전체 원소 중 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리 교환

    ....

    2. n 번째로 작은 원소를 찾아 선택하여 n 번째 원소와 자리 교환

    3. 위 과정 반복하며 정렬 완성

 

 - 수행 과정

정렬되지 않은 배열 L = {69, 10, 30, 2, 8, 22}

69

10

30

2

8

22

① 기준 : 첫 번째 자리

2	10	30	69	8	22
정렬된 원소	정렬되지 않은 원소

② 기준 : 두 번째 자리

2	8	30	69	10	22
정렬된 원소		정렬되지 않은 원소

③ 기준 : 세 번째 자리

2	8	10	69	30	22
정렬된 원소			정렬되지 않은 원소

④ 기준 : 네 번째 자리

2	8	10	22	30	69
정렬된 원소				정렬되지 않은 원소

⑤ 기준 : 다섯 번째 자리

2	8	10	22	30	69
정렬된 원소					정렬되지 않은 원소

⑥ 기준 : 여섯 번째 자리

2	8	10	22	30	69
정렬된 원소

 

 - 알고리즘

selectionSort (list[], n)
	for (i ← 1; i<n; i ← i+1) {
    	// list[i], ..., list[n-1] 중 가장 작은 원소 list[k]를 선택하여 list[i]와 교환;
    	temp ← list[i];
        list[i] ← list[k];
        list[k] ← temp;
    }
end selectionSort()

 - 메모리 사용 공간 : n개의 원소에 대해 n개의 메모리 사용

 - 비교 횟수 : i단계 - 첫 번째 원소를 기준으로 n-i개의 원소 비교

 - 시간 복잡도 : O(n^2) 어떤 경우에서나 같음

 

< 분류 > 

정렬 장소 - 내부 정렬(Internal Sort)  >  교환 방식

[자료구조] 정렬 (Sort)