[자료구조] 선택 정렬

자료구조의 기본 알고리즘

 

" 선택 정렬 "

 

 

선택정렬이란, 가장 무식하고 단순한 방법으로 비교하여 정렬하는 알고리즘이죠

최악의 경우 데이터가 많아질수록 속도 성능은 제곱만큼 하락하는 정말 우리나라에선 사용 못할거에요 그쵸?

그리하여 결론은 선택정렬의 시간복잡도는 O(n²) 

 

 

그럼 알고리즘을 하나하나 비교해보도록 해볼게요.

 

 

 

아래와 같이 랜덤한 숫자 5개가 있다고 가정한다면

 

Step 1.

8

9

10

2

6

1-1 : 첫 번째 비교대상의 시작은 8이니, 배열의 최소 값은 8.

1-2 : 9는 최소값(8)보다 작은가 ? No !

1-3 : 10은 최소 최소값(8)보다 작은가 ? No !

1-4 : 2는 최소값(8)보다 작은가 ? Yes ! 그렇다면 최소값은 2.

1-5 : 6은 최소값(2)보다 작은가 ? No !

 

- 첫 번째 비교대상과 가장 최소값의 위치를 교환하자.

 

 

Step 2. 

2

9

10

8

6

2-1 : 두 번째 비교대상의 시작은 9이니, 배열의 최소 값은 9.

2-2 : 10은 최소값(9)보다 작은가 ? No !

2-3 : 8은 최소값(9)보다 작은가 ? Yes ! 그렇다면 최소값은 이제부터 8.

2-4 : 6은 최소값(8)보다 작은가 ? Yes ! 그렇다면 최소값은 이제부터 6.

 

- 두 번째 비교대상과 가장 최소값의 위치를 교환하자.

 

 

Step 3.

2

6

10

8

9

3-1 : 세 번째 비교대상의 시작은 10이니, 배열의 최소값은 10.

3-2 : 8은 최소값(10)보다 작은가 ?  Yes ! 그렇다면 최소값은 이제부터 8.

3-3 : 9는 최소값(8)보다 작은가 ? No !

 

- 세 번째 비교대상과 가장 최소값은 위치를 교환하자.

 

 

Step 4.

2

6

8

10

9

4-1 : 네 번째 비교대상의 시작은 10이니, 배열의 최소값은 10.

4-2 : 9는 최소값(10)보다 작은가 ? Yes ! 그렇다면 최소값은 이제부터 9.

 

- 네 번째 비교대상과 가장 최소값은 위치를 교환하자.

 

 

Step 5.

2

6

8

9

10

- 마지막 다섯번째 데이터는 비교할 대상이 없으므로 선택 정렬이 종료되지요 :-)

 

 

이렇게 선택정렬의 기본 개념 설명을 마치고, 간단하게 소스코드로 구현을 해볼게요.

 

 

 

function SelectSort(data) {
    for (let i = 0; i < data.length - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < data.length; j++) {
            if (data[j] < data[minIndex]) {
                minIndex = j;
            }
        } // 현재 값과 최소 값이 동일한 위치인 경우 스왑할 필요가 없음       
        if (i != minIndex) {
            let temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }
    }
    return data;
}
var data = [8, 9, 10, 2, 6];
console.log("--Original Data :> 8,9,10,2,6");
console.log("SelectSort Data :> " + SelectSort(data));

가볍에 메모장으로 작성하고 브라우저에서 테스트할 수 있는 Javascript로 구현을 했습죠 : )

 

 

SelectSort.zip

다운로드

 

위 첨부된 압축파일은 선택정렬 샘플 파일이에요.

실행시 브라우저 콘솔창에서 정렬된 결과값을 확인할 수 있어요 !