[algorithm] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

 

 이번 시간에는 선택 정렬에 대해서 알아보도록 하겠습니다. 선택정렬은 정렬순서에 맞게 하나씩 선택해서 옮기면서 정렬이 되게 하는 알고리즘 입니다. 

 

 어떻게 보면 수열에서 최소값부터 시작해서 값을 하나씩 찾으면서 새로운 수열에 순차적으로 넣어주는 형식이라고 할수 있습니다. 그런데 실제 구현을 하려고 할때 굳이 작은 값들을 순차적으로 새로운 배열에 넣어주는 형식 말고 하나의 배열에서 자리의 교체를 통해서 정렬을 할수 있는 방법이 있습니다.

그림을 보면 아래와 같습니다.

 실제 코드는 아래와 같습니다.

public void doSort(int[] numArr){
        int min;
        for(int i = 0; i < numArr.length-1; i++){
            min = i;
            for(int j = i + 1; j < numArr.length; j++){
                if(numArr[j] < numArr[min]){
                    min = j;
                }
            }
            int tmp = numArr[min];
            numArr[min] = numArr[i];
            numArr[i] = tmp;
        }
    }

참고자료 : 윤성우의 열혈 자료구조