[알고리즘] 정렬 - 선택정렬

선택정렬이란

선택 정렬은 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 정렬.

동작 원리

1. 배열의 첫 인덱스를 기준으로 시작

2. 가장 작은 값을 가릴 변수minIdx 생성 (변수에 해당 인덱스를 저장)

3. 그리고 전체 배열 순회

4. 전체 배열 순회 중 첫 인덱스의 값보다 작은 값이 존재하면 minIdx에 해당 인덱스 저장 // 만약 이후에 더 작은 값이 나오면 계속해서 갱신

5. 그리고 가장 작은 값 인덱스를 맨 앞으로 보내고, 가장 작은 값 인덱스에 맨 앞의 값을 넣음으로써 교환

복잡도

선택 정렬의 시간 복잡도는 O(N²)이며 Worst, Average, Best 모두 동일합니다.

만약 배열의 크기가 10으로 주어지면, 버블정렬과 동일하게 배열의 제일 작은 값을 맨 앞에 두고, 그 나머지 (10-1)개만 하면 됨.

즉 10+9+8+..+1 = 55번
배열의 크기가 10개일 땐 55번의 연산이 이루어진다.

그러면

• 10+9+8+..+1 = 55
• N * (N - 1) / 2 = 55
• N * N = 55
• O(N*N) = 55

코드

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = new int[]{22, 50, 17, 25, 18, 32, 33, 44, 29, 8};

        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }

            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }

    }
}

// 출력 >> 8 17 18 22 25 29 32 33 44 50