선택정렬(Selection Sort)

선택정렬(Selection Sort)은 심플한 정렬 알고리즘이다.

알고리즘이 어떤 식으로 동작하는지 살펴보자.

 

위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다.
모든 데이터들을 순차적으로 비교하여 가장 최소값을 찾는다. (여기는 10이 가장 작은 값이다.)

위에서 찾은 가장 작은 값은 10이다. 10을 첫번째 위치에 있는 (index = 0) 인 14와 교체한다. 

맨 왼쪽의 10은 이미 데이터의 모든 원소들 중 가장 작은값이 선택(selection)되어 이동하였으므로 그 다음에는 10을 뺀 나머지 원소들 중 가장 작은 값을 찾는다. 

10을 뺀 나머지 원소들 중에서 가장 작은 값은 14이므로 14를 두번째 위치에 있는(index = 1) 인 33과 교체한다.

이제 10, 14를 뺀 나머지 원소들 중에서 가장 작은 값을 찾고 위에 수행한 절차를 반복하면 아래 그림처럼 정렬이 된다.

▲ [출처] https://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm  

 

선택정렬은 알고리즘이 단순하나 성능은 평균 및 최악의 경우 둘다 O(N²) 이므로  대용량 데이터 셋에 사용하기에는 적합하지 않다.

 

구현 코드는 다음과 같다.

 
public class Main {
 
    public static void main(String[] args)  {
 
        int array[] = {14, 33, 27, 10, 35, 19, 42, 44};
        selectionSort(array);
 
        for (int i = 0 ;i < array.length ; i++){
            System.out.print(array[i] + " ");
        }
    }
 
    
    public static void selectionSort(int[] list) {
 
        for(int i  = 0 ; i < list.length -1 ; i++) {
 
            // 정렬된 요소를 제외한 나머지중 최소값을 찾는다.
            int min = i;
            for(int j = i + 1 ; j < list.length ; j++) {
                if(list[min] > list[j]) {
                    min = j ;
                }
            }
 
            swap(list, i, min);
        }
    }
 
    // 두 원소를 서로 swap(교환한다)
    private  static   void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 
}