선택 정렬(Selection Sort)

개념

요소들 중에서 최대/최소값을 찾아 정렬하는 알고리즘입니다.
최대값 선택 시 내림차순 정렬을 진행합니다.(최솟값 선택 시 오름차순 정렬)

 

로직

오름차순 정렬을 기준으로 보자면
먼저 0~N-1 요소들 중에서 가장 작은 값을 찾고 0번째 인덱스와 교환해줍니다.

그다음 정렬된 0번째를 제외한
1~N-1 요소 중에서 가장 작은 값을 찾고 1번째 인덱스와 교환해줍니다.

이렇게 총 N-2번(마지막 인덱스 탐색 X) 반복하면 정렬이 완료됩니다.

추가 메모리 공간이 필요하지 않는 특징이 있습니다.

 

코드

자바로 작성한 선택정렬 코드는 다음과 같습니다.

// 선택 정렬: N^2 순회
// 오름차순 정렬
for (int i = 0; i < N-1; i ++) {

    int minIdx = i; // 가장 작은 값의 인덱스
    int minVal = arr[i]; // 가장 작은 값
    
    for(int j = i+1 ; j < N ; j ++){
        if(minVal > arr[j]){
            minVal = arr[j];
            minIdx = j;
        }
    }

    // swap
    arr[minIdx] = arr[i];
    arr[i] = minVal;

    System.out.println(Arrays.toString(arr));
}