Blog

[알고리즘] 선택정렬

On 9 10월, 2016 By With 1 Comment

선택정렬

선택정렬은 리스트를 모두 훑어서 리스트내 가장 장은 값을 찾아 리스트의 맨 앞으로 옮기며 정렬을 수행하는 방식이다. 다음과 같은 방식으로 처리되는데, 리스트를 훑다가 작은 값이 나오면 해당 index를 비교대상의 기준의 index로 변경하고 다음 루프에서 해당index와 증가된 루프index에 해당하는 리스트 값과 비교, 비교하여 찾은 가장 장은 값의 index를 가지고 리스트의 가장 작은값을 리스트의 맨 앞으로, 맨 앞의 값을 해당 리스트가 있던자리로 변경하여 다음 루프를 실행한다. 한번 리스트를 훑을때 1개의 값만 정렬이 가능하므로 정렬이 완료될 때 까지 이러한 과정을 반복한다.

복잡도가 높아 버블정렬과 함께 성능이 좋지않은 정렬알고리즘이다.

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 선택정렬
var aData = [4,5,3,1,2],
    nMinValIndex = 0,
    nCount = 1,
    temp;
    
for(var i=0; i<aData.length; i++){
    nMinValIndex = i;
    for(var j= i+1; j<aData.length; j++){
        console.log('최대시간복잡도',count++)
        if(aData[nMinValIndex] > aData[j]){
            nMinValIndex = j;
        }
    }
    temp = aData[nMinValIndex];
    aData[nMinValIndex] = aData[i];
    aData[i] = temp;
}

 

*해당 포스트는 알고리즘 학습을 위한 포스트로 정확하지 못한 개념과 코드가 있을 수 있습니다. 익숙한 언어인 js로 코드를 작성하였는데 개념이나 적절하지 못한 코드는 코멘트 들아주시면 감사하겠습니다 ^^

, ,