[정렬] 선택 정렬

선택 정렬이란?

선택 정렬은 제자리 정렬(In- place sorting) 알고리즘의 하나로 원소를 넣을 위치는 이미 정해져있으며, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

선택 정렬 과정

작업 순서

1. 리스트를 순회하며 가장 작은 요소 찾기
2. 가장 작은 요소와 첫 번째 요소 교환
3. 리스트의 다음 위치로 이동
4. 반복

시간 복잡도

최악, 평균, 최선 모든 경우에 O(n^2)의 시간 복잡도를 가집니다.

공간 복잡도

O(1): 제자리 정렬 알고리즘으로 추가적인 메모리 사용이 거의 없습니다.

장점

구현이 간단하고 이해하기 쉽습니다.

단점

시간 복잡도가 O(n^2)이기 때문에, 데이터의 크기가 큰 경우 비효율적입니다.

코드

    public void selectionSort(int[] array) {
        int n = array.length;

        // 배열을 순회하면서 정렬
        for (int i = 0; i < n - 1; i++) {
            // 현재 범위에서 가장 작은 원소의 인덱스를 찾습니다.
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }