선택 정렬( Selection sort ) 알고리즘

선택 정렬 알고리즘?

각 자리마다 알맞은 수를 선택하여 교체함으로써 정렬하는 알고리즘

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지 와 차례대로 비교하여 그중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

특징

장점

• 자료 이동 횟수가 미리 결정된다.

단점

• 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

구현

public static void selectionSort( int[] target ) {
    for( int i = 0; i < target.length -1; i++ ){
        int minIndex = i;
        for( int j = i+1; j < target.length; j++ ){
            if( target[minIndex] > target[j] ){
                minIndex = j;
            }
        }

        if( minIndex != i ){
            int temp = target[i];
            target[i] = target[minIndex];
            target[minIndex] = temp;
        }
    }
}

 

시간 복잡도

최상, 평균, 최악 모두 O(n^2)

버블 정렬 보다는 빠르다.

 

---

참고

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog