[Algorithm] Selection Sort (선택 정렬)

1. Selection Sort (선택 정렬)

 

선택 정렬은 in-place 비교 정렬 중의 하나로 정렬되지 않은 부분에서 매번 최소값을 가지는 요소를 찾아서 가장 앞으로 자리를 옮기는 방식을 반복하여 정렬을 진행한다. 이 방법을 진행하는 중에는 배열이 최소값들이 순서대로 정렬된 부분과 아직 정렬되지 않은 두 부분으로 나뉘어진다.

 

• 정렬되지 않는 리스트에서 최소값을 찾는다.
• 최소값을 리스트의 가장 앞에 위치한 값과 자리를 바꾼다.
• 첫번째 값을 제외하고 두번째 값부터 리스트를 지정해서 정렬을 진행한다.

매 정렬마다 정렬되지 않은 리스트의 최소값이 정렬된 리스트 이동하는 방식으로 구현된다. 추가적으로 값을 저장하는 메모리가 필요하지 않기 때문에 공간 복잡도에서 이점을 가지게 된다.

 

 

2. Selection Sort 구현

 

매 정렬마다 정렬되지 않은 리스트의 최소값의 인덱스를 구하고 정렬되지 않은 리스트의 첫번째 인덱스의 값과 자리를 바꾼다. 자리를 변경 후 정렬된 리스트와 정렬되지 않은 리스트의 기준이 되는 인덱스에 1을 더해준다. N개의 값이 모두 정렬될 때까지 반복한다.

 

- Java로 구현한 Selection Sort

public class SelectionSort {
    private int[] array;

    public SelectionSort(int[] array) {
        this.array = Arrays.copyOf(array, array.length);
    }

    public int[] sort() {
        int N = array.length;
        for(int i = 0; i < N; i++) {
            int idx = i;
            for(int j = i + 1; j < N; j++) {
                if(array[j] < array[idx]) {
                    idx = j;
                }
            }

            int temp = array[idx];
            array[idx] = array[i];
            array[i] = temp;
        }
        return this.array;
    }
    
}

• source: https://github.com/rmk1075/CS/blob/main/Algorithm/Sorting/SelectionSort/SelectionSort.java

 

3. Selection Sort의 복잡도

- 시간 복잡도: O(N^2)

- 공간 복잡도: O(1)

 

 

[reference]

- https://ko.wikipedia.org/wiki/선택_정렬

선택 정렬 - 위키백과, 우리 모두의 백과사전

- https://www.geeksforgeeks.org/selection-sort/

Selection Sort - GeeksforGeeks