선택 정렬

선택 정렬

선택정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치해 놓고, 나머지 (n-1) 개중에 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식입니다.

정렬 과정

배열의 첫 번째 요소부터 시작하여 그다음 요소들과 비교합니다.

현재 위치의 요소를 기준으로, 그 이후의 모든 요소들과 비교하여 최솟값을 찾습니다.

최솟값을 찾으면 해당 값과 현재 위치의 값을 교환합니다.

이러한 과정을 배열의 마지막 요소까지 반복합니다.

 

[이미지 출처] :  자바 [JAVA] - 선택 정렬 (Selection Sort) (tistory.com)

 

Java Code

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 배열의 모든 요소를 순회하며 정렬 수행
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 최솟값의 인덱스를 저장할 변수
            
            // 최솟값을 찾기 위해 현재 위치 이후의 요소들과 비교
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 최솟값을 찾으면 현재 위치의 값과 최솟값을 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        
        System.out.println("정렬된 배열:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

장점

구현 간단하고 이해하기 쉬움

작은 데이터셋에서는 다른 알고리즘들과 비슷한 성능을 보일 수 있다.

단점

대량의 데이터를 처리할 때 비효율적이며 느리다.

시간 복잡도가 O(n^2)로 동일하여 성능이 좋지 않음.